A Comprehensive Analysis of Sequence Alignment Algorithms for LongRead Sequencing

A Comprehensive Analysis of Sequence Alignment Algorithms for LongRead Sequencing   长Read序列比对算法的综合分析

As the length of sequencing read increasing, greater bioinformation is demanded from long read aligner. The short-read aligner is often widely used to make alignment very fast and accurate, but the approach is ill-suited to finding longer, gapped alignments with long indels. A wide variety of alignment algorithms and aligners have been subsequently developed over the past few years. In this article, we survey the theoretical foundations that underlie long-read alignments and highlight the options and practical trade-offs that need to be considered. Through the evaluation of the sophisticated experiments both on simulated and real data, we illustrate the performance of these aligners on the accuracy, the time and memory cost, as well as the scalability for the modern multi-core architecture. We also consider the future development of long-read alignment algorithms.

  摘要

  随着测序读取长度的增加，对长读取比对者的生物信息要求也越来越高。短读对准器通常被广泛用于使对准非常快速和准确，但这种方法不适合寻找长indel长间隙对准。在过去的几年里，各种各样的对准算法和对准器相继被开发出来。在这篇文章中，我们调查了长 read校准的理论基础，并强调了需要考虑的选项和实际权衡。通过对模拟数据和实际数据的复杂实验的评估，说明了这些对准器在精度、时间和内存开销方面的性能，以及现代多核体系结构的可扩展性。我们也考虑了长读对齐算法的未来发展。

介绍 

虽然DNA测序不再是天方夜谭，但基因组中包含的生命信息仍然是一个谜。
这些问题不仅来自遗传信息中的固有因素，如SNP(单核苷酸多态性)、长indels、基因组重复(基因组中以几乎相同的形式重复的DNA片段)和各种类型的结构变异。
这种情况变得更加复杂的事实是，序列的长度远远短于基因组或基因组特征的研究。
而且，即使短读本身是干净的，读大小本身也是一种噪音或信息丢失的形式。
信息的丢失表现在基因组的装配质量上。
为了解决长度问题，长读测序技术已经被开发出来，可以产生长读，这可以增加重要基因的覆盖，通常跨越一个以上的杂合SNP[1,2]。
这种长读技术的应用包括从头组装(人类[3]，植物或其他复杂基因组[4,5]，人类基因组分阶段[6,7]，以及癌症序列[8]。
针对长参考序列有效地对齐长读操作对对齐工具的开发提出了新的挑战。

 

与短读对齐相比，长读对齐具有一组不同的设计目标。首先，在长读对齐中，我们更倾向于查找局部匹配，因为长读更容易受到引用中的结构变化和错误集的影响，但是受接近读结束的错误匹配的影响更小。相比之下，在短序列比对中，由于长度限制，我们可能会将全长读到参考基因组，并减少由于读到末端的不匹配而导致的参考偏差。其次，长读对准器必须对对准间隙持宽容态度，因为在长读过程中插入更频繁，而且可能是某些技术的主要测序错误来源。但是，只有在短读对准器进行对齐时，才允许使用未打开的或有限的间隙(例如最大一个间隙)，因为它们无法找到更多的间隙，或者在针对此任务进行调优时性能会迅速下降。第三，允许部分对齐读序列的嵌合对齐在longread对齐中将变得非常重要，而在short -胎面对齐中通常很少考虑这一点。

在考虑提高长读对齐速度的算法时，像当前大多数短读对齐器中使用的哈希表索引并不是惟一的选择。BWT和FMindex可以实现较小的内存占用，并且能够提供与标准的Smith-Waterman比对相同的结果，但是与人类基因组序列比对时要快数千倍[9-11]。通过使用动态规划算法和加速特定的硬件特性，如SIMD(单指导员多数据)，通过自顶向下遍历从后缀树中采样的每个子序列，可以有效地对查询进行对齐。在后缀树中，相同的序列在单一路径上折叠，避免了相同子序列的重复比对，从而节省了时间

在这篇文章中，我们首先系统地总结了第2节中针对高通量长读序列映射问题，在最先进的对齐工具中设计的所有技术及其适应性。然后在第3节中，我们用工具选择、测试数据集和硬件环境的标准来检查实验设计。我们将在第4节中使用模拟的和真实的数据集来评估这些工具的映射准确性、运行时和内存使用量以及可伸缩性。最后，我们将讨论对齐算法的未来发展，并在第5部分对本文进行总结。

THE LONG-READ ALIGNMENT ALGORITHMS
Recently, several well-known and widely used long read aligners have been developed, including AGILE (Misra and Agrawal, 2010) [12], GASSST (Rizk and Lavenier, 2010) [13], SSAHA2 (Zemin and Anthony, 2011) [14], BLASR (Mark and Glenn, 2012) [15], Bowtie2 (Langmead and Salzberg, 2012) [16], CUSHAW2 (Yongchao and Bertil, 2012) [17], YAHA (Gregory and Ira, 2012) [18] and BWAMEM (Li and Durbin, 2013) [19], as shown in Table 1. At present, all long-read alignment follow the seed-and-extend paradigm, and the selection process of the high similar region to produce the final alignment. Therefore our review of long-read alignment algorithms will be described orderly in three steps: the seeding step, the extension step and the filtering step. Because the chimeric alignment is only aware in BWA-MEM, it will not be discussed in this paper.

长读对齐算法最近,几个著名的和广泛使用的长阅读对准器已经被开发出来,包括AGILE (Misra and Agrawal, 2010) [12], GASSST (Rizk and Lavenier, 2010) [13], SSAHA2 (Zemin and Anthony, 2011) [14], BLASR (Mark and Glenn, 2012) [15], Bowtie2 (Langmead and Salzberg, 2012) [16], CUSHAW2 (Yongchao and Bertil, 2012) [17], YAHA (Gregory and Ira, 2012) [18] and BWAMEM (Li and Durbin, 2013) [19],如表1所示。目前，所有的长读比对都遵循种子扩展范式，并通过高相似区域的选择过程来产生最终比对。因此，我们对长读对齐算法的回顾将有序地分为三个步骤:播种步骤、扩展步骤和过滤步骤。由于嵌合排列仅在BWA-MEM中被发现，因此本文不进行讨论。