algorithm - 简洁与压缩 de Bruijn 图

Question

我不是该主题的专家，所以请在回答时考虑到这一点。

我正在阅读两篇论文
Succinct de Bruijn Graphs
和
Compacting de Bruijn graphs from sequencing data quickly and in low memory

我无法理解这两种方法之间的区别，所以任何人都可以帮助我理解这两种算法之间的区别吗？或建议进一步阅读以区分两者。

Succinct de Bruijn Graphs(作者用 python 编写了一个)或任何其他高效语言是否有 Java 实现

提前致谢。

Answer 1

压缩 de Bruijn 图与 de Bruijn 图是不同的对象。在后者中，所有节点都是 k-mers(长度为 k)，在前者中，节点是通过原始 de Bruijn 图的路径压缩创建的。因此，压缩图中的节点长度为 k 或更大。

路径压缩意味着，在这种情况下，内部节点具有一个内部邻居和一个外部邻居的每条最大长度路径都减少到一个节点。

虽然我说这两个图是不同的，但它们代表完全相同的信息(这是一组 k-mers)，因此我们经常非正式地将“de Bruijn 图”称为“de Bruijn 图”他们中的任何一个。

简洁表示(对于这些对象中的任何一个)是指使用很少内存的数据结构。

我不知道 sDBGs 的 Java 实现，但在 C++ 中有:https://github.com/cosmo-team/cosmo