第三代测序中基于德布鲁因图的长读错误纠正算法
摘要——PacBio单分子实时测序平台可以产生大量的长读序列，这对基因组的从头组装非常重要。尽管这些长读取具有15%的高错误率，但是由于它们的高错误率而放弃它们是不明智的。Illumina测序平台产生了长度在100 bp左右的短读，错误率低，成本低。但是组装形成的分支很多，不利于后续对基因组的分析。本文提出了一种新的混合纠错方法LecdB，它使用精确的短读来纠正具有较高错误率的长读。首先，从参考序列的短读构建两个固定长度和可变长度的de Bruijn图。然后，遍历要校正的长读数，以找到与固定长度的德布鲁因图一致的强K-mer。使用最大精确匹配算法将没有强K-mer的长读与可变长度de Bruijn图中的节点进行比对。实验表明，与其他基于de Bruijn图的长读校正算法相比，可以获得更好的结果。
关键词—德布鲁因图，纠错，通量，最大精确匹配
I.介绍
DNA测序确定四种含氮碱基(腺嘌呤[A]胞嘧啶[C]鸟嘌呤[G]胸腺嘧啶[T])的序列，是生命科学中的一项基础实验。作为第一代测序平台，Sanger [1]测序基于在体外DNA复制期间通过DNA聚合酶选择性掺入链终止双脱氧核苷酸。这种方法产生的读数具有接近99.999%的极高准确度，但长度相对较短，需要较长的测序时间和较高的成本。以Illumina为代表的第二代测序平台是基于Sanger测序技术开发的。高通量、短运行时间、低成本和低错误率是第二代测序技术的主要特点。第二代测序技术的缺点之一是产生的读长度很短，大约100-200个碱基。由结果组装而成的de Bruijn图有很多分支，无法确定哪一个是正确的路径，不利于后续的基因组分析和从头组装，无法有效利用。与第二代测序技术相比，以PacBio单分子实时(SMRT)测序平台和Oxford Nanopore Technologies的单分子测序平台为代表的第三代测序平台产生的平均读长度可以达到10kb-15kb，可以解决基因组组装、转录组重建、宏基因组学等现代生物学和医学的计算问题。但是第三代测序技术最明显的缺点是错误率可能高达15% [2]。
由于长读包含丰富的遗传信息，长读的纠错是目前最重要的任务。目前，纠错算法可以分为三种类型:长读自纠错；
短读取直接与长读取对齐，然后使用对齐信息进行纠错；
短读被组装形成与长读码对齐的重叠群。
对准信息用于误差校正。长读取自校正算法由LoRMA代表[3]。基于迭代的de Bruijn图，通过逐渐增加K-mer的长度来多次校正长读数。由于不使用参考短读数，需要更深的测序深度，这导致数据集过大，对计算机硬件的要求相对较高。PacBioToCA [4]是长读取误差校正算法的代表，其将短读取与长读取对齐。在短读与长读比对之后，在长读的重复区域中，仅保留具有最高相似性的比对结果用于纠错。但占用大量内存和硬盘空间，运行时间长，不符合当前对测序速度的要求。
基于将短读组装成重叠群的长读纠错算法可以由de Bruijn图算法来表示。de Bruijn图算法最早由Leena Salmela提出，并开发了纠错工具LoRDEC [5]。短读用于构建德布鲁因图，然后映射到长读进行纠错，大大提高了纠错速度。Jabba [6]在此基础上打破了种子长度的限制，使用伪匹配的方法，通过使用最大精确匹配算法来寻找种子，这样种子可以更长，在将长读数与de Bruijn图对齐时对齐精度更高，纠错结果更准确。FMLRC [7]在图形创建过程中使用FM-index来动态选择K-mer大小，并构造两个德布鲁因图，以便可以进行两次误差校正。
我们提出了一种基于德布鲁因图的混合纠错方法。构造了两个德布鲁因图。首先，在长读中搜索强K-mer，然后使用具有固定长度K-mer的de Bruijn图来纠正错误。第二，具有可变长度K-mer的de Bruijn图用于那些没有找到强K-mer的长读取的错误校正。这种方法可以保持高通量和高比对一致性，并尽可能减少运行时间。
II.德布鲁因图的基本原理
在生物医学领域，长度为K的弦称为K-mer。K-mer的具体解释如下:设r是一串碱基，其字母表为∑