title: Data bank homology search algorithm with linear computation complexity.
abstract: 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.
authors.affiliation: Supercomputer Computations Research Institute, Florida State University, Tallahassee 32306-4052.
authors.forename: V B
authors.initials: VB
authors.lastname: Strelets
authors.forename: A A
authors.initials: AA
authors.lastname: Ptitsyn
authors.forename: L
authors.initials: L
authors.lastname: Milanesi
authors.forename: H A
authors.initials: HA
authors.lastname: Lim
mesh_terms: 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