在圖論中，m個符號的n維德布魯因圖是表示符號序列之間重疊的有向圖。它有mn個頂點，由給定符號
De Bruijn graph是一個展示符號序列之間重疊關系的有方向的示意圖斗这。
為什么這里要講這個德布魯因圖塘雳？
因為基因組組裝的組裝工具主要分為三類：基于貪婪算法的拼接方法，基于讀序之間的重疊序列(overlapped sequence)進行拼接的OLC(Overlap-Layout-Consensus)拼接方法和基于德布魯因圖(de bruijn graph)的方法经瓷，這三種方法或多或少基于圖論翠储。第一種是最早期的方法绘雁，目前已被淘汰，第二種適用于一代測序產(chǎn)生長片段序列援所，可以稱之為字符串圖(string graph),第三種是目前二代測序組裝基因組的工具的核心基礎庐舟，也就是de bruijn圖。
de bruijn圖由兩部分組成住拭，節(jié)點(Nodes)和邊(Edges)挪略，節(jié)點由k-mers組成，節(jié)點之間要想形成邊就需要是兩個k-mers存在K-1個完全匹配滔岳。比如說杠娱，ACTG, CTGC, TGCC在K=3時的k-mers為ACT,CTG,TGC,GCC，可以表示為ACT -> CTG -> TGC -> GC.
對于de brujin圖而言谱煤，冗余序列不會影響k-mers的數(shù)量摊求，比如說ACTG,ACTG,CTGC,CTGC,CTGC,TGCC,TGCC在K=3時依舊表示為ACT -> CTG -> TGC -> GCC。
那Kmer為什么是奇數(shù)趴俘？
根本原因是為了避免正反義鏈混淆睹簇。
目前的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為什么必須是奇數(shù)朴下？ - 知乎 (zhihu.com)
純二代測序從頭組裝基因組 - 簡書 (jianshu.com)
