World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Algorithmic Complexity and Reprogrammability of Chemical Structure Networks

    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. V. G. Athyros, D. P. Mikhailidis, A. A. Papageorgiou, V. I. Bouloukos, A. N. Pehlivanidis, A. N. Symeonidis, A. I. Kakafika, S. S. Daskalopoulou and M. Elisaf, 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, ISIGoogle Scholar
    • 2. R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics 74(1) :47–97, 2002. Crossref, ISIGoogle Scholar
    • 3. S.  Boccaletti et al., The structure and dynamics of multilayer networks, Physics Reports 544(1) :1–122, 2014. Crossref, ISIGoogle Scholar
    • 4. M. Dehmer and A. Mowshowitz, A history of graph entropy measures, Information Sciences 181 :57–78, 2011. Crossref, ISIGoogle Scholar
    • 5. S. H. Bertz, The first general index of molecular complexity, J. Am. Chem. SOC. 103 :3599–3601, 1981. Crossref, ISIGoogle Scholar
    • 6. G. J. Chaitin, On the length of programs for computing finite binary sequences, Journal of the ACM 13(4) :547–569, 1966. Crossref, ISIGoogle Scholar
    • 7. Z. Chen, M. Dehmer, F. Emmert-Streib and Y. Shi, Entropy bounds for dendrimers, Applied Mathematics and Computation 242 :462–472, 2014. Crossref, ISIGoogle Scholar
    • 8. P. Csermely, T. Korcsmáros, H. J. Kiss, G. London and R. Nussinov, Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review, Pharmacol Ther. 138(3) :333–408, 2013. Crossref, ISIGoogle Scholar
    • 9. J.-P. Delahaye and H. Zenil, 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, ISIGoogle Scholar
    • 10. J. B. Hendrickson, P. Huang and A. Glenn Toczo, Molecular complexity: A simplified formula adapted to individual atoms, J. Chem. InJ Comput. Sci. 27(2), 1987. Google Scholar
    • 11. A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information and Transmission 1(1) :1–7, 1965. Google Scholar
    • 12. L. A. Levin, 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. N. A. Kiani, M. Shang, H. Zenil and J. Tegnér, Predictive systems toxicology, in Orazio Nicolotti (ed.), Computational Toxicology, Methods and Protocols, Methods in Molecular Biology (Springer, 2017), (in press). Google Scholar
    • 14. P. Martin-Löf, The definition of random sequences, Information and Control, 9 :602–619, 1966. CrossrefGoogle Scholar
    • 15. A. Mowshowitz, Entropy and the complexity of graphs: IV. Entropy measures and graphical structure, Bulletin of Mathematical Biophysics 30 :533–546, 1968. CrossrefGoogle Scholar
    • 16. C. Nantasenamat, C. Isarankura-Na-Ayudhya, T. Naenna and V. Prachayasittikul, A practical overview of quantitative structure-activity relationship, Excli J. 8 :74–88, 2009. ISIGoogle Scholar
    • 17. L. Peshkin, Structure induction by lossless graph compression, Data Compression Conference, DCC ’07, 27–29 March 2007, pages 53–6. Google Scholar
    • 18. M. Randić, On molecular branching, Acta Chim. Slo V. 44 :57–77, 1997. Google Scholar
    • 19. G. Rücker and C. Rücker, Walk counts, labyrinthicity, and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci. 40(1) :99–106, 2000. CrossrefGoogle Scholar
    • 20. F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Correspondence and independence of numerical evaluations of algorithmic information measures, Computability 2(2) :125–140, 2013. CrossrefGoogle Scholar
    • 21. F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Calculating Kolmogorov complexity from the frequency output distributions of small turing machines, PLoS One 9(5), e96223, 2014. Crossref, ISIGoogle Scholar
    • 22. R. J. Solomonoff, A formal theory of inductive inference: Parts 1 and 2, Information and Control 7 :1–22 and 224–254, 1964. CrossrefGoogle 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. S. Wolfram, A New Kind of Science (Wolfram Media, Champaign IL., 2002). Google Scholar
    • 25. M. Yato, K. Homma and A. Ishida, 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, ISIGoogle Scholar
    • 26. H. Zenil, F. Soler-Toscano, K. Dingle and A. Louis, Graph automorphisms and topological characterization of complex networks by algorithmic information content, Physica A: Statistical Mechanics and Its Applications 404 :341–358, 2014. Crossref, ISIGoogle Scholar
    • 27. H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit, Two-dimensional Kolmogorov complexity and validation of the coding theorem method by compressibility, PeerJ. Comput. Sci. 1 :e23, 2015. CrossrefGoogle Scholar
    • 28. H. Zenil, N. A. Kiani and J. Tegnér, Quantifying loss of information in network-based dimensionality reduction techniques, Journal of Complex Networks 4 :342–362, 2016. CrossrefGoogle Scholar
    • 29. H. Zenil, N. A. Kiani and J. Tegnér, Low-algorithmic-complexity entropy-deceiving graphs, Physical Review E 96 :012308, 2017. Crossref, ISIGoogle 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. H. Zenil, N. A. Kiani and J. Tegnér, Methods of information theory and algorithmic complexity for network biology, Seminars in Cell and Developmental Biology 51 :32–43, 2016. Crossref, ISIGoogle Scholar