Biopolymers and cell. 1990. Volume 6. № 6. 7 - 13

P. A. Pevzner

FILTRATION EFFICIENCY IN RAPID HOMOLOGY SEARCH STATISTICAL ALGORITHMS

Summary

    Upon searching local homologies in long sequences ('homology search in nucleotide and amino acid sequences banks, selection of optimal oligonucleotide probes etc.) the neces¬sity of a «rapid» homology search becomes acute. Quadratic complexity of (he dymanic programming algorithms (Needleman—Wunsch and Sellers type) forces the employment of filtration methods, that permits one to reject the sequences with a low homology le¬vel (among the filtration methods the 1—tuple analysis and the statistical method of Mironov—Alexandrov were used). But theoretical substantiations of such algorithms have not been made yet. The present work introduces the notion of filtration efficiency and the efficiency of several filters is given. It was shown that in the 1—tuple analysis the filtration efficiency is associated with the potential extension of the original four— letter alphabet. The formulas that allow choosing the filtration parameters are presented.