本文介绍一下 De Bruijn 图在基因组组装中的原理和应用，依据：
https://www.cs.jhu.edu/~langmea/resources/lecture_notes/17_assembly_dbg_v2.pdf
首先，先直观的看一下用怎样代表文字序列，假设，我们有下面一句话：
“tomorrow and tomorrow and tomorrow”。
那么，如果我们用图来表示的话就是：
image.png
- 上图中的箭头表示边，是有方向的，方向就是阅读文字的方向。
- 因为我们的文字中有有重复出现的单词，所以边呈现出环状。
- 如果节点上有多个边，则为multigraph。
De Bruijn Graph
假设基因组有以下序列：AAABBBBA
把它用3k-mer隔开表示为：AAA, AAB, ABB, BBB, BBB, BBA
每个3k-mer又可以分为左和右两个2 k-mer：AA,AA AA,AB AB,BB BB,BB BB,BB BB,BA
总结为下图
用De Bruijn图表示，为
- 每个边表示一个 3k-mer
- 每个节点表示为 一个2k-mer
在上图中，如果我们能够发现一条路径，经过每个边一次且仅一次，这个路径表示出来就是原始序列。
就上图而言，是这样：
这条路径被称为欧拉路径（Eulerian Walk）
这一节先到这里，关于De Bruijn图的更深入的内容，后面再聊。
