具有线性计算复杂度的数据库同源性搜索算法。

Data bank homology search algorithm with linear computation complexity.

作者信息

Strelets V B, Ptitsyn A A, Milanesi L, Lim H A

机构信息

Supercomputer Computations Research Institute, Florida State University, Tallahassee 32306-4052.

出版信息

Comput Appl Biosci. 1994 Jun;10(3):319-22. doi: 10.1093/bioinformatics/10.3.319.

DOI:10.1093/bioinformatics/10.3.319

PMID:7922689

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.

摘要

提出了一种用于数据库同源性搜索的新算法。新算法的主要优点是：（i）线性计算复杂度；（ii）低内存需求；（iii）对局部区域同源性的存在具有高灵敏度。该算法首先计算查询序列中k元组“实现”的指示矩阵，然后在数据库序列的窄范围内搜索适当数量的匹配k元组。它不需要k元组坐标列表和数据库序列的内存放置。该算法在一个程序中实现，可在与PC兼容的计算机上执行，并在PIR和GenBank数据库上进行了测试，结果良好。还讨论了一些旨在提高选择性的修改。作为一个应用示例，给出了对小鼠同源异型蛋白HOX 3.1同源性的搜索。