计算机科学 ›› 2020, Vol. 47 ›› Issue (11): 268-274.doi: 10.11896/jsjkx.200100079
黄羿1,2, 孔世明2, 王以松1, 张明义3, 马新强1,2
HUANG Yi1,2, KONG Shi-ming2, WANG Yi-song1 , ZHANG Ming-yi3, MA Xin-qiang1,2
摘要: 布尔网络是一种重要的基因调控数学模型,从布尔网络的状态变换推断其结构以发现基因之间的调控关系是布尔网络研究中长期关注的重要问题。已有的归纳逻辑程序算法不能从布尔网络的不确定(解释)状态变换学习推断其网络结构。为此,文中提出了非确定解释转换学习(Learning From Non-deterministic interpretation Transitions,LFNDIT)算法从布尔网络异步更新语义下的解释变换学习其网络结构。首先将异步更新语义下的不确定解释变换集转换成确定解释变换集,然后利用Inoue等提出的从1步解释转换学习(Learning From 1-step state transition,LF1T)算法计算其对应的正规逻辑程序(布尔网络)。该算法的完备性得到了证明,初步的实验结果表明,该方法能有效地从不确定状态变换计算布尔网络的结构,从而为发现布尔网络的结构提供了新的思路。
中图分类号:
[1] KAUFFMAN S A.Metabolic stability and epigenesis in ran-domly constructed genetic nets[J].Journal of Theoretical Bio-logy,1969,22(3):437-467. [2] KAUFFMAN S A.Origins of order in evolution:self-organization and selection[J].In Understanding Origins,10.1007/978-94-015-8054-0.Springer,1992,(Chapter 8):153-181. [3] DUBROVA E,TESLENKO M.A sat-based Algorithm for finding attractors in synchronous Boolean networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(5):1393-1399. [4] VELIZ-CUBA A.Reduction of boolean network models[J].Journal of Theoretical Biology,2011,289:167-172. [5] CHENG D Z,QI H S.Controllability and observability of boo-lean control networks[J].Automatica,2009,45(7):1659-1667. [6] JARRAH A S,LAUBENBACHER R,VELIZ-CUBA A.Thedynamics of conjunctive and disjunctive boolean network models[J].Bulletin of Mathematical Biology,2010,72(6):1425-1447. [7] KRAWITZ P,SHMULEVICH I.Basin entropy in boolean network ensembles[J].Physical Review Letters,2007,98(15):158701. [8] MENINI L,POSSIERI C,TORNAMBÉ A.Boolean networkanalysis through the joint use of linear algebra and algebraic geometry[J].Journal of theoretical biology,2019,472:46-53. [9] TONELLO E,FARCOT E,CHAOUIYA C.Local negative circuits and cyclic attractors in Boolean networks with at most five components[J].SIAM Journal on Applied Dynamical Systems,2019,18(1):68-79. [10] LIANG S D,FUHRMAN S,SOMOGYI R.Reveal,a general reverse engineering algorithm for inference of genetic network architectures[C]//Pacific Symposium on Biocomputing.1998,3:18-29. [11] HAIDER S,PAL R.Boolean network inference from time series data incorporating prior biological knowledge[J].BMC geno-mics,2012,13(6):S9. [12] OSTROWSKI M,PAULEVÉ L,SCHAUB T,et al.Booleannetwork identification from multiplex time series data[C]//International Conference on Computational Methods in Systems Biology.Springer,2015:170-181. [13] OSTROWSKI M,PAULEVÉ L,SCHAUB T,et al.Booleannetwork identification from perturbation time series data combining dynamics abstraction and logic programming[J].Biosystems,2016,149:139-153. [14] LÄHDESMÄKI H,SHMULEVICH I,YLI-HARJA O.Onlearning gene regulatory networks under the boolean network model[J].Machine Learning,2003,52(1/2):147-167. [15] STALIN M,MIGUEL C,EUGENIO A,et al.Griffin:A Tool for Symbolic Inference of Synchronous Boolean Molecular Networks[J].Frontiers in Genetics,2018,9:39. [16] SHI N,ZHU Z,TANG K,et al.ATEN:And/Or tree ensemble for inferring accurate Boolean network topology and dynamics[J].Bioinformatics,2020,36(2):578-585. [17] RÉDA C,WILCZYЙSKI B.Automated inference of gene regulatory networks using explicit regulatory modules[J].Journal of Theoretical Biology,2020,486:110091. [18] YUE J,YAN Y,CHEN Z,et al.Identification of predictors of Boolean networks from observed attractor states[J].Mathematical Methods in the Applied Sciences,2019,42(11):3848-3864. [19] GERSHENSON C.Classification of random boolean networks[J].arXiv:cs/0208001,2002. [20] INOUE K.Logic programming for boolean networks[C]//Twenty-Second International Joint Conference on Artificial Intelligence.2011. [21] INOUE K,SAKAMA C.Oscillating behavior of logic programs[M]//Correct Reasoning.Springer,Berlin,Heidelberg,2012:345-362. [22] MUGGLETON S.Inductive logic programming[J].New Generation Computing,1991,8(4):295-318. [23] MUGGLETON S,DE RAEDT L.Inductive logic programming:Theory and methods[J].The Journal of Logic Programming,1994,19:629-679. [24] INOUE K,RIBEIRO T,SAKAMA C.Learning from interpretation transition[J].Machine Learning,2014,94(1):51-79. [25] RIBEIRO T,INOUE K.Learning prime implicant conditionsfrom interpretation transition[M]//Inductive Logic Programming.Springer,Cham,2015:108-125. [26] HUANG Y,WANG Y,ZHANG Y,et al.Learning Disjunctive Logic Programs from Interpretation Transition[C]//26th International Conference on Inductive Logic Programming.2016:34-40. [27] RIBEIRO T,FOLSCHETTE M,MAGNIN M,et al.Learning Dynamics with Synchronous,Asynchronous and General Semantics[C]//International Conference on Inductive Logic Programming.Springer,Cham,2018:118-140. [28] CHATAIN T,HAAR S,PAULEVÉ L.Boolean networks:beyond generalized asynchronicity[C]//International Workshop on Cellular Automata and Discrete Complex Systems.Springer,Cham,2018:29-42. |
[1] | 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161 |
[2] | 郭宗豪,魏欧. 使用模型检测解决概率布尔网络优化控制 Optimal Control of Probabilistic Boolean Networks Using Model Checking 计算机科学, 2017, 44(5): 193-198. https://doi.org/10.11896/j.issn.1002-137X.2017.05.035 |
[3] | 刘振,张志政. 一种基于ILP和ASP的学习B语言描述的动作模型方法 Learning Action Models Described in Action Language B by Combining ILP and ASP 计算机科学, 2015, 42(1): 220-226. https://doi.org/10.11896/j.issn.1002-137X.2015.01.049 |
[4] | 张伟 杨炳儒 钱榕. 多关系频繁模式发现研究 计算机科学, 2007, 34(7): 158-164. |
[5] | . 粗集和多关系学习综述 计算机科学, 2007, 34(6): 152-155. |
|