何时使用 de Bruijn 图进行字符串重建是困难的？

《ACM Transactions on Algorithms》：When is String Reconstruction using de Bruijn Graphs Hard?

　　

摘要

将片段组装问题归结为（经典欧拉径问题的）变体[2001年Pevzner等人，PNAS]，为基因组组装带来了显著进展。这一归结方法采用了字母表Σ上k阶de Bruijn图G=(V,E)的概念。G中的一条欧拉径代表一个候选基因组重构方案。Bernardini等人还提出了基于z-匿名性的互补性想法[2020年ALENEX]用于数据隐私保护。设S为一条我们想要发布的私有字符串，但需阻止其完整重构。对于隐私阈值z>0，我们计算S的k阶de Bruijn图中至少存在z条欧拉径的最大k值，并通过随机欧拉径发布所得到的字符串S′。

关键问题是：给定一个建模领域知识的函数，从de Bruijn图中重构最优字符串有多难？一种自然模型使用一个函数，将该函数将每个长度为k的字符串映射为其在重构字符串中可能出现的区间。根据上述向de Bruijn图的归结方法，后者转化为一个函数c，该函数将每条边映射为其在欧拉径中可能出现的区间。这由此引出了图上的以下基本问题：给定实例(G,c)，我们能否高效地计算一条满足c的欧拉径？

Hannenhalli等人[1996年CABIOS]形式化了这一问题，并证明其为NP完全问题。Ben-Dor等人[2002年《计算生物学杂志》]证明即使在|Σ|=4的de Bruijn图上，该问题也是NP完全的。在本工作中，我们从下界方向解决了该问题，证明在字母表大小为2的de Bruijn图上寻找满足c的欧拉径是NP完全的。

随后，我们将注意力转向参数化方法，旨在捕捉领域知识质量在复杂性中的影响。Ben-Dor等人开发了一种算法，在de Bruijn图上以O(m·w^1.54w)时间求解该问题，其中m=|E|，w是E中所有边的最大区间长度。Bumpus和Meeks[2023年Algorithmica]后来在时间图上重新发现了同样的算法，这凸显了该问题在其他语境中的重要性。我们的核心贡献是展示组合学洞察如何带来超越现有最优算法的指数级时间改进。特别地，对于重要的de Bruijn图类别，我们开发了一种以w(log w+1)/(k?1)为参数的算法：对于k阶de Bruijn图，其运行时间为O(mw·2^(w log(w+1)/(k?1)))。我们的结果比现有最优算法改善了大约(log w+1)/(k?1)个指数。现有算法对字符串重构有自然的解释：当对于每个长度为k的字符串，我们已知其必须位于一个小范围的位置时，字符串重构可以在线性时间内求解。我们改进的算法表明，当位置范围相对于k较小时就足够了。

随后，我们通过允许每个区间每个位置的代价变化，对现有算法和我们的新FTP算法进行了推广。在这一优化版本中，我们的硬度结果转化为不可近似性，而FTP算法可以通过轻微扩展来运行。令人惊讶的是，即使在这一更一般的设定中，我们将FTP算法扩展到计数和枚举最小代价欧拉径。计数结果在Bernardini等人的数据隐私框架中有直接应用。

AI摘要

AI生成摘要（实验性）

本摘要由自动化工具生成，未由文章作者撰写或审阅。其目的在于支持发现、帮助读者评估相关性，并协助相邻研究领域的读者理解本工作。它旨在补充作者提供的摘要，后者仍为论文的主要摘要。全文仍为权威记录版本。点击此处了解更多信息。点击此处对该摘要的准确性、清晰度和实用性发表评论。这样做将有助于改进和未来的重新生成版本。如需查看此AI生成的通俗摘要，您必须拥有高级访问权限。