Computer Science ›› 2020, Vol. 47 ›› Issue (11): 268-274.doi: 10.11896/jsjkx.200100079

• Artificial Intelligence • Previous Articles     Next Articles

LFNDIT:Learning Boolean Networks from Nondeterministic Interpretation Transitions

HUANG Yi1,2, KONG Shi-ming2, WANG Yi-song1 , ZHANG Ming-yi3, MA Xin-qiang1,2   

  1. 1 College of Computer Science and Technology,GuizhouUniversity,Guiyang 550025,China
    2 College of Artificial Intelligence,Chongqing University of Arts and Sciences,Chongqing 402160,China
    3 Guizhou Academy of Sciences,Guiyang 550001,China
  • Received:2020-01-11 Revised:2020-04-07 Online:2020-11-15 Published:2020-11-05
  • About author:HUANG Yi,born in 1976,Ph.D candidate,professor,is a member of China Computer Federation.Her main research interests include artificial intelligence,knowledge representation and reasoning.
    WANG Yi-song,born in 1975,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include artificial intelligence,knowledge representation and reasoning.
  • Supported by:
    The work was supported by the Nature Science Foundation of China(61976065),Key Industrial Technology Development Project of Chongqing Development and Reform Commission,China(2018148208),Key Technological Innovation and Application Development Project of Chongqing,China(cstc2019jscx-fxydX0094) and Innovation and Entrepreneurship Demonstration Team of Yingcai Program of Chongqing,China(CQYC201903167).

Abstract: Boolean network is an important mathematical model for gene regulation.It is an important issue that inferring structure from the interpretation transitions of Boolean network to discover the regulatory relationship between genes.Thus,resear-chers in the field of Boolean networks have been paying attention for a long time.Existing inductive logic program algorithms cannot infer the network structure from a set of nondeterministic state transitions.To this end,LFNDIT is proposed to learn the structure from state transitions under the asynchronous update semantics of Boolean network.First it translates a set of uncertain state transitions into the set of certain state transitions,and then uses the LF1T learning algorithm proposed by Inoue et al to calculate the corresponding normal logic program (Boolean network).The completeness of LFNDIT is proofed.The preliminary experimental results show that the algorithm can effectively calculate the Boolean network structure from the uncertain state transitions,thus it provides a new idea for discovering Boolean network structure.

Key words: ABN, Boolean network, Inductive logical programming, LFNDIT algorithm, Normal logic programming

CLC Number: 

  • TP391
[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] YANG Xiao, WANG Xiang-kun, HU Hao, ZHU Min. Survey on Visualization Technology for Equipment Condition Monitoring [J]. Computer Science, 2022, 49(7): 89-99.
[2] ZHANG Hong-min, LI Ping-ping, FANG Xiao-bing, LIU Hong. Human Abnormal Behavior Detection Method Based on Improved YOLOv3 Network Model [J]. Computer Science, 2022, 49(4): 233-238.
[3] XU Tao, TIAN Chong-yang, LIU Cai-hua. Deep Learning for Abnormal Crowd Behavior Detection:A Review [J]. Computer Science, 2021, 48(9): 125-134.
[4] HOU Chun-ping, ZHAO Chun-yue, WANG Zhi-peng. Video Abnormal Event Detection Algorithm Based on Self-feedback Optimal Subclass Mining [J]. Computer Science, 2021, 48(7): 199-205.
[5] ZHANG Ren-jie, CHEN Wei, HANG Meng-xin, WU Li-fa. Detection of Abnormal Flow of Imbalanced Samples Based on Variational Autoencoder [J]. Computer Science, 2021, 48(7): 62-69.
[6] GUAN Wen-hua, LIN Chun-yu, YANG Shang-rong, LIU Mei-qin, ZHAO Yao. Detection of Head-bowing Abnormal Pedestrians Based on Human Joint Points [J]. Computer Science, 2021, 48(5): 163-169.
[7] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[8] YAO Lan, ZHAO Yong-heng, SHI Yu-qing, YU Ming-he. Highway Abnormal Event Detection Algorithm Based on Video Analysis [J]. Computer Science, 2020, 47(8): 208-212.
[9] YUAN De-yu, ZHANG Yi-fan, GAO Jian and SUN Hai-chun. Abnormal User Detection Method in Sina Weibo Based on User Feature Extraction [J]. Computer Science, 2020, 47(6A): 364-368.
[10] WANG Kun-lun, LIU Wen-can, HE Xiao-hai, QING Lin-bo, WU Xiao-hong. Motion Feature Descriptor for Abnormal Behavior Detection [J]. Computer Science, 2020, 47(4): 119-124.
[11] DING Rong-li, LI Jie, ZHANG Man, LIU Yan-li, WU Wei. Ship Target Detection in Remote Sensing Image Based on S-HOG [J]. Computer Science, 2020, 47(11A): 248-252.
[12] XU He, WU Hao, LI Peng. Design of Temporal-spatial Data Processing Algorithm for IoT [J]. Computer Science, 2020, 47(11): 310-315.
[13] HOU Ming-xing,QI Hui,HUANG Bin-ke. Data Abnormality Processing in Wireless Sensor Networks Based on Distributed Compressed Sensing [J]. Computer Science, 2020, 47(1): 276-280.
[14] XU Lei, WANG Jian-xin. Data Mining Algorithm of Abnormal Network Based on Fuzzy Neural Network [J]. Computer Science, 2019, 46(4): 73-76.
[15] LI Zhi, MA Chun-lai, MA Tao, SHAN Hong. Anomaly Detection Method of Mobile Terminal User Based on Location Information [J]. Computer Science, 2019, 46(3): 180-187.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!