Data bank homology search algorithm with linear computation complexity
- 1 June 1994
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 10 (3) , 319-322
- https://doi.org/10.1093/bioinformatics/10.3.319
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.Keywords
This publication has 0 references indexed in Scilit: