The evolution of higher-level biochemical reaction models
Tóm tắt
Computational tools for analyzing biochemical phenomena are becoming increasingly important. Recently, high-level formal languages for modeling and simulating biochemical reactions have been proposed. These languages make the formal modeling of complex reactions accessible to domain specialists outside of theoretical computer science. This research explores the use of genetic programming to automate the construction of models written in one such language. Given a description of desired time-course data, the goal is for genetic programming to construct a model that might generate the data. The language investigated is Kahramanoğullari’s and Cardelli’s Programming Interface for Modeling (PIM) language. The PIM syntax is defined in a grammar-guided genetic programming system. All time series generated during simulations are described by statistical feature tests, and the fitness evaluation compares feature proximity between the target and candidate solutions. PIM models of varying complexity were used as target expressions for genetic programming, and were successfully reconstructed in all cases. This shows that the compositional nature of PIM models is amenable to genetic program search.
Tài liệu tham khảo
citation_journal_title=Inf. Sci.; citation_title=Evolutionary modeling and inference of gene network; citation_author=S. Ando, E. Sakamoto, H. Iba; citation_volume=145; citation_issue=3–4; citation_publication_date=2002; citation_pages=237-259; citation_doi=10.1016/S0020-0255(02)00235-9; citation_id=CR1
P. Angeline, Evolving predictors for chaotic time series. In Proceedings of the. SPIE: Application and Science of Computational Intelligence, vol. 3390, pp. 170–180 (1998)
citation_journal_title=Nat. Comput.; citation_title=Petri nets for modelling metabolic pathways: a survey; citation_author=P. Baldan, N. Cocco, A. Marin, M. Simeoni; citation_volume=9; citation_issue=4; citation_publication_date=2010; citation_pages=955-989; citation_doi=10.1007/s11047-010-9180-6; citation_id=CR3
citation_title=Artificial Regulatory Networks and Genetic Programming; citation_inbook_title=Genetic Programming Theory and Practice; citation_publication_date=2003; citation_pages=43-61; citation_id=CR4; citation_author=W. Banzhaf; citation_publisher=Kluwer
P. Bentley, J. Wakefield, in Soft Computing in Engineering Design and Manufacturing, ed. by P.K. Chawdhry et al. Finding Acceptable Solutions in the Pareto-Optimal Range Using Multiobjective Genetic Algorithms (Springer, Berlin, 1997)
BioSPI: The biospi project (2010).
http://www.wisdom.weizmann.ac.il/biospi
. Last accessed July 9, 2010
citation_journal_title=Trans. Comput. Syst. Biol.; citation_title=A compositional approach to the stochastic dynamics of gene networks; citation_author=R. Blossey, L. Cardelli, A. Phillips; citation_volume=3939; citation_publication_date=2006; citation_pages=99-122; citation_id=CR7
citation_journal_title=Phys. A Stat. Theor. Phys.; citation_title=Performance of genetic programming to extract the trend in noisy data series; citation_author=A. Borrelli, I. De Falco, A. Della Cioppa, M. Nicodemi, G. Trautteura; citation_volume=370; citation_issue=1; citation_publication_date=2006; citation_pages=104-108; citation_doi=10.1016/j.physa.2006.04.025; citation_id=CR8
citation_title=Computational Modeling of Genetic and Biochemical Networks; citation_publication_date=2001; citation_id=CR9; citation_author=J. Bower; citation_author=H. Bolouri; citation_publisher=MIT Press, Kaufmann
citation_journal_title=Syst. Synth. Biol.; citation_title=Evolving cell models for systems and synthetic biology; citation_author=H. Cao, F. Romero-Campero, S. Heeb, M. Camara, N. Krasnogor; citation_volume=4; citation_issue=1; citation_publication_date=2010; citation_pages=55-84; citation_doi=10.1007/s11693-009-9050-7; citation_id=CR10
A. Castellini, V. Manca, in Proceedings of the GECCO 2009, ed. by A.I. Esparcia et al. Learning Regulation Functions of Metabolic Systems by Artificial Neural Networks (ACM Press, New york, 2009), pp. 193–200
citation_journal_title=Brief Bioinform; citation_title=Petri net modelling of biological networks; citation_author=C. Chaoulya; citation_volume=8; citation_issue=4; citation_publication_date=2007; citation_pages=210-219; citation_doi=10.1093/bib/bbm029; citation_id=CR12
citation_journal_title=Bioinformatics; citation_title=Identification of biochemical networks by S-tree based genetic programming; citation_author=D.Y. Cho, K.H. Cho, B.T. Zhang; citation_volume=22; citation_issue=13; citation_publication_date=2006; citation_pages=1631-1640; citation_doi=10.1093/bioinformatics/btl122; citation_id=CR13
citation_journal_title=Math. Biosci.; citation_title=Recent developments in parameter estimation and structure identification of biochemical and genomic systems; citation_author=I. Chou, E. Voit; citation_volume=219; citation_publication_date=2009; citation_pages=57-83; citation_doi=10.1016/j.mbs.2009.03.002; citation_id=CR14
D. Chu, in Proceedings of the CEC 2007, ed. by D. Srinivasan, L. Wang. Evolving Genetic Regulatory Networks for Systems Biology (IEEE Press, Singapore, 2007), pp. 875–882
citation_title=Programming in Prolog; citation_publication_date=1994; citation_id=CR16; citation_author=W. Clocksin; citation_author=C. Mellish; citation_publisher=Springer
citation_title=Evolutionary Algorithms for Solving Multi-Objective Problems; citation_publication_date=2007; citation_id=CR17; citation_author=C.C. Coello; citation_author=G. Lamont; citation_author=D.V. Veldhuizen; citation_publisher=Kluwer
V. Danos, J. Feret, W. Fontana, R. Harmer, J. Krivine, in CONCUR 2007, ed. by L. Caires, V. Vasconcelos. Rule-Based Modelling of Cellular Signalling. LNCS 4703 (Springer, Berline, 2007), pp. 17–41
L. Dematte, C. Priami, A. Romanel, in SFM 2008, ed. by M. Bernardo, P. Degano, G. Zavattaro. The BlenX Language: A Tutorial. LNCS 5016 (Springer, Berline, 2008), pp. 313–365
citation_title=Cellular Automaton Modeling of Biological Pattern Formation; citation_publication_date=2005; citation_id=CR20; citation_author=A. Deutsch; citation_author=S. Dormann; citation_publisher=Birkhauser
B. Drennan, R. Beer, in Artificial Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, ed. by L.R. Rocha et al. Evolution of Repressilators Using a Biologically-Motivated Model of Gene Expression (MIT Press, Cambridge, 2006), pp. 22–27
citation_journal_title=J. Theor. Biol.; citation_title=Cellular automata approaches to biological modeling; citation_author=G. Ermentrout, L. Edelstein-Keshet; citation_volume=160; citation_publication_date=1993; citation_pages=97-133; citation_doi=10.1006/jtbi.1993.1007; citation_id=CR22
citation_journal_title=Nat. Biotechnol.; citation_title=Executable cell biology; citation_author=J. Fisher, T. Henzinger; citation_volume=25; citation_issue=11; citation_publication_date=2007; citation_pages=1239-1249; citation_doi=10.1038/nbt1356; citation_id=CR23
A. Floares, in WCCI 2008, ed. by J. Wang. Automatic Inferring Drug Gene Regulatory Networks with Missing Information Using Neural Networks and Genetic Programming (IEEE, New York, 2008), pp. 3078–3085
citation_journal_title=J. Comput. Biol.; citation_title=Using Bayesian networks to analyze expression data; citation_author=N. Friedman, M. Linial, I. Nachman, D. Pe’er; citation_volume=7; citation_issue=3-4; citation_publication_date=2000; citation_pages=601-620; citation_doi=10.1089/106652700750050961; citation_id=CR25
citation_journal_title=J. Phys. Chem; citation_title=Exact stochastic simulation of coupled chemical reactions; citation_author=D. Gillespie; citation_volume=81; citation_publication_date=1977; citation_pages=2340-2361; citation_doi=10.1021/j100540a008; citation_id=CR26
citation_title=Genetic Algorithms in Search, Optimization, and Machine Learning; citation_publication_date=1989; citation_id=CR27; citation_author=D. Goldberg; citation_publisher=Addison Wesley
M. Guerriero, J. Heath, C. Priami, in CMSB 2007, ed. by M. Calder, S. Gilmore. An Automated Translation from a Narrative Language for Biological Modelling into Process Algebra. LNCS 4695 (Springer, Berlin, 2007), pp. 136–151
citation_journal_title=Biosystems; citation_title=Gene regulatory network inference: data integration in dynamic models—a review; citation_author=M. Hecker, S. Lambeck, S. Toepfer, E. Someren, R. Guthke; citation_volume=96; citation_issue=1; citation_publication_date=2009; citation_pages=86-103; citation_doi=10.1016/j.biosystems.2008.12.004; citation_id=CR29
citation_title=Communicating Sequential Processes; citation_publication_date=1985; citation_id=CR30; citation_author=C.A.R. Hoare; citation_publisher=Prentice-Hall
citation_journal_title=Bioinformatics; citation_title=Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic Bayesian networks; citation_author=D. Husmeier; citation_volume=19; citation_issue=17; citation_publication_date=2003; citation_pages=2271-2282; citation_doi=10.1093/bioinformatics/btg313; citation_id=CR31
J. Imada, Evolutionary synthesis of stochastic gene network models using feature-based search spaces. Master’s thesis, Department of Computer Science, Brock University (2009)
J. Imada, B. Ross, Evolutionary synthesis of stochastic gene network models using feature-based search spaces. New Generation Computing (2010, in press)
INRIA: OCAML (2010).
http://caml.inria.fr/ocaml/
. Last accessed July 1, 2010
citation_journal_title=IEEE Trans. Evol. Comput.; citation_title=Evolutionary optimization in uncertain environments–a survey; citation_author=Y. Jin, J. Branke; citation_volume=9; citation_issue=3; citation_publication_date=2005; citation_pages=303-317; citation_doi=10.1109/TEVC.2005.846356; citation_id=CR35
O. Kahramanogullari, Pim—spim (2010).
http://sites.google.com/site/ozankahramanogullari/software/pim
. Last accessed July 12, 2011
O. Kahramanogullari, L. Cardelli, in DCM’09, ed. by S.B. Cooper, V. Danos. An Intuitive Automated Modelling Interface for Systems Biology (EPTCS, 2009), pp. 1–18
citation_journal_title=Bioinformatics; citation_title=Dynamic modeling of genetic networks using genetic algorithm and S-system; citation_author=S. Kikuchi, D. Tominaga, M. Arita, K. Takahashi, M. Tomita; citation_volume=19; citation_issue=5; citation_publication_date=2003; citation_pages=643-650; citation_doi=10.1093/bioinformatics/btg027; citation_id=CR38
citation_title=Identifying Metabolic Pathways and Gene Regulation Networks with Evolutionary Algorithms; citation_inbook_title=Evolutionary Computation in Bioinformatics; citation_publication_date=2003; citation_pages=255-278; citation_id=CR39; citation_author=J. Kitagawa; citation_author=H. Iba; citation_publisher=Morgan Kaufmann
citation_title=Genetic Programming: On the Programming of Computers by Means of Natural Selection; citation_publication_date=1992; citation_id=CR40; citation_author=J. Koza; citation_publisher=MIT Press
citation_title=Genetic Programming IV: Routine Human-Competitive Machine Intelligence; citation_publication_date=2003; citation_id=CR41; citation_author=J. Koza; citation_author=M. Keane; citation_author=M. Streeter; citation_author=W. Mydlowec; citation_author=J. Yu; citation_author=G. Lanza; citation_publisher=Kluwer Academic Publishers
J. Koza, W. Mydlowec, G. Lanza, J. Yu, M. Keane, Reverse Engineering and Automatic Synthesis of Metabolic Pathways from Observed Data using Genetic Programming. Technical report SMI-2000-0851, Stanford Medical Informatics (2000)
citation_journal_title=Genomics Proteomics Bioinf.; citation_title=Applying intelligent computing techniques to modeling biologial networks from expression data; citation_author=W.P. Lee, K.C. Yang; citation_volume=6; citation_issue=2; citation_publication_date=2008; citation_pages=111-120; citation_doi=10.1016/S1672-0229(08)60026-1; citation_id=CR43
A. Leier, P. Kuo, W. Banzhaf, K. Burrage, in EuroGP 2006, ed. by P. Collet et al. Evolving Noisy Oscillatory Dynamics in Genetic Regulatory Networks. LNCS, vol. 3905 (Springer, Berlin, 2006), pp. 290–299
citation_journal_title=Biosystems; citation_title=Evolving fuzzy rules to model gene expression; citation_author=R. Linden, A. Bhaya; citation_volume=88; citation_issue=1-2; citation_publication_date=2007; citation_pages=76-91; citation_doi=10.1016/j.biosystems.2006.04.006; citation_id=CR45
citation_title=Computational Methods of Feature Selection; citation_publication_date=2007; citation_id=CR46; citation_author=H. Liu; citation_author=H. Motoda; citation_publisher=Chapman and Hall/CRC
F. Markowetz, A Bibliography on Learning Causal Networks of Gene Interactions (2005).
http://www.molgen.mpg.de/~markowet/docs/network-bib.pd
. Last accessed April 1, 2005
citation_journal_title=BMC Bioinf.; citation_title=Inferring cellular networks—a review; citation_author=F. Markowetz, R. Spang; citation_volume=8; citation_publication_date=2007; citation_pages=1-17; citation_doi=10.1186/1471-2105-8-S6-S5; citation_id=CR48
citation_title=Communication and Concurrency; citation_publication_date=1989; citation_id=CR49; citation_author=R. Milner; citation_publisher=Prentice Hall
J. Moore, L. Hahn, In: Proceeding of the GECCO 2004, ed. by K. Deb et al. Systems Biology Modeling in Human Genetic Using Petri Nets and Grammatical Evolution. LNCS 3102 (Springer, Berlin, 2004), pp. 392–401
A. Nanopoulos, R. Alcock, Y. Manolopoulos, in Information Processing and Technology, ed. by N. Mastorakis, S.D. Nikolopoulos. Feature-Based Classification of Time-Series Data. (Nova Science Publishers, Inc., Commack, 2001), pp. 49–61
citation_title=CCS—and its Relationship to Net Theory, LNCS 255; citation_inbook_title=Petri Nets: Application and Relationship to Other Models of Concurrency; citation_publication_date=1987; citation_pages=393-415; citation_id=CR52; citation_author=M. Nielsen; citation_publisher=Springer
J. Nummela, B. Julstrom, in Proceedings of the GECCO 2005, ed. by H.-G. Beyer et al. Evolving Petri Nets to Represent Metabolic Pathways (ACM, New York, 2005), pp. 2133–2139
citation_title=Membrane Computing: An Introduction; citation_publication_date=2002; citation_id=CR54; citation_author=G. Paun; citation_publisher=Springer
citation_journal_title=J. Am. Med. Inform. Assoc.; citation_title=Using petri net tools to study properties and dynamics of biological systems; citation_author=M. Peleg, D. Rubin, R. Altman; citation_volume=12; citation_issue=2; citation_publication_date=2005; citation_pages=181-199; citation_doi=10.1197/jamia.M1637; citation_id=CR55
citation_journal_title=Trans. Comput. Syst.Biol.; citation_title=P systems: a new computational modelling tool for systems biology; citation_author=M. Perez-Jiminez, F. Romero-Campero; citation_volume=VI; citation_publication_date=2006; citation_pages=176-197; citation_id=CR56
A. Phillips, The stochastic pi machine (2008).
http://research.microsoft.com/aphillip/spim
. Last accessed Dec 9, 2008
A. Phillips, L. Cardelli, in Proceedings of the Bioconcur’04. A Correct Abstract Machine for the Stochastic Pi-calculus (2004)
citation_journal_title=Comput. J.; citation_title=Stochastic pi-calculus; citation_author=C. Priami; citation_volume=38; citation_issue=7; citation_publication_date=1995; citation_pages=579-589; citation_doi=10.1093/comjnl/38.7.578; citation_id=CR59
citation_journal_title=IEEE Trans. Signal Process.; citation_title=Inference of noisy nonlinear differential equation models for gene regulatory networks using genetic programming and kalman filtering; citation_author=L. Qian, H. Wang, E. Dougherty; citation_volume=56; citation_issue=7; citation_publication_date=2008; citation_pages=3327-3339; citation_doi=10.1109/TSP.2008.919638; citation_id=CR60
citation_journal_title=Cell; citation_title=Nature, nurture, or chance: stochastic gene expression and its consequences; citation_author=A. Raj, A. van Oudenaarden; citation_volume=135; citation_publication_date=2008; citation_pages=216-226; citation_doi=10.1016/j.cell.2008.09.050; citation_id=CR61
citation_journal_title=Theor. Comput. Sci.; citation_title=BioAmbients: an abstraction for biological compartments; citation_author=A. Regev, E. Panina, W. Silverman, L. Cardelli, E. Shapiro; citation_volume=325; citation_issue=1; citation_publication_date=2004; citation_pages=141-167; citation_doi=10.1016/j.tcs.2004.03.061; citation_id=CR62
citation_journal_title=Knowl. Inf. Syst.; citation_title=Evolution of mathematical models of chaotic systems based on multiobjective genetic programming; citation_author=K. Rodriguez-Vazquez, P.J. Fleming; citation_volume=8; citation_issue=2; citation_publication_date=2005; citation_pages=235-256; citation_doi=10.1007/s10115-004-0184-3; citation_id=CR63
citation_journal_title=New Gener. Comput.; citation_title=Logic-based genetic programming with definite clause translation grammars; citation_author=B. Ross; citation_volume=19; citation_issue=4; citation_publication_date=2001; citation_pages=313-337; citation_doi=10.1007/BF03037572; citation_id=CR64
B. Ross, in Proceedings CI-2007, ed. by R. Andonie. Using Genetic Programming to Synthesize Monotonic Stochastic Processes (ACTA Press, 2007)
B. Ross, in Proceedings of the CEC 2011. Evolution of Stochastic Bio-Networks Using Summed Rank Strategies (IEEE Press, New York, 2011)
B. Ross, J. Imada, in Proceedings of the GECCO 2009. Evolving Stochastic Processes Using Feature Tests and Genetic Programming (2009)
B. Ross, J. Imada, in Genetic Programming—Theory and Practice, ed. by R. Riolo et al. Using Multi-objective Genetic Programming to Synthesize Stochastic Processes (Springer, 2009)
E. Sakamoto, H. Iba, in Proceedings of the CEC 2001. Inferring a System of Differential Equations for a Gene Regulatory Network by Using Genetic Programming (IEEE Press, New York, 2001), pp. 720–726
R. Schwaerzel, T. Bylander, in GECCO 2006, ed. by M. Keijzer et al. Predicting Currency Exchange Rates by Genetic Programming with Trigonometric Functions and High-Order Statistics (ACM, New York, 2006), pp. 955–956
citation_title=Biological Modeling and Simulation; citation_publication_date=2008; citation_id=CR71; citation_author=R. Schwartz; citation_publisher=MIT Press
SICS: SICStus Prolog 4 (2010).
http://www.sics.se/isl/sicstuswww/site/index.htm
. Last accessed July 1, 2010.
F. Streichert, H. Planatscher, C. Spieth, H. Ulmer, A. Zell, In GECCO-2004, ed. by K. Deb et al. Comparing Genetic Programming and Evolution Strategies on Inferring Gene Regulatory Networks. LNCS, vol. 3102 (Springer, Seattle, 2004), pp. 471–480
citation_title=Cell Biology: Networks, Regulation and Pathways; citation_inbook_title=Encyclopedia of Complexity and Systems Science; citation_publication_date=2009; citation_id=CR74; citation_author=G. Tkacik; citation_author=W. Bialek; citation_publisher=Springer
H. Wang, L. Qian, E. Dougherty, in CIBCB 07, ed. by G. Volkert. Inference of Gene Regulatory Networks using S-System: A Unified Approach. (IEEE, New York, 2007), pp. 82–89
X. Wang, K. Smith, R. Hyndman, Characteristic-based clustering for time series data. Data Min. Knowl. Discov. 13(3), 335–364. (2006). doi:
10.1007/s10618-005-0039-x
Wikipedia: Phagocytosis (2010).
http://en.wikipedia.org/wiki/Phagocytosi
. Last accessed July 2, 2010
citation_journal_title=Bioinformatics; citation_title=Advances to Bayesian network inference for generating causal networks from observational biological data; citation_author=J. Yu, V. Smith, P. Wang, A. Hartemink, E. Jarvis; citation_volume=20; citation_issue=18; citation_publication_date=2004; citation_pages=3594-3603; citation_doi=10.1093/bioinformatics/bth448; citation_id=CR78
W. Zhang, G. Yang, Wu Z., in Proceedings of the 3rd International Conference on Machine Learning and Cybernetics. Genetic Programming-based Modeling on Chaotic Time Series (IEEE, New York, 2004), pp. 2347–2352
