de Bruijn graph（德布鲁因图）：一种用来表示字符串片段之间重叠关系的图结构，常用于计算机科学与生物信息学（尤其是基因组组装）。典型构造方式是：把长度为 k-1 的子串作为节点，把长度为 k 的子串（或相邻重叠关系）作为有向边，从而把“重叠拼接”问题转化为寻找欧拉路径/回路等图问题。
/di brun rf/
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（德布鲁因序列）/strong> 密切相关；后来这一思想被广泛用于字符串处理与生物序列拼接，因此形成了术语 de Bruijn graph。
Select Language