Abstract
We develop a GPU based technique to analyze bio-pathway models consisting of systems of ordinary differential equations (ODEs). A key component in our technique is an online procedure for verifying whether a numerically generated trajectory of a model satisfies a property expressed in bounded linear temporal logic. Using this procedure, we construct a statistical model checking algorithm which exploits the massive parallelism offered by GPUs while respecting the severe constraints imposed by their memory hierarchy and the hardware execution model. To demonstrate the computational power of our method, we use it to solve the parameter estimation problem for bio-pathway models. With three realistic benchmarks, we show that the proposed technique is computationally efficient and scales well with the number of GPU units deployed. Since both the verification framework and the computational platform are generic, our scheme can be used to solve a variety of analysis problems for models consisting of large systems of ODEs.
This research was supported by the Singapore MOE grant MOE2013-T2-2-033.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Source code available at https://www.comp.nus.edu.sg/~rpsysbio/smcgpu/.
References
Barnat, J., Brim, L., Cerná, I., Drazan, S., Fabriková, J., Láník, J., Safránek, D., Ma, H.: Biodivine: A framework for parallel analysis of biological models. In: Proceedings Second International Workshop on Computational Models for Cell Processes, COMPMOD 2009, Eindhoven, The Netherlands, 3 November 2009, pp. 31–45 (2009)
Barnat, J., Brim, L., Ceska, M., Lamr, T.: Cuda accelerated LTL model checking. In: 2009 15th International Conference on Parallel and Distributed Systems (ICPADS), pp. 34–41. IEEE (2009)
Barre, B., Klein, M., Soucy-Boivin, M., Ollivier, P.-A., Hallé, S.: MapReduce for parallel trace validation of LTL properties. In: Qadeer, S., Tasiran, S. (eds.) RV 2012. LNCS, vol. 7687, pp. 184–198. Springer, Heidelberg (2013)
Biere, A., Cimatti, A., Clarke, E., Zhu, Y.: Symbolic model checking without BDDs. In: Cleaveland, W.R. (ed.) TACAS 1999. LNCS, vol. 1579, p. 193. Springer, Heidelberg (1999)
Bortolussi, L., Sanguinetti, G.: Learning and designing stochastic processes from logical constraints. In: Joshi, K., Siegle, M., Stoelinga, M., D’Argenio, P.R. (eds.) QEST 2013. LNCS, vol. 8054, pp. 89–105. Springer, Heidelberg (2013)
Brown, K.S., Hill, C.C., Calero, G.A., Myers, C.R., Lee, K.H., Sethna, J.P., Cerione, R.A.: The statistical mechanics of complex signaling networks: nerve growth factor signaling. Phys. Biol. 1(3), 184 (2004)
Bulychev, P., David, A., Larsen, K.G., Mikučionis, M., Poulsen, D.B., Legay, A., Wang, Z.: Uppaal-smc: Statistical model checking for priced timed automata. arXiv preprint arXiv:1207.1272 (2012)
Clarke, E.M., Faeder, J.R., Langmead, C.J., Harris, L.A., Jha, S.K., Legay, A.: Statistical model checking in BioLab: applications to the automated analysis of T-cell receptor signaling pathway. In: Heiner, M., Uhrmacher, A.M. (eds.) CMSB 2008. LNCS (LNBI), vol. 5307, pp. 231–250. Springer, Heidelberg (2008)
David, A., Du, D., Guldstrand Larsen, K., Legay, A., Mikučionis, M.: Optimizing control strategy using statistical model checking. In: Brat, G., Rungta, N., Venet, A. (eds.) NFM 2013. LNCS, vol. 7871, pp. 352–367. Springer, Heidelberg (2013)
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107–113 (2008)
Goldbeter, A., Pourquié, O.: Modeling the segmentation clock as a network of coupled oscillations in the Notch, Wnt and FGF signaling pathways. J. Theoret. Biol. 252(3), 574–585 (2008)
Gyori, B.M., Liu, B., Paul, S., Ramanathan, R., Thiagarajan, P.: Approximate probabilistic verification of hybrid systems. In: Abate, A., Sǎfránek, D. (eds.) HSB 2015. LNCS (LNBI), vol. 9271, pp. 96–116. Springer, Heidelberg (2015)
Hagiescu, A., Liu, B., Ramanathan, R., Palaniappan, S.K., Cui, Z., Chattopadhyay, B., Thiagarajan, P., Wong, W.F.: GPU code generation for ode-based applications with phased shared-data access patterns. ACM Trans. Archit. Code Optim. (TACO) 10(4), 55 (2013)
Hindmarsh, A., Brown, P., Grant, K., Lee, S., Serban, R., Shumaker, D., Woodward, C.: SUNDIALS: Suite of nonlinear and differential/algebraic equation solvers. ACM T. Math. Softw. 31(3), 363–396 (2005)
Hirsch, M., Smale, S., Devaney, R.: Differential equations, dynamical systems, and an introduction to chaos. Academic Press, New York (2012)
Jha, S.K., Langmead, C.J.: Synthesis and infeasibility analysis for stochastic models of biochemical systems using statistical model checking and abstraction refinement. Theoret. Comput. Sci. 412(21), 2162–2187 (2011)
Klipp, E., Herwig, R., Kowald, A., Wierling, C., Lehrach, H.: Systems Biology in Practice: Concepts, Implementation and Application. Wiley-VCH, Weinheim (2005)
Kuhtz, L., Finkbeiner, B.: Efficient parallel path checking for linear-time temporal logic with past and bounds. arXiv preprint arXiv:1210.0574 (2012)
Lambert, J.D.: Numerical Methods for Ordinary Differential Systems: The Initial Value Problem. Wiley, Chichester (1991)
Le Novere, N., Bornstein, B., Broicher, A., Courtot, M., Donizelli, M., Dharuri, H., Li, L., Sauro, H., Schilstra, M., Shapiro, B., Snoep, J., Hucka, M.: BioModels database: a free, centralized database of curated, published, quantitative kinetic models of biochemical and cellular systems. Nucleic Acids Res. 34, D689–D691 (2006)
Legay, A., Delahaye, B., Bensalem, S.: Statistical model checking: an overview. In: Barringer, H., et al. (eds.) RV 2010. LNCS, vol. 6418, pp. 122–135. Springer, Heidelberg (2010)
Lindholm, E., Nickolls, J., Oberman, S., Montrym, J.: Nvidia tesla: a unified graphics and computing architecture. IEEE Micro 28(2), 39–55 (2008)
Liu, B., Hagiescu, A., Palaniappan, S.K., Chattopadhyay, B., Cui, Z., Wong, W.F., Thiagarajan, P.: Approximate probabilistic analysis of biopathway dynamics. Bioinformatics 28(11), 1508–1516 (2012)
Maeda, A., Ozaki, Y.I., Sivakumaran, S., Akiyama, T., Urakubo, H., Usami, A., Sato, M., Kaibuchi, K., Kuroda, S.: Ca2+-independent phospholipase A2-dependent sustained Rho-kinase activation exhibits all-or-none response. Genes to Cells 11(9), 1071–1083 (2006)
Maedo, A., Ozaki, Y., Sivakumaran, S., Akiyama, T., Urakubo, H., Usami, A., Sato, M., Kaibuchi, K., Kuroda, S.: Ca\(^{2+}\)-independent phospholipase A2-dependent sustained Rho-kinase activation exhibits all-or-none response. Genes Cells 11, 1071–1083 (2006)
Moles, C.G., Mendes, P., Banga, J.R.: Parameter estimation in biochemical pathways: a comparison of global optimization methods. Genome Res. 13(11), 2467–2474 (2003)
Murray, L.: GPU acceleration of Runge-Kutta integrators. IEEE Trans. Parallel Distrib. Syst. 23(1), 94–101 (2012)
Oshima, K., Matsumoto, T., Fujita, M.: Hardware implementation of BLTL property checkers for acceleration of statistical model checking. In: Proceedings of the International Conference on Computer-Aided Design, pp. 670–676. IEEE Press (2013)
Palaniappan, S.K., Gyori, B.M., Liu, B., Hsu, D., Thiagarajan, P.S.: Statistical model checking based calibration and analysis of bio-pathway models. In: Gupta, A., Henzinger, T.A. (eds.) CMSB 2013. LNCS, vol. 8130, pp. 120–134. Springer, Heidelberg (2013)
Runarsson, T.P., Yao, X.: Stochastic ranking for constrained evolutionary optimization. IEEE Trans. Evol. Comput. 4(3), 284–294 (2000)
Sen, K., Viswanathan, M., Agha, G.: On statistical model checking of stochastic systems. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 266–280. Springer, Heidelberg (2005)
Wald, A.: Sequential tests of statistical hypotheses. Ann. Math. Stat. 16, 117–186 (1945)
Younes, H.L., Kwiatkowska, M., Norman, G., Parker, D.: Numerical vs. statistical probabilistic model checking. Int. J. Softw. Tools Technol. Transfer 8(3), 216–228 (2006)
Younes, H.L., Simmons, R.G.: Statistical probabilistic model checking with a focus on time-bounded properties. Inf. Comput. 204(9), 1368–1409 (2006)
Zhou, Y., Liepe, J., Sheng, X., Stumpf, M.P., Barnes, C.: GPU accelerated biochemical network simulation. Bioinformatics 27(6), 874–876 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Ramanathan, R., Zhang, Y., Zhou, J., Gyori, B.M., Wong, WF., Thiagarajan, P.S. (2015). Parallelized Parameter Estimation of Biological Pathway Models. In: Abate, A., Šafránek, D. (eds) Hybrid Systems Biology. HSB 2015. Lecture Notes in Computer Science(), vol 9271. Springer, Cham. https://doi.org/10.1007/978-3-319-26916-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-26916-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26915-3
Online ISBN: 978-3-319-26916-0
eBook Packages: Computer ScienceComputer Science (R0)