×

Biochemical reaction rules with constraints. (English) Zbl 1326.68050

Barthe, Gilles (ed.), Programming languages and systems. 20th European symposium on programming, ESOP 2011, held as part of the joint European conferences on theory and practice of software, ETAPS 2011, Saarbrücken, Germany, March 26 – April 3, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19717-8/pbk). Lecture Notes in Computer Science 6602, 338-357 (2011).
Summary: We propose React\((C)\), an expressive programming language for stochastic modeling and simulation in systems biology that is based on biochemical reactions with constraints. We prove that React\((C)\) can express the stochastic \(\pi \)-calculus, in contrast to previous rule-based programming languages, and further illustrate the high expressiveness of React\((C)\). We present a stochastic simulator for React\((C)\) independently of the choice of the constraint language \(C\). Our simulator decides for a given reaction rule whether it can be applied to the current biochemical solution. We show that this decision problem is NP-complete for arbitrary constraint systems \(C\) and that it can be solved in polynomial time for rules of bounded arity. In practice, we propose to solve this problem by constraint programming.
For the entire collection see [Zbl 1213.68027].

MSC:

68N15 Theory of programming languages
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
92-08 Computational methods for problems pertaining to biology
92C40 Biochemistry, molecular biology
92C42 Systems biology, networks

Software:

BioNetGen; SpiCO; Dizzy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blinov, M.L., Faeder, J.R., Goldstein, B., Hlavacek, W.S.: Bionetgen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. Bioinformatics 20(17), 3289–3291 (2004) · doi:10.1093/bioinformatics/bth378
[2] Cardelli, L.: From processes to odes by chemistry. In: IFIP TCS. IFIP, vol. 273, pp. 261–281. Springer, Heidelberg (2008)
[3] Chabrier-Rivier, N., Fages, F., Soliman, S.: The biochemical abstract machine biocham. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 172–191. Springer, Heidelberg (2005) · Zbl 1088.68817 · doi:10.1007/978-3-540-25974-9_14
[4] Danos, V., Feret, J., Fontana, W., Harmer, R., Krivine, J.: Abstracting the differential semantics of rule-based models: Exact and automated model reduction. In: 25th LICS, pp. 362–381. IEEE Press, Los Alamitos (2010)
[5] Danos, V., Feret, J., Fontana, W., Krivine, J.: Scalable simulation of cellular signaling networks. In: Shao, Z. (ed.) APLAS 2007. LNCS, vol. 4807, pp. 139–157. Springer, Heidelberg (2007) · Zbl 05275792 · doi:10.1007/978-3-540-76637-7_10
[6] Danos, V., Laneve, C.: Formal molecular biology. TCS 325(1), 69–110 (2004) · Zbl 1071.68041 · doi:10.1016/j.tcs.2004.03.065
[7] Fournet, C., Gonthier, G.: The reflexive cham and the join-calculus. In: POPL, pp. 372–385. ACM Press, New York (1996)
[8] Gillespie, D.T.: A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. Journal of Computational Physics 22(4), 403–434 (1976) · doi:10.1016/0021-9991(76)90041-3
[9] Gilroy, S.W., Harrison, M.D.: SBML: a user interface mark-up language based on interaction style. Int. J. Web Eng. Technol. 4(2), 207–234 (2008) · Zbl 05422796 · doi:10.1504/IJWET.2008.018098
[10] John, M., Lhoussaine, C., Niehren, J.: Dynamic compartments in the imperative pi calculus. In: Degano, P., Gorrieri, R. (eds.) CMSB 2009. LNCS, vol. 5688, pp. 235–250. Springer, Heidelberg (2009) · Zbl 05609279 · doi:10.1007/978-3-642-03845-7_16
[11] John, M., Lhoussaine, C., Niehren, J., Uhrmacher, A.: The attributed pi calculus with priorities. In: Priami, C., Breitling, R., Gilbert, D., Heiner, M., Uhrmacher, A.M. (eds.) Transactions on Computational Systems Biology XII. LNCS, vol. 5945, pp. 13–76. Springer, Heidelberg (2010) · Zbl 1275.92023 · doi:10.1007/978-3-642-11712-1_2
[12] Krivine, J., Danos, V., Benecke, A.: Modelling epigenetic information maintenance: A kappa tutorial. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 17–32. Springer, Heidelberg (2009) · Zbl 05571884 · doi:10.1007/978-3-642-02658-4_3
[13] Kuttler, C., Lhoussaine, C., Nebut, M.: Rule-based modeling of transcriptional attenuation at the tryptophan operon. In: Priami, C., Breitling, R., Gilbert, D., Heiner, M., Uhrmacher, A.M. (eds.) Transactions on Computational Systems Biology XII. LNCS, vol. 5945, pp. 199–228. Springer, Heidelberg (2010) · Zbl 1275.92024 · doi:10.1007/978-3-642-11712-1_6
[14] Kuttler, C., Lhoussaine, C., Niehren, J.: A stochastic pi calculus for concurrent objects. In: Anai, H., Horimoto, K., Kutsia, T. (eds.) Ab 2007. LNCS, vol. 4545, pp. 232–246. Springer, Heidelberg (2007) · Zbl 1126.92003 · doi:10.1007/978-3-540-73433-8_17
[15] Laneve, C., Pradalier, S., Zavattaro, G.: From biochemistry to stochastic processes. ENTCS 253(3), 167–185 (2009)
[16] Papanikolaou, N.: The space and motion of communicating agents author: Robin Milner. SIGACT News 41(3), 51–55 (2010) · doi:10.1145/1855118.1855130
[17] Phillips, A., Cardelli, L.: Efficient, correct simulation of biological processes in the stochastic pi-calculus. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS (LNBI), vol. 4695, pp. 184–199. Springer, Heidelberg (2007) · Zbl 05282354 · doi:10.1007/978-3-540-75140-3_13
[18] Priami, C.: Stochastic pi-calculus. Comput. J. 38(7), 578–589 (1995) · Zbl 05478217 · doi:10.1093/comjnl/38.7.578
[19] Ramsey, S., Orrell, D., Bolouri, H.: Dizzy: Stochastic simulation of large-scale genetic regulatory networks. J. Bioinformatics and Computational Biology 3(2), 415–436 (2005) · Zbl 02216506 · doi:10.1142/S0219720005001132
[20] Regev, A., Panina, E.M., Silverman, W., Cardelli, L., Shapiro, E.Y.: Bioambients: an abstraction for biological compartments. TCS 325(1), 141–167 (2004) · Zbl 1069.68569 · doi:10.1016/j.tcs.2004.03.061
[21] Regev, A., Shapiro, E.: Cells as Computation. Nature 419, 343 (2002) · doi:10.1038/419343a
[22] Romanel, A., Priami, C.: On the computational power of BlenX. TCS 411(2), 542–565 (2010) · Zbl 1186.68200 · doi:10.1016/j.tcs.2009.09.038
[23] Versari, C.: A core calculus for a comparative analysis of bio-inspired calculi. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 411–425. Springer, Heidelberg (2007) · Zbl 1187.68331 · doi:10.1007/978-3-540-71316-6_28
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.