Use of Büchi automata and randomness for the description of biological processes

  • Authors

    • Konstantinos Giannakis Department of Informatics, Ionian University, Corfu, Greece
    • Theodore Andronikos Department of Informatics, Ionian University, Corfu, Greece
    2015-03-13
    https://doi.org/10.14419/ijsw.v3i1.4356
  • ω-Automata, Concurrent Systems, Infinite Sequences, Probabilistic Computation, Protein Folding

  • The main topic of this study is the modelling and verification of biological systems using ω-automata. This work focuses on the protein folding problem and the infinite behaviour it features in many cases. Specifically, stochastic computational models with infinite input are used in this paper’s approach and indicative aspects of a biological problem are presented using both ω-automata and probabilistic Büchi automata (PBAs), making a novel attempt to establish their use in reasoning about biological processes. Necessary preliminary definitions and background towards this direction are provided. Finally, the pros and cons of each model are shown through examples. Overall, this work contributes by combining for the very first time PBAs with real biological mechanisms, with indicative examples, both with PBAs and NBAs (non-deterministic Büchi automata).

  • References

    1. [1] M. Sipser. Introduction to the Theory of Computation. Thomson Course Technology, 2nd edition, 2006.

      [2] J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2nd edition, 2000.

      [3] H. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 2nd edition, 1997.

      [4] A. Sadot, J. Fisher, D. Barak, Y. Admanit, M. J. Stern, E. J. A. Hubbard, and D. Harel. Toward verified biological models. Computational Biology and Bioinformatics, IEEE/ACM Transactions on, 5(2):223-234, 2008.

      [5] L. M. Adleman et al. Molecular computation of solutions to combinatorial problems. Science-AAAS-Weekly Paper Edition, 266(5187):1021-1023, 1994.

      [6] G. Păun , G. Rozenberg, and A. Salomaa. DNA computing: new computing paradigms. Springer, 1998.

      [7] J. R. Büchi. Weak second-order arithmetic and finite automata. In Zeitschrift fr mathematische Logik und Grundlagen der Mathematik. 1960.

      [8] J. R. Büchi. On a decision method in restricted second-order arithmetic. In Proceedings of the 1960 International Congress for the Logic, Methodology and Philosophy of Science, pages 1-11. Stanford University Press, 1962.

      [9] M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, (141):1-35, 1969.

      [10] M. O. Rabin. Automata on infinite objects and Church's problem. Number 13. Amer Mathematical Society, 1972.

      [11] S. Safra. On the complexity of omega-automata. In Proceedings of the 29th Symposium on Foundations of Computer Science (FOCS88), pages 319-327. IEEE Computer Society, 1988.

      [12] W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer-Verlag, 1996.

      [13] W. Thomas. Automata on infinite objects. In Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 133-192. Elsevier Science, 1990.

      [14] W. Thomas. Complementation of Büchi automata revisited. In Contributions on Theoretical Computer Science in Honor of Arto Saloma, pages 109-120. Springer-Verlag, 1999.

      [15] E. Gradel, W. Thomas, and T. Wilke. Automata, logics, and infinite games: a guide to current research. Springer, 2002.

      [16] W. Thomas and H. Lescow. Logical specifications of infinite computations. A Decade of Concurrency Reflections and Perspectives, pages 583-621, 1994.

      [17] R. McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, (9):521-530, 1966.

      [18] M. Y. Vardi. An automata-theoretic approach to linear temporal logic. In Ban Higher Order Workshop, pages 238-266. Springer-Verlag, 1995.

      [19] M.Y. Vardi and P. Wolper. An automata-theoretic approach to automatic program verification. In Proceedings of the First Symposium on Logic in Computer Science, pages 322-331, 1986.

      [20] M.Y. Vardi. Automatic verification of probabilistic concurrent finite state programs. In FOCS, pages 327-338, 1985.

      [21] M. Y. Vardi and P. Wolper. Reasoning about infinite computations. Information and Computation, 115(1):1-37, 1994.

      [22] K. Giannakis and T. Andronikos. Querying linked data and Büchi automata. In Semantic and Social Media Adaptation and Personalization (SMAP), 2014 9th International Workshop on, pages 110-114. IEEE, 2014.

      [23] M. O. Rabin. Probabilistic automata. Information and Control, (6):230-245, 1963.

      [24] A. Paz. Introduction to probabilistic automata. Academic Press, Inc., Orlando, FL, USA, 1971.

      [25] C. Courcoubetis and M. Yannakakis. The complexity of probabilistic verification. Journal of the ACM, 42(4):857-907, 1995.

      [26] L. De Alfaro. Formal verification of probabilistic systems. PhD thesis, Stanford University, Department of Computer Science, 1997.

      [27] O. Goldreich. Randomized methods in computation. Lecture Notes. http://www. wisdom. weizmann. ac.il/~oded/rnd-sum. html, 2001.

      [28] H. Gimbert and Y. Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In Automata, Languages and Programming, pages 527-538. Springer, 2010.

      [29] C. Baier, N. Bertrand, and M. Grosser. On decision problems for probabilistic Büchi automata. In FOSSACS, pages 287-301. Springer, 2008.

      [30] C. Baier and M. Grosser. Recognizing ω-regular languages with probabilistic automata. In LICS, pages 137-146, 2005.

      [31] C. Baier, N. Bertrand, and M. Grosser. Probabilistic automata over infinite words: Expressiveness, efficiency, and decidability. In DCFS, volume 3 of EPTCS, pages 3-16, 2009.

      [32] C. Baier, M. Grosser, and N. Bertrand. Probabilistic ω-automata. Journal of the ACM, 59(1):1-52, 2012.

      [33] C. Baier, N. Bertrand, and M. Grosser. Probabilistic acceptors for languages over infinite words. In M. Nielsen et al., editor, SOFSEM, volume 5404 of Lecture Notes in Computer Science, pages 19-33. Springer-Verlag, 2009.

      [34] C. Baier, N. Bertrand, and M. Grosser. The effect of tossing coins in omega-automata. In M. Bravetti and G. Zavattaro, editors, CONCUR, volume 5710, of Lecture Notes in Computer Science, pages 15-29. Springer-Verlag, 2009.

      [35] T. Weidner. Probabilistic automata and probabilistic logic. In V. Sassone B. Rovan and P. Widmayer, editors, MFCS 2012, pages 813-824. Springer-Verlag, 2012.

      [36] T. Weidner. Probabilistic ω-regular expressions. In Language and Automata Theory and Applications, pages 588-600. Springer, 2014.

      [37] J. Fisher, D. Harel, and T. A. Henzinger. Biology as reactivity. Communications of the ACM, 54(10):72-82, 2011.

      [38] D. Harel, Y. Setty, S. Efroni, N. Swerdlin, and I. R. Cohen. Concurrency in biological modeling: Behavior, execution and visualization. Electronic Notes in Theoretical Computer Science, 194(3):119-131, 2008.

      [39] S. K. Jha, E. M. Clarke, C. J. Langmead, A. Legay, A. Platzer, and P. Zuliani. A bayesian approach to model checking biological systems. In Computational Methods in Systems Biology, pages 218-234. Springer, 2009.

      [40] R. Freund, M. Oswald, and L. Staiger. ω-p automata with communication rules. In C. Martin-Vide, G. Mauri, G. Păun , G. Rozenberg, and A. Salomaa, editors, Membrane Computing, volume 2933 of Lecture Notes in Computer Science, pages 203-217. Springer Berlin Heidelberg, 2004.

      [41] G. Păun . Computing with membranes. Journal of Computer and System Sciences, 61(1):108-143, 2000.

      [42] E. Petre. Watson-crick ω-automata. Journal of Automata, anguages and Combinatorics, 8(1):59-70, 2003.

      [43] R. Freund, Gh Păun , G. Rozenberg, and A Salomaa. Watson-crick finite automata. DNA Based Computers Three, 48:297, 1999.

      [44] K. Giannakis and T. Andronikos. Mitochondrial fusion through membrane automata. In GeNeDis 2014, pages 163-172. Springer, 2015.

      [45] A. Li and V. Daggett. Identication and characterization of the unfolding transition state of chymotrypsin inhibitor 2 by molecular dynamics simulations. Journal of molecular biology, 257(2):412-429, 1996.

      [46] C. M. Dobson. Protein folding and misfolding. Nature, 426(6968):884-890, 2003.

      [47] F. U. Hartl. Chaperone-assisted protein folding: the path to discovery from a personal perspective. Nature medicine, 17(10):1206-1210, 2011.

      [48] A. L. Horwich. Protein folding in the cell: an inside story. Nature medicine, 17(10):1211-1216, 2011.

      [49] Y. Kang and C. M. Fortmann. An alternative approach to protein folding. BioMed research international, 2013, 2013.

      [50] S. W. Englander, L. Mayne, and M. M. G. Krishna. Protein folding and misfolding: mechanism and principles. Quarterly reviews of biophysics, 40(04):287-326, 2007.

      [51] Y.-F. Shen, B. Li, and Z.-P. Liu. Protein structure alignment based on internal coordinates. Interdisciplinary Sciences: Computational Life Sciences, 2(4):308-319, 2010.

      [52] D. Baker and A. Sali. Protein structure prediction and structural genomics. Science, 294(5540):93-96, 2001.

      [53] J.-M. Chandonia and S. E. Brenner. The impact of structural genomics: expectations and outcomes. Science, 311(5759):347-351, 2006.

      [54] H. A. Scheraga, M. Khalili, and A. Liwo. Protein-folding dynamics: overview of molecular simulation techniques. Annu. Rev. Phys. Chem., 58:57-83, 2007.

      [55] Timo Koski. Hidden Markov models for bioinformatics, volume 2. Springer, 2001.

      [56] H. Ding, H Lin, W. Chen, Z.-Q. Li, F.-B. Guo, J. Huang, and N. Rao. Prediction of protein structural classes based on feature selection technique. Interdisciplinary Sciences: Computational Life Sciences, 6(3):235-240, 2014.

      [57] M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM journal of research and development, 3(2):114-125, 1959.

      [58] B. H. Toyama and M. W. Hetzer. Protein homeostasis: live long, won't prosper. Nature Reviews Molecular Cell Biology, 14(1):55-61, 2013.

      [59] B. Alberts, D. Bray, K. Hopkin, A. Johnson, J. Lewis, M. Ra, K. Roberts, and P. Walter. Essential cell biology. Garland Science, 2013.

      [60] D. J. Selkoe. Folding proteins in fatal ways. Nature, 426(6968):900-904, 2003.
      [61] A. L. Goldberg. Protein degradation and protection against misfolded or damaged proteins. Nature, 426(6968):895-899, 2003.

      [62] H. Chen and D. C. Chan. Mitochondrial dynamics-fusion, fission, movement, and mitophagy-in neurodegenerative diseases. Human molecular genetics, 18(R2):R169-R176, 2009.

      [63] A. M. van der Bliek, Q. Shen, and S. Kawajiri. Mechanisms of mitochondrial fission and fusion. Cold Spring Harbor perspectives in biology, 5(6), 2013.

      [64] D. L. Longo and S. L. Archer. Mitochondrial dynamics-mitochondrial fission and fusion in human diseases. New England Journal of Medicine, 369(23):2236-2251, 2013.

      [65] Y. M. Li. Finite automata based on quantum logic and monadic second-order quantum logic. Sci China Inf Sci, (53):101-114, 2010.

  • Downloads

  • How to Cite

    Giannakis, K., & Andronikos, T. (2015). Use of Büchi automata and randomness for the description of biological processes. International Journal of Scientific World, 3(1), 113-123. https://doi.org/10.14419/ijsw.v3i1.4356