Edge Minimization in de Bruijn Graphs
Edge Minimization in de Bruijn Graphs
复制标题
de Bruijn 图中的边最小化
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pascal Weber
中科院分区：
文献类型：
--
作者：
Uwe Baier;Thomas Büchler;Enno Ohlebusch;Pascal Weber
介绍了de Bruijn图边最小化问题，它与de Bruijn图的压缩有关：在所有阶数中找出边数最少的k阶de Bruijn图。我们描述了一个有效的算法，解决了这个问题。由于边缘最小化问题是连接到BWT压缩技术称为“隧道”，本文还描述了一种方法，以尽量减少隧道BWT的长度，这样的方式，有用的属性序列分析被保留。虽然这是一个限制，但这是朝着找到最小化空间的最佳不相交块的开放问题的解决方案的重大进展，如Alanko等人所述。
This paper introduces the de Bruijn graph edge minimization problem, which is related to the compression of de Bruijn graphs: find the order-k de Bruijn graph with minimum edge count among all orders. We describe an efficient algorithm that solves this problem. Since the edge minimization problem is connected to the BWT compression technique called "tunneling", the paper also describes a way to minimize the length of a tunneled BWT in such a way that useful properties for sequence analysis are preserved. Although being a restriction, this is significant progress towards a solution to the open problem of finding optimal disjoint blocks that minimize space, as stated in Alanko et al. (DCC 2019).
影响因子：
5.8
作者：
Baier, Uwe;Beller, Timo;Ohlebusch, Enno
通讯作者：
Ohlebusch, Enno