迈向自然基因组重排小简约问题统一精确解法

系统发育重建是比较基因组学中的一个基本问题。作为重排研究中的一个理论问题，它被建模为小简约性问题（Small Parsimony Problem, SPP），其中需要确定祖先基因组结构，同时使整个系统发育过程中发生的重排事件数最小。由于重排事件的普遍存在及其临床重要性，这一问题在微生物基因组学和癌症基因组学中具有重要意义。该问题中的基因组结构被表示为标记序列，而标记本身是具有方向性的序列特征（如基因），用于对非结构变异进行抽象。近期研究聚焦于自然基因组模型下的问题，在该模型中允许标记拷贝数发生任意变化。自然基因组通常在DCJ-indel模型下进行研究，该模型已经成功应用于质粒数据。对于DCJ-indel模型下小简约性问题的一个变体，也已有整数线性规划（ILP）解法。 然而，这些解法在适用性方面存在局限，因为出于可处理性的考虑，它们做出了一些关键性简化：将祖先标记频率以及预先计算得到的候选祖先邻接关系及其预测似然作为输入。这从理论和实践两个角度都带来了多重问题。首先，这种简化意味着并未在完整状态空间中搜索解，而只是搜索由预先计算的候选邻接关系所限定的基因组子集，因此无法保证得到精确SPP的最优解。其次，标记频率由外部给定，缺乏理论保证。第三，用于预先计算邻接关系的方法依赖于基因树，这要求以基因为标记，而基因注释往往并不可靠，尤其是在重排频繁的区域。此外，这还将该方法的适用范围限制在那些既具有足够分化程度、又具有足够规模以产生信息丰富的基因树的基因组集合上。例如，对于质粒而言，这种情况很少出现，因为其核苷酸突变比重排更为罕见，且基因组规模较小。 因此，我们重新审视这一问题，通过为插入缺失操作引入代价来求解精确SPP。这使我们能够计算标记频率的取值范围，并推导出一系列理论结果，从而在不牺牲最优性的前提下缩减ILP所需搜索的解空间。我们表明，这使得该问题在小型且近期分化的基因组情形下变得可处理。我们首先在模拟基因组上验证了这一点，随后又在一组致病性质粒上进行了测试，这些质粒代表了该方法一个现实的应用场景。

1 德国比勒费尔德大学技术学院与生物技术中心（CeBiTec）； 在 Google Scholar 上查找该作者 在 PubMed 上查找该作者 在持有人为作者/资助方，其已授予 bioRxiv 永久展示该预印本的许可。 本作品依据 CC-BY 4.0 国际许可协议 提供。

返回顶部 上一页 下一页

发布于 2026 年 6 月 28 日。 下载 PDF 补充材料 电子邮件

感谢您有兴趣帮助传播 bioRxiv。 您的电子邮件 *

您的姓名 *

发送至 * 请输入多个地址，每行一个，或以逗号分隔。

您将发送以下内容的电子邮件： 面向天然基因组重排简约性问题统一精确解法的研究

邮件主题 （您的姓名）已从 bioRxiv 转发了一个页面给您

邮件正文 （您的姓名）认为您可能希望查看 bioRxiv 网站上的此页面。

您的个人留言

验证码 此问题用于测试您是否为人类访客，并防止自动化垃圾信息提交。

分享 面向天然基因组重排简约性问题统一精确解法的研究

Leonard Bohnenkaemper， Daria Frolova

bioRxiv 2026.06.23.733974； doi： https://doi.org/10.64898/2026.06.23.733974

分享本文： 复制

引文工具 面向天然基因组重排简约性问题统一精确解法的研究

Leonard Bohnenkaemper， Daria Frolova

bioRxiv 2026.06.23.733974； doi： https://doi.org/10.64898/2026.06.23.733974

📄 原文链接：https://www.biorxiv.org/content/10.64898/2026.06.23.733974v1?rss=1

🏷️ 比较基因组学 基因组重排 小简约问题 整数线性规划 DCJ-indel模型 系统发育重建