基于满足性判定的布尔网络环求解算法

摘要：

环是布尔网络状态转换过程中的稳定态，在模式检测、基因调控网络和可达性分析等领域都有重要的意义。计算布尔网络状态转换中的所有环是一个NP完全问题。该文基于全解布尔满足性判定(SAT)算法，设计了一种求解所有小于等于指定步长环的算法。算法基于布尔网络的状态转换函数和状态环属性生成合取范式形式(CNF)的问题集，通过融合冲突子句学习(CDCL)、非时序回退、阻塞子句和变量分类等技术，降低算法的计算复杂度。实验结果表明，该算法能够高效地计算指定步长的环。对于无法计算所有环的复杂网络，指定步长计算环的方式将更有应用价值。

关键词：布尔网络、环、满足性判定、阻塞子句

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61272175

在线出版日期：2015-12-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：881-886