A deterministic finite automaton for faster protein hit detection in BLAST
A deterministic finite automaton for faster protein hit detection in BLAST
复制标题
DOI：
10.1089/cmb.2006.13.965
复制
发表时间：
2006-05-01
影响因子：
1.7
通讯作者：
Cannane, Adam
中科院分区：
文献类型：
--
作者：
Cameron, Michael;Williams, Hugh E.;Cannane, Adam
BLAST是最流行的生物信息学工具，每天用于运行数百万个查询。然而，评估这样的查询很慢，在现代工作站上通常需要几分钟。因此，面对指数增长的集合大小，通过改进其算法和优化，对改进搜索时间至关重要。我们提出了一个优化的BLAST算法的第一阶段，专门为蛋白质搜索设计。它产生与NCBI-BLAST相同的结果，但在基于英特尔的平台上大约59%的时间；我们还展示了其他流行架构的结果。总的来说，这节省了大约15%的典型BLAST总搜索时间。我们的方法使用确定性有限自动机（DFA），灵感来自1990年BLAST算法中使用的原始方案。这些技术针对现代硬件进行了优化，谨慎地使用缓存敏感的方法来提高速度。我们优化的DFA方法已集成到BLAST的新版本中，该版本可在http://www.fsa-blast.org/免费下载。
BLAST is the most popular bioinformatics tool and is used to run millions of queries each day. However, evaluating such queries is slow, taking typically minutes on modern workstations. Therefore, continuing evolution of BLAST-by improving its algorithms and optimizations-is essential to improve search times in the face of exponentially increasing collection sizes. We present an optimization to the first stage of the BLAST algorithm specifically designed for protein search. It produces the same results as NCBI-BLAST but in around 59% of the time on Intel-based platforms; we also present results for other popular architectures. Overall, this is a saving of around 15% of the total typical BLAST search time. Our approach uses a deterministic finite automaton (DFA), inspired by the original scheme used in the 1990 BLAST algorithm. The techniques are optimized for modern hardware, making careful use of cache-conscious approaches to improve speed. Our optimized DFA approach has been integrated into a new version of BLAST that is freely available for download at http://www.fsa-blast.org/.