Dream-stellar：一种并行且空间效率高的精确局部比对算法

《BMC Bioinformatics》：Dream-stellar: parallel and space efficient exact local alignment

基因组长序列本地对齐中，DREAM-Stellar通过并行化加速和IBF数据结构优化，将处理速度提升900倍，有效减少重复序列影响，相比BLAST等工具显著提高匹配准确率，适用于基因组比对场景。

　　

摘要

背景

在大型基因组数据集中搜索局部比对是一个计算上的挑战。一个特别的障碍是处理重复序列，这些序列出现在不同的上下文中，会导致较高的运行时间成本。对于实际的同源性搜索来说，开发一个特定但敏感的过滤机制非常重要。良好的过滤机制可以在比对之前缩小搜索范围，同时不会遗漏重要的匹配结果。

结果

我们推出了DREAM-Stellar，这是一个并行化的、更新版的成对局部比对工具Stellar。新的比对工具DREAM-Stellar包括四个步骤：预处理查询和参考序列、构建用于分发查询的数据结构、并行计算结果，最后将结果合并。在分发查询时，我们使用了IBF数据结构以及一个新的局部比对预过滤器。我们对五种局部比对工具在模拟数据和真实基因组数据上的性能进行了比较，发现像BLAST这样的启发式工具会遗漏大量重要的局部比对结果，或者被数百万个不那么重要的匹配结果所淹没。与单线程版本相比，DREAM-Stellar在32个并行线程上的运行速度提高了900倍，能够在几分钟内找到一对基因组之间的所有比对结果。因此，DREAM-Stellar的运行时间与BLAST等工具相当。

结论

DREAM-Stellar在处理非常长的序列时非常实用且速度快，使其成为在编辑距离模型下寻找基因组序列之间局部比对的理想新工具。该软件可在https://github.com/seqan/dream-stellar处免费获取，适用于Linux和Mac OS X系统。