第二、三代基因组测序数据混合拼接软件综述

第二、三代基因组测序数据混合拼接软件综述

王 昊1，陈 挺2*  （1.清华大学 计算机科学与技术系，北京 10084； 2.清华大学 计算机系、清华大学人工智能研究院，北京 10084）    摘要:DNA 测序是生物信息学研究的重要内容之一，对测序序列的从头拼接是其中非常基础而重要 的步骤。随着测序技术的不断更新，新的第三代测序数据拥有更长的序列长度、高错误率等性质， 针对这些性质，同时使用二代、三代测序数据进行混合拼接是获得更好的拼接结果一种重要方式。 本文介绍了现有的混合拼接软件的基本原理，并比较了不同软件拼接结果。最后，本文对选择拼接 软件以及提出新的混合拼接方法的研究方向给出了建议。 关键词：生物信息学；全基因组序列拼接；第三代测序技术；混合拼接； 中图分类号：TP391；TP301.6   文献标志码：A    文章编号：1672-5565（2020）04-000-00      Survey of computational methods for second- and third-generation sequencing hybrid assembly WANG Hao1， CHEN Ting2*  (1.Tsinghua University Computer Science and Technology, Beijing 100084, China;  2. Department of Computer Science and Technology & Institute for Artificial Intelligence, Tsinghua University, Beijing 100084, China)    Abstract：DNA sequencing is essential for Bioinformatics research, and de novo genome assembly is the first step toward characterization of microbial species. With the continuous development of sequencing technology, the new third-generation sequencing produces longer reads but with higher error rates than the second-generation sequencing. Based on these properties, combining second- and third-generation sequencing data for hybrid assembly promises to obtain better de novo assembly results. This article introduces the basic principles of state-of-the-art hybrid assembly methods and compares the assembly results of different software tools. Finally, this paper suggests selection of assembly software and proposes how to improve hybrid assembly approaches. Keywords: Bioinformatics; Whole genome assembly; Third-generation sequencing technology; Hybrid assembly    DNA 作为生物重要的遗传物质，一直被生物学家在不同层面进行深入研究。从发现 DNA 的结 构开始，人类通过研究复杂多样的基因组，在健康和疾病的研究中已取得了长足的进步。为了研究 DNA 序列，DNA 测序是必不可少的环节。由于现有技术仅能测得较短的 DNA 序列，因此将 DNA测序获得的读段（Read）进行从头拼接（De novo assembly）成为较长的重叠群（Contig）、进而拼装 成更长的骨架（Scaffold）、最终获得完整的基因组（Genome）一直是生物信息学的重要课题。而随 着测序技术的发展，测序试剂和仪器不断更新换代，测序的速度、价格，以及测序获得的读段在质 量、长度、碱基偏好等方面特性也有变化，针对新的测序数据设计更适应数据的拼装算法也是不断 推陈出新。 1977 年，由 Sanger 等人提出的链终止法测序方法开创了测序技术的先河[1]，这种测序方法后来 通常被称为 Sanger 测序法，即第一代测序技术。第一代测序技术的主要特点是获得的读段序列长度 较长，通常可达 1 000 bp，准确性高，可达 99.999%，但是测序的成本比较高，通量也比较低。这些 特点决定了第一代测序技术通常被应用于长度较短，或者十分重要的基因组测序任务中。  为了解决第一代测序技术具有通量低、成本高的局限性， 454 焦磷酸测序[2]，Rothberg [3]等测序 仪器相继诞生。这些新一代测序仪可以获得每次运行上百万上亿次读数的更高输出，但是读取长度 更短，最新一代的 Illumina 机器现在输出大约 250-300 bp 的高质量读数。这些测序技术现在被称为 第二代测序技术。第二代测序技术还包括 Ion Torrents 的 Ion Proton 测序仪。与 Sanger，454 和 Illumina 相比，这种技术不依赖于光学方法，可以使用购买成本较低的机器进行快速而便宜的测序。尽管第 二代测序仪具有高通量、相对便宜的价格，同时具有高质量的碱基和低错误率，但它们测得的读段 较短是主要问题。现在，第二代测序技术可以测得包括复杂的哺乳动物在内的绝大多数生物的基因 组，并保证成本控制在可接受的范围内。这意味着几乎所有生物的基因组都向人类打开了解码的道 路，并允许人们对这些基因组做进一步的分析。     随着技术的发展，第三代测序技术应运而生。由 Pacific Biosciences（PacBio）公司开发的测序 仪（如 RS I，RS II 和 Sequel 机器）使用单分子实时（SMRT）测序技术[2]，而牛津纳米孔技术（ONT） 开发了用于纳米孔测序的装置[4]。 与第二代技术（如 454，Illumina，Ion Torrent）相比，这些第三 代测序方法在测序文库制备过程中不包括扩增步骤，因此能够进行单分子测序，去除了扩增过程带 来的偏倚（Bias）。此外，第三代测序技术预期的读段长度远远高于第二代技术，平均读段长度可以 超过 6-8 kbp，最大读段长度超过 30-150 kbp[5]。使用第三代测序长读段文库可以定向、排序、间隔 或连接基因组拼接中的重叠群，以提升这些基因组草图的质量。PacBio 的 SMRT 长读段已经证明在 解析长重复区域方面是有效的[6]，并且可能成为原核生物基因组测序的金标准。此外，SMRT 长读段 已被用于解决黑猩猩[7]和人类[8]的复杂基因组区域。但是第三代测序仪的比较高的错误率决定了它们 还不能完全取代第二代测序测序平台。对于许多组学问题研究，比如宏基因组学，第二代技术至少 在未来几年仍将是最先进的技术[9]。 尽管从头拼接算法取得了长足的进展，但短读段或长读段技术的固有问题仍然阻碍了完整的基 因组的构建。一方面，由于第二代测序数据误差小，组装第二代测序数据集可以产生准确的重叠群， 但由于它们读段尺寸太小而无法识别更大的基因组重复序列。另一方面，由于第三代测序数据的长 度优势，纯第三代测序数据装配算法（例如 HGAP[7]）可以轻松地解决较大的重复区域，但是为了 最小化错误率的影响以得到较高的准确率，需要巨大的测序深度。自第一个 SMRT 测序平台发布， 就出现了利用这两种测序方法的互补性产生各种组装混合数据集的想法以利用两者的混合拼接算法。 1 现有拼接算法  尽管测序手段不断升级，但无论是二代测序数据拼接还是二三代混合拼接，对测序数据进行拼 接的算法思路是整体一致的。由于基因组中绝大部分的区域是没有互相重复的，所以通过比对读段 上的碱基序列，找到他们的重叠区域（Overlap），然后通过将这些读段通过重叠区域连接起来以得 到更长的序列，即重叠群（Contig）。 由于拼接得到的重叠群数量通常远多于实际的染色体数量，因 此需要第二阶段的拼接骨架以将部分碎片拼接为更长的序列。拼接骨架（Scaffolding）是将重叠群按 照正确的顺序和方向进行集合并进行连接的过程，其中间可能存在一些没有具体测序数据间隙（Gap） 以 N（即未知碱基）进行填充，最终得到的序列被称为骨架（Scaffold）。 通过包括对特定的一些间隙进行填充（Gap fill）等方式，对拼接得到的进一步进行基因组后处理（Genome finishing）， 即可 以得到相应物种的基因组草图。 无论是将读段连接为重叠群，还是进一步的骨架拼接，都可以归纳为如下数学模型：在读段/重 叠群间重叠信息的约束条件下，确认所有读段/重叠群的顺序和方向。可以证明，确定所有读段/重叠 群的顺序等价于最优线性排列问题，这一问题是 NP 难的（ NP-hard）[10]。因此，寻求最优解在计 算复杂度上目前而言是不可行的，拼接算法需要寻求某种近似解，以在合理的时间和空间复杂度下 获得准确可以率接受的解。现有的拼接算法大体可以按以下分类： 1.1 贪心法  贪心法【11】是最早采用于基因拼接算法的方法（见图 1）。贪心法的策略是选取某一问题的初始 解，然后选择最小代价的步骤，转移到下一个逼近最终目标的解，如此反复以达到最终目标或者其 他终止条件。在基因组拼接问题中，贪心法的具体步骤如下：首先选取一个读段作为初始重叠群， 然后寻找与当前重叠群重叠区域相似度得分最高的读段，与当前重叠群进行拼接，得到新的重叠群， 直到没有读段与当前重叠群足够相似。思路简单、复杂度低是贪心法的主要优势，但该方法只能找 到局部最优解。如何从局部最优逼近全局最优是该方法面临的主要挑战。使用这一方法的软件有 SSPACE 等。    图 1 贪心法图解 Fig. 1 The greedy method 注：由于测序误差、不同区域间的重复序列等原因，贪心法可能选择错误读段扩展. 1.2 OLC 算法 OLC 算法（ Overlap-Layout-Consensus） [12]如其名字所示，主要可分为以下三个步骤：（1）Overlap： 对所有读段进行两两比对，找到读段间的重叠信息。但由于两两比对的复杂度太高，实际算法通常 先采取某种方式筛选可能比较相似的读段对，仅比较这些可能相似的读段，其余读段对相似度视为 0。 （2）Layout：根据得到的重叠信息将测序读段视为图上的点，读段间的相似关系视为连线，构建 OLC 图（见图 2）。 （3）Consensus：利用 OLC 图上的连接信息，找到遍历图上所有节点的最佳路径， 即寻找图上的哈密顿道路，这也导致该算法复杂度通常较高，通常用于读段较长、总读段数较少的 拼接。使用这一方法的软件有 Celera Assembler 等。    图 2 OLC 法图解 Fig. 2  An example of the OLC method 注：图中左侧为基因组上序列实际对应的位置，红色连接是因重复序列等原因产生的的重叠信息。右图为实际得到 的 OLC 图，OLC 算法需要排除错误的红色边，找到真实的读段间顺序，即图中黑色边构成的路径。