SSAHA: A fast search method for large DNA databases
SSAHA: A fast search method for large DNA databases
复制标题
DOI：
10.1101/gr.194201
复制
发表时间：
2001-10-01
期刊：
影响因子：
7
通讯作者：
Mullikin, JC
中科院分区：
文献类型：
--
作者：
Ning, ZM;Cox, AJ;Mullikin, JC
我们描述了一种算法，SSAHA（序列搜索和通过哈希算法对齐），用于在包含多个DNA的数据库上进行快速搜索。数据库中的序列通过将它们分解为连续碱基的连续K-tuples进行预处理，然后使用哈希表来存储每个k-tuple的每次出现的位置。通过从哈希表中获取查询序列中每个k-tuple的“命中”，然后对结果进行排序来完成数据库中的查询序列。我们讨论了元组长度k对算法的搜索速度，记忆使用量和灵敏度的影响，并介绍了计算实验的结果，这些实验表明SS：HA可以比BLAST或FASTA快三到四个数量级，而，而FastA则可以快。与后缀树方法相比，需要更少的内存。 SSAHA算法用于高通量单核苷酸多态性（SNP）检测和非常大的序列组件。此外，它为Ensembl项目提供了基于Web的序列搜索设施。
We describe an algorithm, SSAHA (Sequence Search and Alignment by Hashing Algorithm), for performing fast searches on databases containing multiple gigabases of DNA. Sequences in the database are preprocessed by breaking them into consecutive k-tuples of k contiguous bases and then using a hash table to store the position of each occurrence of each k-tuple. Searching for a query sequence in the database is done by obtaining from the hash table the "hits" for each k-tuple in the query sequence and then performing a sort on the results. We discuss the effect of the tuple length k on the search speed, memory usage, and sensitivity of the algorithm and present the results of computational experiments which show that Ss: HA can be three to four orders of magnitude faster than BLAST or FASTA, while requiring less memory than suffix tree methods. The SSAHA algorithm is used for high-throughput single nucleotide polymorphism (SNP) detection and very large scale sequence assembly. Also, it provides Web-based sequence search facilities for Ensembl projects.