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

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

郭文生, 杨国武, 李晓瑜, 高敏

文章导航 > 电子科技大学学报 > 2015 > 44(6): 881-886

郭文生, 杨国武, 李晓瑜, 高敏. 基于满足性判定的布尔网络环求解算法[J]. 电子科技大学学报, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

引用本文:

郭文生, 杨国武, 李晓瑜, 高敏. 基于满足性判定的布尔网络环求解算法[J]. 电子科技大学学报, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

GUO Wen-sheng, YANG Guo-wu, LI Xiao-yu, GAO Min. SAT-Based Algorithm for Finding Cycles in a Boolean Network[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

Citation:

GUO Wen-sheng, YANG Guo-wu, LI Xiao-yu, GAO Min. SAT-Based Algorithm for Finding Cycles in a Boolean Network[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

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

doi: 10.3969/j.issn.1001-0548.2015.06.015

中图分类号: TP301.6

SAT-Based Algorithm for Finding Cycles in a Boolean Network

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

[1]	ZHAO Q. A remark on "scalar equations for synchronous boolean networks with biological applications" by C. Farrow, J. Heidel, J. Maloney, and J. Rogers[J]. IEEE Transactions on Neural Networks, 2005, 16(6): 1715-1716.
[2]	T AKUTSU, S KOSUB, A A MELKMAN, et al. Finding a periodic attractor of a Boolean network[J]. Transactions on Computational Biology and Bioinformatics, 2012, 9(5): 1410-1421.
[3]	MCMILLAN K L. Applying SAT methods in unbounded symbolic model checking[C]//14th International Conference on Computer Aided Verification. Denmark: Springer, 2002.
[4]	CHAUHAN P, CLARKE E M, KROENING D. Using SAT based image computation for reachability analysis[M]. The Netherlands: Springer, 2003.
[5]	DUBROVA E, TESLENKO M. A SAT-based algorithm for finding attractors in synchronous Boolean networks[J]. Transactions on Computational Biology and Bioinformatics (TCBB), 2011, 8(5): 1393-1399.
[6]	BRAUER J, KING A, KRIENER J. Existential quantification as incremental SAT[C]//23rd International Conference on Computer Aided Verification. Snowbird UT, USA: Springer, 2011.
[7]	LIMA J F. Boolean satisfiability solvers: Techniques, implementations and analysis[J]. Electrónica e Telecomunicações S. A., 2013, 5(2): 218-225.
[8]	GRUMBERG O, SCHUSTER A, YADGAR A. Memory efficient all-solutions SAT solver and its application for reachability analysis[C]//5th international confrence on Formal Methods in Computer-Aided Design. Texas, USA: Springer, 2004.
[9]	YU Y, SUBRAMANYAN P, TSISKARIDZE N, MALIK S. All-SAT using minimal blocking clauses[C]//27th International Conference on VLSI Design and 13th International Conference on Embedded Systems. Mumbai, India: IEEE, 2014.

[1]	陈柳, 曾成, 褚青如, 张洁, 补世荣, 宁俊松. 利用金属环聚焦的HTS薄膜R_s分布测试法的研究 . 电子科技大学学报, 2017, 46(1): 156-160. doi: 10.3969/j.issn.1001-0548.2017.01.021
[2]	程红丽, 贾龙飞. Buck变换器的数字电流滞环控制策略的改进 . 电子科技大学学报, 2017, 46(6): 812-818. doi: 10.3969/j.issn.1001-0548.2017.06.003
[3]	吴淮, 孙颖, 许春香, 伍玮. 对一种基于身份环签名方案的安全性分析 . 电子科技大学学报, 2013, 42(6): 926-929. doi: 10.3969/j.issn.1001-0548.2013.06.022
[4]	张旭东, 黄洪钟, XIE Min. 单环法求解基于可靠性的设计优化问题 . 电子科技大学学报, 2011, 40(1): 157-160. doi: 10.3969/j.issn.1001-0548.2011.01.030
[5]	朱维军, 邓淼磊, 周清雷, 张海宾. 扩展命题区间时序逻辑公式可满足性判定算法 . 电子科技大学学报, 2011, 40(5): 753-758. doi: 10.3969/j.issn.1001-0548.2011.05.023
[6]	黄平, 韩满贵. 多极磁环二维场分布的有限元计算 . 电子科技大学学报, 2010, 39(3): 447-449. doi: 10.3969/j.issn.1001-0548.2010.03.027
[7]	杨文峰, 胡予濮, 高军涛. 布尔函数的代数攻击 . 电子科技大学学报, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006
[8]	程梦璋, 景为平. CMOS环型压控振荡器的设计 . 电子科技大学学报, 2009, 38(2): 305-308. doi: 10.3969/j.issn.1001-0548.2009.02.35
[9]	李金海, 巴晓辉, 陈杰. 三阶卡尔曼滤波数字锁频环设计及性能分析 . 电子科技大学学报, 2008, 37(5): 677-680,729.
[10]	胡皓全, 曹纪纲. 新型微带交叉耦合环微波带通滤波器 . 电子科技大学学报, 2008, 37(6): 875-878.
[11]	谢昭贤, 黄大贵, 明爱国, 李智军, 下条诚. 基于同时发射声纳环移动机器人导航系统 . 电子科技大学学报, 2007, 36(2): 309-311,321.
[12]	林蓉平, 王晟, 李乐民. 一种考虑阻塞率的WDM网络可用性算法 . 电子科技大学学报, 2007, 36(1): 1-4.
[13]	张治中, 曾庆济, 雒江涛, 蒋铭, 赵正福. 弹性分组多环互连网络的跨环传输研究 . 电子科技大学学报, 2006, 35(5): 729-732.
[14]	何敏, 刘心松, 赵东风, 陈建英. 分布式并行无线令牌环接入控制协议 . 电子科技大学学报, 2005, 34(6): 813-816.
[15]	张天良, 羊恺, 补世荣, 刘娟秀, 罗正祥. 易加工开口环高温超导线性相位滤波器 . 电子科技大学学报, 2004, 33(4): 371-373.
[16]	洪洁, 范修斌, 方刚, 路晓峰. 布尔函数最优连续化 . 电子科技大学学报, 2004, 33(5): 621-622,626.
[17]	宋文, 伊良忠, 牟行军. 15-谜问题的可达性判定 . 电子科技大学学报, 2004, 33(5): 604-607.
[18]	李中桂, 邱昆, 张宏斌, 薛飞. WDM双纤双向自愈环网的研究 . 电子科技大学学报, 2001, 30(6): 559-562.
[19]	谭扬波, 陈光. 固定极Reed-Muller展开式在布尔函数等效性的应用 . 电子科技大学学报, 1999, 28(2): 216-218.
[20]	陈玉生, 朱君范, 虞厥邦. 一种改进的非线性锁相环分析及仿真方法 . 电子科技大学学报, 1998, 27(1): 39-42.

WeChat

点击查看大图

计量

文章访问数: 4894
HTML全文浏览量: 155
PDF下载量: 401
被引次数: 0

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

doi: 10.3969/j.issn.1001-0548.2015.06.015

刊出日期: 2015-12-15

中图分类号: TP301.6

关键词:

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

English Abstract

郭文生, 杨国武, 李晓瑜, 高敏. 基于满足性判定的布尔网络环求解算法[J]. 电子科技大学学报, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

引用本文:

郭文生, 杨国武, 李晓瑜, 高敏. 基于满足性判定的布尔网络环求解算法[J]. 电子科技大学学报, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

GUO Wen-sheng, YANG Guo-wu, LI Xiao-yu, GAO Min. SAT-Based Algorithm for Finding Cycles in a Boolean Network[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

Citation:

GUO Wen-sheng, YANG Guo-wu, LI Xiao-yu, GAO Min. SAT-Based Algorithm for Finding Cycles in a Boolean Network[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 881-886. doi: 10.3969/j.issn.1001-0548.2015.06.015

全文HTML

参考文献 (9)

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发