BMC Bioinformatics. 2014;15 Suppl 9(Suppl 9):S12. doi: 10.1186/1471-2105-15-S9-S12. Epub 2014 Sep 10.
Although there are many different algorithms and software tools for aligning sequencing reads, fast gapped sequence search is far from solved. Strong interest in fast alignment is best reflected in the $10(6) prize for the Innocentive competition on aligning a collection of reads to a given database of reference genomes. In addition, de novo assembly of next-generation sequencing long reads requires fast overlap-layout-concensus algorithms which depend on fast and accurate alignment.
We introduce ARYANA, a fast gapped read aligner, developed on the base of BWA indexing infrastructure with a completely new alignment engine that makes it significantly faster than three other aligners: Bowtie2, BWA and SeqAlto, with comparable generality and accuracy. Instead of the time-consuming backtracking procedures for handling mismatches, ARYANA comes with the seed-and-extend algorithmic framework and a significantly improved efficiency by integrating novel algorithmic techniques including dynamic seed selection, bidirectional seed extension, reset-free hash tables, and gap-filling dynamic programming. As the read length increases ARYANA's superiority in terms of speed and alignment rate becomes more evident. This is in perfect harmony with the read length trend as the sequencing technologies evolve. The algorithmic platform of ARYANA makes it easy to develop mission-specific aligners for other applications using ARYANA engine.
ARYANA with complete source code can be obtained from http://github.com/aryana-aligner.
尽管有许多不同的算法和软件工具可用于对齐测序读段,但快速缺口序列搜索仍远未得到解决。对快速对齐的强烈兴趣最好反映在 Innocentive 竞赛上,该竞赛的奖金为 100 万美元,用于将一组读段与给定的参考基因组数据库对齐。此外,下一代测序长读段的从头组装需要快速的重叠布局共识算法,这些算法依赖于快速准确的对齐。
我们引入了 ARYANA,这是一种快速缺口读段对齐器,它建立在 BWA 索引基础设施的基础上,具有全新的对齐引擎,使其速度明显快于其他三个对齐器:Bowtie2、BWA 和 SeqAlto,具有相当的通用性和准确性。ARYANA 采用种子和扩展算法框架,而不是耗时的回溯处理不匹配的过程,通过集成包括动态种子选择、双向种子扩展、无重置哈希表和缺口填充动态编程在内的新型算法技术,显著提高了效率。随着读长的增加,ARYANA 在速度和对齐率方面的优势变得更加明显。这与测序技术发展带来的读长趋势完全一致。ARYANA 的算法平台使其易于使用 ARYANA 引擎为其他应用开发特定任务的对齐器。
ARYANA 的完整源代码可从 http://github.com/aryana-aligner 获得。