Algorithmic Complexity and Reprogrammability of Chemical Structure Networks
Abstract
Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of applying a computational interventional calculus based on the principles of algorithmic probability to chemical structure networks. We profile the sensitivity of the elements and covalent bonds in a chemical structure network algorithmically, asking whether reprogrammability affords information about thermodynamic and chemical processes involved in the transformation of different compound classes. We arrive at numerical results suggesting a correspondence between some physical, structural and functional properties. Our methods are capable of separating chemical classes that reflect functional and natural differences without considering any information about atomic and molecular properties. We conclude that these methods, with their links to chemoinformatics via algorithmic, probability hold promise for future research.
An online implementation to estimations of graph complexity is available online at http://www.complexitycalculator.com
References
- 1. , Effect of statins and aspirin alone and in combination on clinical outcome in dyslipidaemic patients with coronary heart disease. A subgroup analysis of the GREACE study, Platelets 16(2) :65–71, 2005. Crossref, ISI, Google Scholar
- 2. , Statistical mechanics of complex networks, Reviews of Modern Physics 74(1) :47–97, 2002. Crossref, ISI, Google Scholar
- 3. , The structure and dynamics of multilayer networks, Physics Reports 544(1) :1–122, 2014. Crossref, ISI, Google Scholar
- 4. , A history of graph entropy measures, Information Sciences 181 :57–78, 2011. Crossref, ISI, Google Scholar
- 5. , The first general index of molecular complexity, J. Am. Chem. SOC. 103 :3599–3601, 1981. Crossref, ISI, Google Scholar
- 6. , On the length of programs for computing finite binary sequences, Journal of the ACM 13(4) :547–569, 1966. Crossref, ISI, Google Scholar
- 7. , Entropy bounds for dendrimers, Applied Mathematics and Computation 242 :462–472, 2014. Crossref, ISI, Google Scholar
- 8. , Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review, Pharmacol Ther. 138(3) :333–408, 2013. Crossref, ISI, Google Scholar
- 9. , Numerical evaluation of the complexity of short strings: A glance into the innermost structure of algorithmic randomness, Applied Mathematics and Computation 219 :63–77, 2012. Crossref, ISI, Google Scholar
- 10. , Molecular complexity: A simplified formula adapted to individual atoms, J. Chem. InJ Comput. Sci. 27(2), 1987. Google Scholar
- 11. , Three approaches to the quantitative definition of information, Problems of Information and Transmission 1(1) :1–7, 1965. Google Scholar
- 12. , Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems of Information Transmission 10(3) :206–210, 1974. Google Scholar
- 13. ,
Predictive systems toxicology , in Orazio Nicolotti (ed.), Computational Toxicology, Methods and Protocols,Methods in Molecular Biology (Springer, 2017), (in press). Google Scholar - 14. , The definition of random sequences, Information and Control, 9 :602–619, 1966. Crossref, Google Scholar
- 15. , Entropy and the complexity of graphs: IV. Entropy measures and graphical structure, Bulletin of Mathematical Biophysics 30 :533–546, 1968. Crossref, Google Scholar
- 16. , A practical overview of quantitative structure-activity relationship, Excli J. 8 :74–88, 2009. ISI, Google Scholar
- 17. , Structure induction by lossless graph compression, Data Compression Conference, DCC ’07,
27–29 March 2007 , pages 53–6. Google Scholar - 18. , On molecular branching, Acta Chim. Slo V. 44 :57–77, 1997. Google Scholar
- 19. , Walk counts, labyrinthicity, and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci. 40(1) :99–106, 2000. Crossref, Google Scholar
- 20. , Correspondence and independence of numerical evaluations of algorithmic information measures, Computability 2(2) :125–140, 2013. Crossref, Google Scholar
- 21. , Calculating Kolmogorov complexity from the frequency output distributions of small turing machines, PLoS One 9(5), e96223, 2014. Crossref, ISI, Google Scholar
- 22. , A formal theory of inductive inference: Parts 1 and 2, Information and Control 7 :1–22 and
224–254 , 1964. Crossref, Google Scholar - 23. N. Siddharth, B. Paige, J-W van de Meent, A. Desmaison, N. D. Goodman, P. Kohli, F. Wood and P. H. S. Torr, Learning disentangled representations with semi-supervised deep generative models, arxiv:1706.00400 [stat.ML], 2017. Google Scholar
- 24. , A New Kind of Science (Wolfram Media, Champaign IL., 2002). Google Scholar
- 25. , Reduction of carboxylic esters to ethers with triethyl silane in the combined use of titanium tetrachloride and trimethylsilyl trifluoromethanesulfonate, Tetrahedron 57(25) :5353–5359, 2001. Crossref, ISI, Google Scholar
- 26. , Graph automorphisms and topological characterization of complex networks by algorithmic information content, Physica A: Statistical Mechanics and Its Applications 404 :341–358, 2014. Crossref, ISI, Google Scholar
- 27. , Two-dimensional Kolmogorov complexity and validation of the coding theorem method by compressibility, PeerJ. Comput. Sci. 1 :e23, 2015. Crossref, Google Scholar
- 28. , Quantifying loss of information in network-based dimensionality reduction techniques, Journal of Complex Networks 4 :342–362, 2016. Crossref, Google Scholar
- 29. , Low-algorithmic-complexity entropy-deceiving graphs, Physical Review E 96 :012308, 2017. Crossref, ISI, Google Scholar
- 30. H. Zenil, S. Hernández-Orozco, N. A. Kiani, F. Soler-Toscano, A. Rueda-Toicen, A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity, arXiv:1609.00110 [cs.IT], 2016. Google Scholar
- 31. H. Zenil, N. A. Kiani, F. Marabita, Y. Deng, S. Elias, A. Schmidt, G. Ball and J. Tegnér, An algorithmic information calculus for causal discovery and reprogramming systems, 2017. BioArXiv Doi:https://doi.org/10.1101/185637. Google Scholar
- 32. H. Zenil, L. Badillo, S. Hernández-Orozco and F. Hernández-Quiroz, Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability, International Journal of Parallel Emergent and Distributed Systems (accepted), arXiv:1711.01711v7 [cs.IT], 2017. Google Scholar
- 33. , Methods of information theory and algorithmic complexity for network biology, Seminars in Cell and Developmental Biology 51 :32–43, 2016. Crossref, ISI, Google Scholar


