保持可达性的最小割边问题及其在生物学中的应用

生物通路分析通常需要识别能够阻断到达某种不良状态的干预措施，例如与疾病相关的模块、有毒副产物或不利表型，同时保留关键生物功能之间的可达性。受这一背景驱动，我们研究可达性保持的最小割边问题（Reachability Preserving Minimum Edge Cut, RPMEC）：给定受保护终端点 (s_1) 和 (s_2) 以及目标终端点 (t)，其目标是在保持 (s_1) 与 (s_2) 连通的同时，移除一个总成本最小的边集，使得 (s_1) 和 (s_2) 与 (t) 分离。该形式化定义自然地刻画了通路层面的干预设计问题，即在不破坏所需功能连通性的前提下，破坏有害的信号传导、代谢或相互作用路径。 我们重新考察了三终端无向割边情形，并分析了一种类似 Dijkstra 的动态规划算法：该算法在平面图上是精确的，但在一般图上会失效。我们刻画了保证其精确性所需的结构条件，即最优源侧区域的前沿可实现性（frontier-realizability），并识别出若经过适当预处理后该条件很可能成立的生物图表示，包括人工整理的平面通路图、Reactome 风格的层次树、经 SCC 缩约的反馈模块、具有支配子结构的代谢构件 DAG，以及蛋白质相互作用网络的功能模块商图。我们还进一步讨论了有向变体、近似策略，以及基于 ASP、MILP、有界树宽动态规划和重要分离子的精确替代方法。上述结果为判定在生物通路干预问题中何时快速贪心计算是可靠的、何时需要更具表达能力的精确优化方法，提供了图论基础。

qiduan{at}gmail.com

摘要

信息/历史

指标

预览 PDF

摘要

生物通路分析通常需要识别能够阻断通向某种不良状态的可达性的干预措施，例如与疾病相关的模块、有毒副产物或不良表型，同时保留基持有人为作者/资助方，其已授予 bioRxiv 永久展示该预印本的许可。

本文依据 CC-BY 4.0 国际许可协议 公开提供。

查看讨论主题。

返回顶部

上一页

下一页

发布于 2026 年 6 月 3 日。

下载 PDF

电子邮件

感谢您有兴趣帮助传播 bioRxiv 的内容。

您的电子邮件

*

您的姓名

*

发送至

*

请输入多个地址，每行一个，或用逗号分隔。

您将通过电子邮件发送以下内容

可达性保持最小割边问题及其在生物学中的应用

邮件主题

（您的姓名）已从 bioRxiv 向您转发了一个页面

邮件正文

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

您的个人留言

验证码

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

分享

可达性保持最小割边问题及其在生物学中的应用

Jing Xie，

Qi Duan

bioRxiv

2026.06.01.729192；

doi：

https://doi.org/10.64898/2026.06.01.729192

分享本文：

复制

引文工具

可达性保持最小割边问题及其在生物学中的应用

Jing Xie，

Qi Duan

bioRxiv

2026.06.01.729192；

doi：

https://doi.org/10.64898/2026.06.01.729192

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

🏷️ 生物通路分析 图论算法 最小割边 网络干预设计 动态规划