Research on Fast Search for DNA Sequence Using Vector Quantization

在GenBank、EMBL、DDBJ等数据库中积累了大量的DNA序列数据。此外，数据量仍呈指数级增长。DNA序列的同源性检索是生命科学领域的一项重要任务。在本研究中，我们提出了一种高效的分层DNA序列搜索方法，以提高搜索速度，同时保持精度不变。对于给定的查询DNA序列，首先采用基于直方图特征的快速局部搜索方法作为过滤机制，然后扫描数据库中的序列；大量相似性较低的DNA序列将被排除在后续搜索之外。然后对每个余数序列应用Smith-Waterman算法。利用GenBank序列数据进行的实验结果表明，将直方图信息与Smith-Waterman算法相结合的方法在DNA序列搜索中具有更高的效率。

The enormous quantity of DNA sequence data has been accumulated in the database like GenBank, EMBL, and DDBJ, etc. Moreover, the volume of data still increases in exponential. Homology search of DNA sequences is the most important task in the life science area. In this research, we propose an efficient hierarchical DNA sequence search method to improve the search speed while the accuracy is being kept constant. For a given query DNA sequence, firstly, a fast local search method using histogram features is used as a filtering mechanism before scanning the sequences in the database. A large number of DNA sequences with low similarity will be excluded for latter searching. The Smith-Waterman algorithm is then applied to each remainder sequences. Experimental results using GenBank sequence data show the proposed method combining histogram information and Smith-Waterman algorithm is more efficient for DNA sequence search.