1. 欧拉路径 Euler Path

(1) 欧拉路径的定义

一张图由顶点 (vertex) 和边 (edge) 构成。对于每个顶点，其连接的边的数目称为这个顶点的度 (degree)。

对于一个图$\textbf{G}$，如果一条路径经过这个图中所有的边，且恰好经过一次，则这条路径就是图$\textbf{G}$中的一个欧拉路径 (Euler Path)。有欧拉路径的图可以进行 “一笔画” 把所有的边画完而且没有重复。

根据路径的起点与终点是否是同一个节点，欧拉路径可以细分为：

欧拉回路 (closed Euler path)：起点与终点相同的欧拉路径
欧拉开路 (open Euler path)：起点与终点不同的欧拉路径

(2) 欧拉路径的存在条件

对于无向图，有：

对于欧拉回路的情况，一个无向图存在欧拉回路当且仅当这个图是连通图 (connected)，并且每个顶点的度均是偶数。
对于欧拉开路的情况，一个无向图存在欧拉开路当且仅当这个图是连通图，并且有且只有两个顶点的度是奇数。

必要性证明：假设路径经过顶点$A$，那么会有一条路径进入$A$，也会有一条路径离开$A$，于是$A$的度数一定会是偶数。对于欧拉回路，起点与终点相同，因此起点的度数也是偶数；对于欧拉开路，起点与终点不同，两点的度数是奇数。

充分性证明：以欧拉回路为例，假设所有顶点的度数都是偶数。选取一个起点$A_1$，从$A_1$出发每经过一个顶点$A_i$，由于$A_i$的度数是偶数，所以必然也会从$A_i$再出发，而最终回到$A_1$。于是得到一个回路$A_1 \cdots A_i \cdots A_1$（如下图黑色的回路）。如果这条回路没有包括所有的边，那么除去这条回路和这条回路上的顶点，剩余顶点的度依然都是偶数。可以继续找到另一条回路，并且因为图是联通的，可以从$A_1 \cdots A_i \cdots A_1$之中的一个顶点出发，作为下一条回路的起点（如下图蓝色的回路）。以此类推，因为总的顶点数和边数是有限的，总可以结束这个过程。最终这些回路可以连接成为一条回路，这就证明了欧拉回路的存在。

对于有向图，有

对于欧拉回路的情况，一个有向图存在欧拉回路当且仅当这个图是连通图，并且每个顶点的入度 (in degree) 等于出度 (out degree)。
对于欧拉开路的情况，一个有向图存在欧拉开路当且仅当这个图是连通图，并且有且只有两个顶点的入度不等于出度。对于这两个特殊的顶点，其中一个顶点的入度比出度大 1，这个点是欧拉开路的终点；另一个顶点的入度比出度小 1，这个点是欧拉开路的起点。

2. de Bruijn图

(1) de Bruijn序列

如果有一个字典$\Sigma$，其元素个数是$\alpha$，那么其上的一个 de Bruijn序列 $S$是一个长度为$\alpha^n$的循环序列，$S$包含所有$\Sigma$上长度为$n$的子序列。

例如$\Sigma = \{0, \, 1 \}, \, \alpha = 2$，如果$n=3$，那么一个 de Bruijn序列可以是 $S = 00011101$。其长度为$\alpha^n = 2^3 = 8$。可以验证，$S$包含了所有的长度为$3$的子序列（$000 , 001 , 010 , 011 , 100 , 101 , 110 , 111$）。

(2) de Bruijn图

用来生产de Bruijn序列的有向图称为 de Bruijn有向图 (de Bruijn digraph)。比如用来生成上一节包含所有长度为 $3$ 的二进制子序列的 de Bruijn序列的有向图如下，有向图的每一个顶点都是一个长度为$n-1$的二进制的序列，并且每条有向边用 $0$ 或 $1$ 标注。顶点 $A$ 指向顶点 $B$的条件是，把顶点$A$ 代表的二进制序列的第一个比特 (bit) 去掉，然后在剩余的序列后面加上一个新的比特($0$ 或 $1$)，等于顶点$B$所代表的二进制序列。

图中每一个顶点$x_1x_2$会有两条向外的边($0$ 或 $1$)，同样也会有两个顶点($0x_1,1x_1$)指向该顶点。所以每一个顶点的入度和出度是相等的。这个 de Bruijn有向图一定存在欧拉回路。把图中的每条有向边上的标注($0$ 或 $1$)按照一条欧拉回路依次连接，就能得到一个 de Bruijn序列。

对于更多元素的 de Bruijn序列，也可以构造相应的 de Bruijn有向图来求解。比如求二进制的 $n = 4$的 de Bruijn序列，可以先构造长度为 $3$ 的全部子序列，然后建立 de Bruijn有向图。

对于一般的情况，如果要构造一个包含所有长度为 $n$ 的二进制子序列的 de Bruijn序列，其长度至少应该是 $2 ^ n2$。构造方法需要从顶点为所有 $n - 1$ 长度的二进制子序列构成的图中构造欧拉回路。由于每个$n - 1$长度的子序列会有两条向外的边 ($0$ 或 $1$)，所以 de Bruijn有向图中一共有$2^{n - 1} \times 2 = 2^n$条边，欧拉回路的长度就是$2^n$，符合其长度的最小的要求；欧拉回路又包含了所有的长度为 $n$ 的子序列。所以这样构造的 de Bruijn序列就是满足包含所有长度为 $n$ 的子序列中长度最短的序列。

3. de Bruijn图在基因组学的应用

在基因测序中所得数据的总长度将比基因组本身长得多，比如30亿bp基因组的总测序长度可能达到300亿bp，所以需要合适的算法将这些测序短序列read拼接起来。二代测序数据拼接常选择基于de Bruijn图的方法。

这类方法通过将测序序列打断成更小的长度为$k$的小片段（k-mer）来降低计算的规模。对于一条长度为$N$的序列，从头到尾依次取k-mer，一共可以取到$N-k+1$个k-mer，每两个相邻的k-mer之间都有长度为$k-1$的重叠区域。通过读取构造的de Bruijn图可以获得完整的基因序列。

通过将序列打断为k-mer，de Bruijn图方法降低了大量短序列数据集中的数据冗余性，降低了整体数据量和计算量，也避免了一些错误的拼接结果。