基因组组装策略（上）——基于二代测序结果的De Bruijn图方法

基因组组装是生物信息学的核心问题，具有重要的应用价值。基于需组装的原始数据的来源，可以将基因组的组装分为基于一代sanger测序的基因组装和基于二代测序的基因组装。常规的基因组组装软件可以根据得到的reads读长将所有的reads组装成完整的基因组，其核心为组装算法。

目前常用的组装算法包括：基于Overlap/Layout/Consensus的OLC方法，贪婪图方法，deBruijn图方法等。 

传统的sanger测序数据进行基因组装通常基于OLC方法进行。OLC方法首先通过动态规划算法对所有的reads进行相互比对，并根据比对结果绘制哈密顿图（Hamilton），然后在此图中寻找合适的通路，从而将短的序列组装成contig（如图1所示）。

图1 基于哈密顿图的OLC方法进行基因组装

二代测序具有读长短、重复率高、overlap高的的特点，导致了直接使用OLC法进行组装会消耗大量的内存且运行速度很慢（时间复杂度为n^2，n为reads个数），且高度overlap容易导致跳过片段间隔。对于大规模基因组测序产生的以亿计的序列reads，采用OLC方法进行组装几乎是不可能的。 

目前，对二代测序reads的组装通常采用的是基于De Bruijn图和欧拉路径的序列组装模型。该方法将reads分割为更短的k-mer，当k-mer较小时，出错的概率也会随之降低。该方法的步骤如下：

1. 将reads切分成长度为k的子串，称之为k-mers。

2. 如果存在reads使两个k-mers相邻且存在k-1个字符重合，则可以在二者间画出一条有向边，从而将两条reads的关系映射到了图上。

3. 重复以上步骤，得到最终的De Bruijn图，从而将reads组装成基因组的问题转化成在De Bruijn图中寻找一条包含了所有reads的路径问题。

图2 de Bruijn Graph算法的示意图(图片来源：Ayling et al. Briefings in Bioinformatics, 2019)

要求解该问题，等价于寻找一条没有分支的路径，使之通过的有向边尽可能多。基于图论中的欧拉路径思想，可以使用Fluery算法和Hierholzer算法求得最终的解集。

这里以Hierholzer算法为例，简单介绍其工作原理：

（1）判断奇点数。奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。

（2）开始递归函数Hierholzer(x):循环寻找与x相连的边(x,u)，删除(x,u)，删除(u,x)，递归执行Hierholzer(u);并将x插入答案队列之中。

（3）倒序输出答案队列。

图3 Hierholzer算法求解De Bruijn图最大有向路径原理

De Bruijn图用于二代测序基因组组装不再以read为单位组织数据，而是以k-mer为单位进行精确组装，可以更好地处理二代测序较高的测序错误率，实现精确的拼接，其优点如下：

1. 降低了算法的时间复杂度与空间复杂度，节约内存资源，加快组装速度。

2. 以k-mer代替reads不影响图中的点个数与质量，并降低了duplication reads的影响。

3. 存在overlap的reads会唯一同一条有向边上，在遍历图搜索时降低了时间复杂度。