de Bruijn graph（德布鲁因图）：一种用来表示字符串片段之间重叠关系的图结构，常用于计算机科学与生物信息学（尤其是基因组组装）。典型构造方式是：把长度为 k-1 的子串作为节点，把长度为 k 的子串（或相邻重叠关系）作为有向边，从而把“重叠拼接”问题转化为寻找欧拉路径/回路等图问题。
/diː ˈbruːɪn ɡræf/
We built a de Bruijn graph from the sequencing reads.
我们用测序读段构建了一个德布鲁因图。
By compressing non-branching paths in the de Bruijn graph, the assembler can produce longer contigs even with noisy data.
通过压缩德布鲁因图中不分叉的路径，组装器即使在噪声较大的数据下也能生成更长的 contig（连续序列片段）。
“de Bruijn”来自荷兰数学家 Nicolaas Govert de Bruijn（尼古拉斯·戈弗特·德布鲁因） 的姓氏。该类图结构与他在组合数学中研究的 de Bruijn sequence（德布鲁因序列） 密切相关；后来这一思想被广泛用于字符串处理与生物序列拼接，因此形成了术语 de Bruijn graph。
Select Language