Data bank homology search algorithm with linear computation complexity.
A new algorithm for data bank homology search is proposed. The principal advantages of the new algorithm are: (i) linear computation complexity; (ii) low memory requirements; and (iii) high sensitivity to the presence of local region homology. The algorithm first calculates indicative matrices of k-tuple 'realization' in the query sequence and then searches for an appropriate number of matching k-tuples within a narrow range in database sequences. It does not require k-tuple coordinates tabulation and in-memory placement for database sequences. The algorithm is implemented in a program for execution on PC-compatible computers and tested on PIR and GenBank databases with good results. A few modifications designed to improve the selectivity are also discussed. As an application example, the search for homology of the mouse homeotic protein HOX 3.1 is given.
Strelets
V B
VB
Supercomputer Computations Research Institute, Florida State University, Tallahassee 32306-4052.
Ptitsyn
A A
AA
Milanesi
L
L
Lim
H A
HA
D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D016208:Databases, Factual; D015723:Gene Library; D005801:Genes, Homeobox / Q000235:genetics; D016247:Information Storage and Retrieval; D016014:Linear Models; D008432:Mathematical Computing; D051379:Mice; D012680:Sensitivity and Specificity; D017385:Sequence Homology