论文标题
De Bruijn图和Wheeler图的空间有效合并
Space efficient merging of de Bruijn graphs and Wheeler graphs
论文作者
论文摘要
简洁数据结构的合并是一种良好的技术，用于有效地构建大型简洁索引。在本文的第一部分中，我们提出了一种新算法，用于合并De Bruijn图的简洁表示。对于同一问题，我们的算法具有相同的最先进算法的渐近成本，但它使用了其不到一半的工作空间。我们算法的一个新颖的重要特征，在任何现有工具中都找不到，它可以计算在相同的渐近时间/空间范围内的联合图的可变顺序简洁表示。在本文的第二部分中，我们考虑了合并Wheeler图的简洁表示的更一般的问题，Wheeler Graph是最近引入的图形家族，其中包括特殊情况De Bruijn图和许多其他基于BWT或其变体之一的已知简洁索引。我们表明，惠勒图合并通常是一个更加困难的问题，并且为确定联合图是否具有满足惠勒条件的订单是否有序的问题，我们为稍微简化的问题提供了一种效率的空间算法。
The merging of succinct data structures is a well established technique for the space efficient construction of large succinct indexes. In the first part of the paper we propose a new algorithm for merging succinct representations of de Bruijn graphs. Our algorithm has the same asymptotic cost of the state of the art algorithm for the same problem but it uses less than half of its working space. A novel important feature of our algorithm, not found in any of the existing tools, is that it can compute the Variable Order succinct representation of the union graph within the same asymptotic time/space bounds. In the second part of the paper we consider the more general problem of merging succinct representations of Wheeler graphs, a recently introduced graph family which includes as special cases de Bruijn graphs and many other known succinct indexes based on the BWT or one of its variants. We show that Wheeler graphs merging is in general a much more difficult problem, and we provide a space efficient algorithm for the slightly simplified problem of determining whether the union graph has an ordering that satisfies the Wheeler conditions.
