德布鲁因图 (De Bruijn graph)
在图论中，m个符号的n维德布鲁因图是表示符号序列之间重叠的有向图。它有mn个顶点，由给定符号
De Bruijn graph是一个展示符号序列之间重叠关系的有方向的示意图。
image.png
为什么这里要讲这个德布鲁因图？
因为基因组组装的组装工具主要分为三类：基于贪婪算法的拼接方法，基于读序之间的重叠序列(overlapped sequence)进行拼接的OLC(Overlap-Layout-Consensus)拼接方法和基于德布鲁因图(de bruijn graph)的方法，这三种方法或多或少基于图论。第一种是最早期的方法，目前已被淘汰，第二种适用于一代测序产生长片段序列，可以称之为字符串图(string graph),第三种是目前二代测序组装基因组的工具的核心基础，也就是de bruijn图。
de bruijn图由两部分组成，节点(Nodes)和边(Edges)，节点由k-mers组成，节点之间要想形成边就需要是两个k-mers存在K-1个完全匹配。比如说，ACTG, CTGC, TGCC在K=3时的k-mers为ACT,CTG,TGC,GCC，可以表示为ACT -> CTG -> TGC -> GC.
对于de brujin图而言，冗余序列不会影响k-mers的数量，比如说ACTG,ACTG,CTGC,CTGC,CTGC,TGCC,TGCC在K=3时依旧表示为ACT -> CTG -> TGC -> GCC。
image.png
那Kmer为什么是奇数？
根本原因是为了避免正反义链混淆。
目前的NGS测序技术也做不到通测基因组。一般来说都是测出上百万千万亿万个小小的片段（read，长度一般是100bp-300bp）。而且，为了确保准确性，基因组都会被反复测很多层。组装时构建的kmer单位，实际上是对这些read进行的。具体的操作就是按照kmer的长度把这些read切割成更小的、存在重叠关系的片段。那么，此刻当我们构建de Bruijn graph时，如何能够保证正确地把同属于一条read上的Kmer连接起来，就显得极为重要了！我们不能一会儿把A kmer正确地连到它自己所在的read，一会儿又连到它互补链的read上去！
[算法学习 1] 基因组组装算法 De Bruijn Graph - 知乎 (zhihu.com)
De Bruijn graph - Wikipedia
利用de Bruijn graph组装基因组的时候，Kmer为什么必须是奇数？ - 知乎 (zhihu.com)
纯二代测序从头组装基因组 - 简书 (jianshu.com)
