Methods of information theory and algorithmic complexity for network biology

by H. Zenil, N. Kiani, J. Tegnér
Year:2016

Bibliography

Methods of information theory and algorithmic complexity for network biology
H. Zenil, N. Kiani, J. Tegnér
Seminars of Developmental and Cell Biology March 51: 32-43, 2016

Abstract

​We survey and introduce concepts and tools located at the intersection of information theory and network biology. We show that Shannon's information entropy, compressibility and algorithmic complexity quantify different local and global aspects of synthetic and biological data. We show examples such as the emergence of giant components in Erdös-Rényi random graphs, and the recovery of topological properties from numerical kinetic properties simulating gene expression data. We provide exact theoretical calculations, numerical approximations and error estimations of entropy, algorithmic probability and Kolmogorov complexity for different types of graphs, characterizing their variant and invariant properties. We introduce formal definitions of complexity for both labeled and unlabeled graphs and prove that the Kolmogorov complexity of a labeled graph is a good approximation of its unlabeled Kolmogorov complexity and thus a robust definition of graph complexity.

DOI: 10.1016/j.semcdb.2016.01.011

Methods of information theory and algorithmic complexity for network biology.pdf

Preprint PDF

Early Version PDF

Keywords

Algorithmic probability Algorithmic randomness Biological networks Complex networks Information theory Kolmogorov complexity
KAUST

"KAUST shall be a beacon for peace, hope and reconciliation, and shall serve the people of the Kingdom and the world."

King Abdullah bin Abdulaziz Al Saud, 1924 – 2015

Contact Us

  • 4700 King Abdullah University of Science and Technology

    Thuwal 23955-6900, Kingdom of Saudi Arabia

     

Quick links

© King Abdullah University of Science and Technology. All rights reserved