GTCA CAGG
依靠以上例子，我们可以将这些K-mer建立成一个deBruijn图，每一个k-mer是图中的一个点，如果两个k-mer中有k-1个核苦酸的重叠区域,就给这两个点之间连一条边。
依照以上方法，我们就可以将基因组拼接问题模型化处理，就可以将哈密尔顿问题转换为在deBruijn图中寻找的欧拉路问题。而欧拉路问题，就是一条访问图中每一条边一次并且仅访问一次的路。由于哈密尔顿问题与欧拉路的建模方法有所差异，所以对于基因的拼接问题就从一个寻找哈密尔顿路问题转化为寻找欧拉路问题，这样，求解难度就在原有的基础上下降了不少。 在过去的几十年内，对于基因组拼接算法我们已经开发出诸多算法，通过总结，我们可以将这些算法分为如下三种类型：第一，贪婪方法；第二，“重叠～排列～共有序列”方法；第三，则为图方法，针对这三种方法，我们将在下节一一介绍。
2.1.1贪婪方法
在研究基因组拼接的初期，对于基因组拼接，学者们的处理方法都是借助贪婪方法来进行基因组拼接的，且许多拼接工具都是利用这一理论思想。 在基因组拼接中，贪婪拼接方法的基本思路主要是：在测序时，将具有重叠区域的测序序列进行一定的延长，且每一次延
16
长，我们都要选择与当前序列的一端较长的重叠区域并且此重叠区域的相似度尽可能高的一条序列，然后再通过合并这两个重叠区域相似度极高的序列去延长当前序列，从而达到基因组拼接的效果。 以上我们简单地介绍了贪婪方法的基本思路，接下来，我们将重点介绍贪婪方法的步骤，对于贪婪方法的步骤，具体总结如下： 第一.计算出基因中测序片段的所有两两联配(alignment); 第二.在测序片段中，获得两个具有最大的重叠区域的序列； 第三.合并这两个重叠区域最大序列，使之成为一个新的序列； 第四.重复步骤二和三，直到剩下的所有序列小于某一个数值或者没有重叠区域。从步骤上看，我们已然知晓，序列的两两联配是贪婪算法的重要支持点，也是生物信息学研究的基本问题之一。
2.1.2重叠-排列-共有序列的方法
在测序中，重叠排列共有序列的方法是第一代测序数据的拼接中最为常用的方法，同时也是最成功的算法之一。在测序中，很多拼接工具都利用重叠排列共有序列方法，由此可见，重叠排列共有序列方法在测序中具有较高的实用性，因此，我们有必要对此方法进行一定的介绍，据总结，重叠排序共有序列方法的步骤如下：
第一.计算重叠区域。在测序拼接中，首先要计算出所有测序片段两两之间的重叠区域，计算重叠区域的意义是为了构造出一个重叠图，而重叠图中的每一个点都代表着一个测序片段，当两个测序片段
17
之间具有重叠区域时，则给他们之间连一条边。
第二.图排列阶段。重叠图构造成功后，我们便在重叠图中寻找一些能够代表原始DNA序列的路。在理想情况下，在重叠图中，我们都希望获得一条相对完整的基因组序列，这样我们便可以从重叠图寻找到一个哈密尔顿路。
第三.确定共有序列。所谓确定共有序列，其实质就是确定一个序列，使该确定序列包含步骤二中的每一条序列，也就是说，该共有序列是步骤二中所有序列的子序列。
从效果上分析，贪婪方法的效果要次于重叠排列共有序列的方法，这也是重叠排序共有序列方法为什么能在第一代测序片段拼接中受欢迎的原因之一。虽然重叠排序共有序列具有高效性，不过与贪婪方法一样，重叠排序共有序列方法要计算测序片段两两之间的联配，而测序片段之间的联配的计算量十分浩大，故此，在第二代测序的拼接中，此方法的应用相对于第一代测序拼接要少得多。
2.1.3 De Bruijn 图方法
在二十一世纪初期，Pavel与Pevzner等人通过相关的研究探讨，最终提出了一个新的基因组拼接方法，这个拼接方法与贪婪方法和重叠排序共有序列方法并不相同，因为此方法并不直接利用测序序列，而只是通过一定的手段，将基因中的测序片段打碎，使之成为具有重叠区域的一系列长短序列，而打碎的短序列都具有相同的长度，且长
18
度都为A个核苷酸，在此，我们都称之为tmer。且每一个测序片段都依次被人为打碎，从而成为相互之间都具有k-l个核苦酸的重叠A:mer。
因此，我们可以利用测序数据中所包含的的A:mer,然后去构造出一个deBruijn图，在此图中，对于每一个tmer，我们都可以将其看成是一个点，而两个tmer之间如果正巧有h个核苷酸重叠区域，那么这两个tmer之间就可以连一条边。正因为两个tmer之间如果有h个核苷酸重复区域可以连一条边，那么在测序过程中，就可以避免一些测序错误，构造出来的图与直接用测序片段构造的图有异曲同工之妙。在deBrujin图中，基因组所对应的一条能通过所有边的路，在生物学上，我们都称其为欧拉路。
这样，就可以将基因组的拼接问题摇身一变，使其转化为在deBrujin图上寻找到一个欧拉路的问题，而在图中寻找欧拉路，我们可以利用多项式的解法去处理该问题。
在基因拼接过程中，基于图方法的设计，并不是针对于第二代测序的拼接，从实际意义上研究，deBrujin方法出现的时间要早于第二代测序，在其出现之前，此方法就己经存在了。不过，由于该算法中deBruijn图的规模与基因测序数据的规模没有一点联系，这两者之间仅仅只跟基因组的大小有关联，故此，该方法特别适用于像第二代测序技术的高通量数据拼接中，这也是为什么该方法在第二代测序的拼接中得到了广泛应用的最佳解释。重叠排序共有序列方法之所以在第一代测序中取得不菲的成绩，其主要因素在于它所构造的图的规模跟
19
测序片段的数量多少有一定的关联性，而拥有高通量数据的第二代测序技术，也正因为其数据量相对较大，导致图的规模较，最终出现无法求解的尴尬现象。
然而正因为份图这一优点，导致基因拼接过程比重叠排共有序列方法高效，所以在后来的研究中，基于第二代测序的基因组拼接算法，人们都差不多采用deBrujin这一方法。
以上阐述的观点基本上适用于理想状态，而在实际的拼接过程中，我们最终所获得基因组序列并不是一条十分完整的基因组序列，受到其他因素的影响，在基因拼接中，我们所获得的序列是几条或者几十条、以至于更多条且序列与序列之间没有重叠区域的一些DNA序列。故此，要想获得完整的基因组序列，还需要借助一些方法或者手段对这些序列进行进一步加工处理，这样才能充分利用基因双端的测序信息，求解出序列的方向与序列与序列间的对应位置。除此之外，我们还可以通过一些实验去填补基因组中的缺陷，最终解决问题获得一条较为完整的基因组序列。
2.2基于参考基因组的转录组拼接算法
在对绝缘拼接的过程中，基于参考基因组的拼接，主要涉及如下三个步骤：第一步，RNA-seq的数据被映射到参考基因组上。在此过程中，我们利用的映射工具主要有以下几大类：其中包括TopHat , SpIiceMap，MapSplice以及GSNAP等，这些映射工具对剪接具有一定
20