Building mathematical models of cellular networks lies at the core of systems biology. It involves, among other tasks, the reconstruction of the structure of interactions between molecular components, which is known as network inference or reverse engineering. Information theory can help in the goal of extracting as much information as possible from the available data. A large number of methods founded on these concepts have been proposed in the literature, not only in biology journals, but in a wide range of areas. Their critical comparison is difficult due to the different focuses and the adoption of different terminologies. Here we attempt to review some of the existing information theoretic methodologies for network inference, and clarify their differences. While some of these methods have achieved notable success, many challenges remain, among which we can mention dealing with incomplete measurements, noisy data, counterintuitive behaviour emerging from nonlinear relations or feedback loops, and computational burden of dealing with large data sets.
References
[1]
Kitano, H. Foundations of Systems Biology; MIT Press: Cambridge, MA, USA, 2001.
[2]
Arkin, A.; Schaffer, D. Network news: Innovations in 21st century systems biology. Cell 2011, 144, 844–849, doi:10.1016/j.cell.2011.03.008. 21414475
[3]
Gray, R. Entropy and Information Theory; Springer-Verlag: New York, NY, USA, 2009.
[4]
Shannon, C. A mathematical theory of communication. Bell Syst. Tech. J. 1948, 27, 379–423, doi:10.1002/j.1538-7305.1948.tb01338.x.
[5]
Quastler, H. Information Theory in Biology; University of Illinois Press: Urbana, IL, USA, 1953.
[6]
Bekey, G.; Beneken, J. Identification of biological systems: A survey. Automatica 1978, 14, 41–47, doi:10.1016/0005-1098(78)90075-4.
[7]
D'haeseleer, P.; Liang, S.; Somogyi, R. Genetic network inference: From co-expression clustering to reverse engineering. Bioinformatics 2000, 16, 707–726, doi:10.1093/bioinformatics/16.8.707. 11099257
[8]
Crampin, E.; Schnell, S.; McSharry, P. Mathematical and computational techniques to deduce complex biochemical reaction mechanisms. Prog. Biophys. Mol. Biol. 2004, 86, 77–112, doi:10.1016/j.pbiomolbio.2004.04.002. 15261526
[9]
Ross, J. Determination of complex reaction mechanisms. Analysis of chemical, biological and genetic networks. J. Phys. Chem. A 2008, 112, 2134–2143, doi:10.1021/jp711313e. 18275175
[10]
De Jong, H. Modeling and simulation of genetic regulatory systems: A literature review. J. Comput. Biol. 2002, 9, 67–103, doi:10.1089/10665270252833208. 11911796
[11]
Cho, K.; Choo, S.; Jung, S.; Kim, J.; Choi, H.; Kim, J. Reverse engineering of gene regulatory networks. IET Syst. Biol. 2007, 1, 149–163, doi:10.1049/iet-syb:20060075. 17591174
Hecker, M.; Lambeck, S.; Toepfer, S.; van Someren, E.; Guthke, R. Gene regulatory network inference: Data integration in dynamic models–A review. Biosystems 2009, 96, 86–103, doi:10.1016/j.biosystems.2008.12.004. 19150482
[14]
López-Kleine, L.; Leal, L.; López, C. Biostatistical approaches for the reconstruction of gene co-expression networks based on transcriptomic data. Brief. Funct. Genomics 2013, doi:10.1093/bfgp/elt003.
[15]
Koyutürk, M. Algorithmic and analytical methods in network biology. WIREs Syst. Biol. Med. 2009, 2, 277–292.
[16]
De Smet, R.; Marchal, K. Advantages and limitations of current network inference methods. Nat. Rev. Microbiol. 2010, 8, 717–729. 20805835
[17]
Soranzo, N.; Bianconi, G.; Altafini, C. Comparing association network algorithms for reverse engineering of large-scale gene regulatory networks: Synthetic versus real data. Bioinformatics 2007, 23, 1640–1647, doi:10.1093/bioinformatics/btm163. 17485431
[18]
Altay, G.; Emmert-Streib, F. Revealing differences in gene network inference algorithms on the network level by ensemble methods. Bioinformatics 2010, 26, 1738–1744, doi:10.1093/bioinformatics/btq259. 20501553
[19]
Bansal, M.; Belcastro, V.; Ambesi-Impiombato, A.; di Bernardo, D. How to infer gene networks from expression profiles. Mol. Syst. Biol. 2007, 3, 78:1–78:10.
[20]
Hurley, D.; Araki, H.; Tamada, Y.; Dunmore, B.; Sanders, D.; Humphreys, S.; Affara, M.; Imoto, S.; Yasuda, K.; Tomiyasu, Y.; et al. Gene network inference and visualization tools for biologists: Application to new human transcriptome datasets. Nucleic Acids Res. 2012, 40, 2377–2398, doi:10.1093/nar/gkr902. 22121215
[21]
Walter, E.; Pronzato, L. Identification of parametric models from experimental data. In Communications and Control Engineering Series; Springer: London, UK, 1997.
[22]
Ljung, L. System Identification: Theory for the User; Prentice Hall: Upper Saddle River, NJ, USA, 1999.
[23]
Galton, F. Regression towards mediocrity in hereditary stature. J. Anthropol. Inst. Great Brit. Ire. 1886, 15, 246–263, doi:10.2307/2841583.
[24]
Stigler, S. Francis Galton's account of the invention of correlation. Stat. Sci. 1989, 4, 73–79, doi:10.1214/ss/1177012580.
[25]
Samoilov, M. Reconstruction and functional analysis of general chemical reactions and reaction networks. PhD thesis, Stanford University, Stanford, CA, USA, 1997.
[26]
Samoilov, M.; Arkin, A.; Ross, J. On the deduction of chemical reaction pathways from measurements of time series of concentrations. Chaos 2001, 11, 108–114, doi:10.1063/1.1336499. 12779446
[27]
Linfoot, E. An informational measure of correlation. Inf. Control 1957, 1, 85–89.
[28]
Cover, T.; Thomas, J. Elements of Information Theory; Wiley: New York, NY, USA, 1991.
[29]
Numata, J.; Ebenh？h, O.; Knapp, E. Measuring correlations in metabolomic networks with mutual information. Genome Inform. 2008, 20, 112–122. 19425127
[30]
Steuer, R.; Kurths, J.; Daub, C.; Weise, J.; Selbig, J. The mutual information: Detecting and evaluating dependencies between variables. Bioinformatics 2002, 18, S231–S240, doi:10.1093/bioinformatics/18.suppl_2.S231. 12386007
[31]
Fraser, A.; Swinney, H. Independent coordinates for strange attractors from mutual information. Phys. Rev. A 1986, 33, 1134–1140, doi:10.1103/PhysRevA.33.1134. 9896728
[32]
Cellucci, C.; Albano, A.; Rapp, P. Statistical validation of mutual information calculations: Comparison of alternative numerical algorithms. Phys. Rev. E 2005, 71, 066208:1–066208:14.
[33]
Moon, Y.; Rajagopalan, B.; Lall, U. Estimation of mutual information using kernel density estimators. Phys. Rev. E 1995, 52, 2318–2321, doi:10.1103/PhysRevE.52.2318.
[34]
Hausser, J.; Strimmer, K. Entropy inference and the James-Stein estimator, with application to nonlinear gene association networks. J. Mach. Learn. Res. 2009, 10, 1469–1484.
[35]
Olsen, C.; Meyer, P.; Bontempi, G. On the impact of entropy estimation on transcriptional regulatory network inference based on mutual information. EURASIP J. Bioinform. Syst. Biol. 2009, 2009, 308959:1–308959:9.
[36]
De Matos Simoes, R.; Emmert-Streib, F. Influence of statistical estimators of mutual information and data heterogeneity on the inference of gene regulatory networks. PLoS One 2011, 6, e29279:1–e29279:14.
[37]
Rissanen, J. Modeling by shortest data description. Automatica 1978, 14, 465–471, doi:10.1016/0005-1098(78)90005-5.
[38]
Margolin, A.; Wang, K.; Califano, A.; Nemenman, I. Multivariate dependence and genetic networks inference. IET Syst. Biol. 2010, 4, 428–440, doi:10.1049/iet-syb.2010.0009. 21073241
[39]
Marko, H. Information theory and cybernetics. IEEE Spectrum 1967, 4, 75–83.
[40]
Marko, H. The bidirectional communication theory–a generalization of information theory. IEEE Trans. Commun. 1973, 21, 1345–1351, doi:10.1109/TCOM.1973.1091610.
[41]
Massey, J. Causality, feedback and directed information. Proceedings of the International Symposium on Information Theory and Its Applications (ISITA-90), Hawaii, HA, USA, 27–30 November 1990; pp. 303–305.
[42]
Tsallis, C. Possible generalization of Boltzmann-Gibbs statistics. J. Stat. Phys. 1988, 52, 479–487, doi:10.1007/BF01016429.
[43]
Tsallis, C.; Gell-Mann, M.; Sato, Y. Asymptotically scale-invariant occupancy of phase space makes the entropy Sq extensive. Proc. Natl. Acad. Sci. USA 2005, 102, 15377–15382, doi:10.1073/pnas.0503807102. 16230624
[44]
Tsallis, C. Entropic nonextensivity: A possible measure of complexity. Chaos Soliton Fract. 2002, 13, 371–391, doi:10.1016/S0960-0779(01)00019-4.
[45]
Barabási, A.; Albert, R. Emergence of scaling in random networks. Science 1999, 286, 509–512, doi:10.1126/science.286.5439.509. 10521342
[46]
Barabási, A. Scale-free networks: A decade and beyond. Science 2009, 325, 412–413, doi:10.1126/science.1173299. 19628854
[47]
Farber, R.; Lapedes, A.; Sirotkin, K. Determination of eukaryotic protein coding regions using neural networks and information theory. J. Mol. Biol. 1992, 226, 471–479, doi:10.1016/0022-2836(92)90961-I. 1640461
[48]
Korber, B.; Farber, R.; Wolpert, D.; Lapedes, A. Covariation of mutations in the V3 loop of human immunodeficiency virus type 1 envelope protein: an information theoretic analysis. Proc. Natl. Acad. Sci. USA 1993, 90, 7176–7180, doi:10.1073/pnas.90.15.7176. 8346232
[49]
Liang, S.; Fuhrman, S.; Somogyi, R. REVEAL, a general reverse engineering algorithm for inference of genetic network architectures. Proceedings of the Pacific Symposium on Biocomputing, Hawaii, HA, USA, 4–9 January 1998; Volume 3, pp. 18–29.
[50]
Michaels, G.; Carr, D.; Askenazi, M.; Fuhrman, S.; Wen, X.; Somogyi, R. Cluster analysis and data visualization of large scale gene expression data. Proceedings of the Pacific Symposium on Biocomputing, Hawaii, HA, USA, 4–9 January 1998; Volume 3, pp. 42–53.
[51]
Butte, A.; Kohane, I. Mutual information relevance networks: Functional genomic clustering using pairwise entropy measurements. Proceedings of the Pacific Symposium on Biocomputing, Hawaii, HA, USA, 4–9 January 2000; Volume 5, pp. 418–429.
[52]
Butte, A.; Tamayo, P.; Slonim, D.; Golub, T.; Kohane, I. Discovering functional relationships between RNA expression and chemotherapeutic susceptibility using relevance networks. Proc. Natl. Acad. Sci. USA 2000, 97, 12182–12186, doi:10.1073/pnas.220392197. 11027309
[53]
Stuart, J.; Segal, E.; Koller, D.; Kim, S. A gene-coexpression network for global discovery of conserved genetic modules. Science 2003, 302, 249–255, doi:10.1126/science.1087447. 12934013
Adami, C. Information theory in molecular biology. Phys. Life Rev. 2004, 1, 3–22.
[56]
Arkin, A.; Ross, J. Statistical Construction of chemical reaction mechanisms from measured time-series. J. Phys. Chem. 1995, 99, 970–979, doi:10.1021/j100003a020.
[57]
Arkin, A.; Shen, P.; Ross, J. A test case of correlation metric construction of a reaction pathway from measurements. Science 1997, 277, 1275–1279, doi:10.1126/science.277.5330.1275.
[58]
Wahl, S.; Haunschild, M.; Oldiges, M.; Wiechert, W. Unravelling the regulatory structure of biochemical networks using stimulus response experiments and large-scale model selection. Syst. Biol. 2006, 153, 275–285, doi:10.1049/ip-syb:20050089.
[59]
Villaverde, A.F.; Ross, J.; Morán, F.; Banga, J.R. MIDER: Network inference with Mutual Information Distance and Entropy Reduction. 2013. Available online: http://www.iim.csic.es/gingproc/mider.html/ (accessed on 6 May 2013).
[60]
Lecca, P.; Morpurgo, D.; Fantaccini, G.; Casagrande, A.; Priami, C. Inferring biochemical reaction pathways: The case of the gemcitabine pharmacokinetics. BMC Syst. Biol. 2012, 6, 51:1–51:21.
[61]
Székely, G.; Rizzo, M.; Bakirov, N. Measuring and testing dependence by correlation of distances. Ann. Stat. 2007, 35, 2769–2794, doi:10.1214/009053607000000505.
[62]
Szekely, G.; Rizzo, M. Brownian distance correlation. Ann. Appl. Stat. 2009, 3, 1236–1265, doi:10.1214/09-AOAS312.
[63]
Roy, A.; Post, C. Detection of long-range concerted motions in protein by a distance covariance. J. Chem. Theory Comput. 2012, 8, 3009–3014, doi:10.1021/ct300565f. 23610564
[64]
Kong, J.; Klein, B.; Klein, R.; Lee, K.; Wahba, G. Using distance correlation and SS-ANOVA to assess associations of familial relationships, lifestyle factors, diseases, and mortality. Proc. Natl. Acad. Sci. USA 2012, 109, 20352–20357, doi:10.1073/pnas.1217269109. 23175793
[65]
Kumari, S.; Nie, J.; Chen, H.; Ma, H.; Stewart, R.; Li, X.; Lu, M.; Taylor, W.; Wei, H. Evaluation of gene association methods for coexpression network construction and biological knowledge discovery. PLoS One 2012, 7, e50411:1–e50411:17.
[66]
Reshef, D.; Reshef, Y.; Finucane, H.; Grossman, S.; McVean, G.; Turnbaugh, P.; Lander, E.; Mitzenmacher, M.; Sabeti, P. Detecting novel associations in large data sets. Science 2011, 334, 1518–1524. 22174245
[67]
Kinney, J.; Atwal, G. Equitability, mutual information, and the maximal information coefficient. arXiv 2013. arXiv:1301, 7745.
[68]
Heller, R.; Heller, Y.; Gorfine, M. A consistent multivariate test of association based on ranks of distances. arXiv 2012. arXiv:1201, 3522.
[69]
Reshef, D.; Reshef, Y.; Mitzenmacher, M.; Sabeti, P. Equitability analysis of the maximal information coefficient, with comparisons. arXiv 2013. arXiv:1301, 6314.
[70]
Lopes, F.; de Oliveira, E.; Cesar, R. Inference of gene regulatory networks from time series by Tsallis entropy. BMC Syst. Biol. 2011, 5, 61:1–61:13.
[71]
Zhao, W.; Serpedin, E.; Dougherty, E.R. Inferring gene regulatory networks from time series data using the minimum description length principle. Bioinformatics 2006, 22, 2129–2135, doi:10.1093/bioinformatics/btl364. 16845143
[72]
Dougherty, J.; Tabus, I.; Astola, J. Inference of gene regulatory networks based on a universal minimum description length. EURASIP J. Bioinform. Syst. Biol. 2008, 2008, 482090:1–482090:11.
Margolin, A.; Nemenman, I.; Basso, K.; Wiggins, C.; Stolovitzky, G.; Favera, R.; Califano, A. ARACNE: An algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context. BMC Bioinform. 2006, 7, S7:1–S7:15, doi:10.1186/1471-2105-7-71.
[77]
Zoppoli, P.; Morganella, S.; Ceccarelli, M. TimeDelay-ARACNE: Reverse engineering of gene networks from time-course data by an information theoretic approach. BMC Bioinform. 2010, 11, 154:1–154:15.
[78]
Zhao, W.; Serpedin, E.; Dougherty, E. Inferring connectivity of genetic regulatory networks using information-theoretic criteria. IEEE ACM Trans. Comput. Biol. Bioinformatics 2008, 5, 262–274, doi:10.1109/TCBB.2007.1067.
[79]
Faith, J.; Hayete, B.; Thaden, J.; Mogno, I.; Wierzbowski, J.; Cottarel, G.; Kasif, S.; Collins, J.; Gardner, T. Large-scale mapping and validation of Escherichia coli transcriptional regulation from a compendium of expression profiles. PLoS Biol. 2007, 5, e8:1–e8:13.
[80]
Friedman, N.; Linial, M.; Nachman, I.; Pe'er, D. Using Bayesian networks to analyze expression data. J. Comput. Biol. 2000, 7, 601–620, doi:10.1089/106652700750050961. 11108481
[81]
Michoel, T.; de Smet, R.; Joshi, A.; van de Peer, Y.; Marchal, K. Comparative analysis of module-based versus direct methods for reverse-engineering transcriptional regulatory networks. BMC Syst. Biol. 2009, 3, 49:1–49:13.
[82]
Meyer, P.; Kontos, K.; Lafitte, F.; Bontempi, G. Information-theoretic inference of large transcriptional regulatory networks. EURASIP J. Bioinform. Syst. Biol. 2007, 2007, 79879:1–79879:9.
[83]
Tourassi, G.; Frederick, E.; Markey, M.; Floyd, J. Application of the mutual information criterion for feature selection in computer-aided diagnosis. Med. Phys. 2001, 28, 2394–2402, doi:10.1118/1.1418724. 11797941
[84]
Peng, H.; Long, F.; Ding, C. Feature selection based on mutual information: Criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans. Pattern Anal. Mach. Intell. 2005, 27, 1226–1238, doi:10.1109/TPAMI.2005.159. 16119262
[85]
Ding, C.; Peng, H. Minimum redundancy feature selection from microarray gene expression data. J. Bioinform. Comput. Biol. 2005, 3, 185–205, doi:10.1142/S0219720005001004. 15852500
[86]
Meyer, P.; Lafitte, F.; Bontempi, G. Minet: A R/Bioconductor package for inferring large transcriptional networks using mutual information. BMC Bioinform. 2008, 9, 461:1–461:10.
[87]
Meyer, P.; Marbach, D.; Roy, S.; Kellis, M. Information-theoretic inference of gene networks using backward elimination. Proceedings of the IASTED International Conference on Computational Bioscience (CompBio), BIOCOMP, Cambridge, MA, USA, 1–3 November 2010; pp. 1–6.
[88]
Luo, W.; Hankenson, K.; Woolf, P. Learning transcriptional regulatory networks from high throughput gene expression data using continuous three-way mutual information. BMC Bioinform. 2008, 9, 467:1–467:15.
[89]
Watkinson, J.; Liang, K.; Wang, X.; Zheng, T.; Anastassiou, D. Inference of regulatory gene interactions from expression data using three-way mutual information. Ann. N.Y. Acad. Sci. 2009, 1158, 302–313, doi:10.1111/j.1749-6632.2008.03757.x. 19348651
[90]
Stolovitzky, G.; Prill, R.; Califano, A. Lessons from the DREAM2 Challenges. Ann. N.Y. Acad. Sci. 2009, 1158, 159–195, doi:10.1111/j.1749-6632.2009.04497.x. 19348640
[91]
Wang, X.; Qi, Y.; Jiang, Z. Reconstruction of transcriptional network from microarray data using combined mutual information and network-assisted regression. IET Syst. Biol. 2011, 5, 95–102, doi:10.1049/iet-syb.2010.0041. 21405197
[92]
Bonneau, R.; Reiss, D.; Shannon, P.; Facciotti, M.; Hood, L.; Baliga, N.; Thorsson, V. The Inferelator: An algorithm for learning parsimonious regulatory networks from systems-biology data sets. de novo. Genome Biol. 2006, 7, R36:1–R36:16.
[93]
Bonneau, R.; Facciotti, M.; Reiss, D.; Schmid, A.; Pan, M.; Kaur, A.; Thorsson, V.; Shannon, P.; Johnson, M.; Bare, J.; et al. A predictive model for transcriptional control of physiology in a free living cell. Cell 2007, 131, 1354–1365, doi:10.1016/j.cell.2007.10.053. 18160043
[94]
Greenfield, A.; Madar, A.; Ostrer, H.; Bonneau, R. DREAM4: Combining genetic and dynamic information to identify biological networks and dynamical models. PLoS One 2010, 5, e13397:1–e13397:14.
[95]
De La Fuente, A.; Bing, N.; Hoeschele, I.; Mendes, P. Discovery of meaningful associations in genomic data using partial correlation coefficients. Bioinformatics 2004, 20, 3565–3574, doi:10.1093/bioinformatics/bth445. 15284096
[96]
Bing, N.; Hoeschele, I. Genetical genomics analysis of a yeast segregant population for transcription network inference. Genetics 2005, 170, 533–542, doi:10.1534/genetics.105.041103. 15781693
[97]
？ak？r, T.; Hendriks, M.; Westerhuis, J.; Smilde, A. Metabolic network discovery through reverse engineering of metabolome data. Metabolomics 2009, 5, 318–329, doi:10.1007/s11306-009-0156-4. 19718266
[98]
Pearl, J. An introduction to causal inference. Int. J. Biostat. 2010, 6, 7:1–7:61.
[99]
Rice, J.; Tu, Y.; Stolovitzky, G. Reconstructing biological networks using conditional correlation analysis. Bioinformatics 2005, 21, 765–773, doi:10.1093/bioinformatics/bti064. 15486043
[100]
Opgen-Rhein, G.; Strimmer, K. From correlation to causation networks: A simple approximate learning algorithm and its application to high-dimensional plant gene expression data. BMC Syst. Biol. 2007, 1, 37:1–37:10.
[101]
Mathai, P.; Martins, N.; Shapiro, B. On the detection of gene network interconnections using directed mutual information. Proceedings of the Information Theory and Applications Workshop, La Jolla, CA, USA, 29 January–2 February 2007; pp. 274–283.
[102]
Rao, A.; Hero, A.; States, D.; Engel, J. Using directed information to build biologically relevant influence networks. J. Bioinform. Comput. Biol. 2008, 6, 493–519, doi:10.1142/S0219720008003515. 18574860
[103]
Kaleta, C.; G？hler, A.; Schuster, S.; Jahreis, K.; Guthke, R.; Nikolajewa, S. Integrative inference of gene-regulatory networks in Escherichia coli using information theoretic concepts and sequence analysis. BMC Syst. Biol. 2010, 4, 116:1–116:11.
[104]
Quinn, C.; Coleman, T.; Kiyavash, N.; Hatsopoulos, N. Estimating the directed information to infer causal relationships in ensemble neural spike train recordings. J. Comput. Neurosci. 2011, 30, 17–44, doi:10.1007/s10827-010-0247-2. 20582566
[105]
Emmert-Streib, F. Influence of the experimental design of gene expression studies on the inference of gene regulatory networks: Environmental factors. PeerJ 2013, 1, e10:1–e10:20, doi:10.7717/peerj.101.
[106]
De Matos Simoes, R.; Emmert-Streib, F. Bagging statistical network inference from large-scale gene expression data. PLoS One 2012, 7, e33624:1–e33624:11.
[107]
Altay, G.; Emmert-Streib, F. Inferring the conservative causal core of gene regulatory networks. BMC Syst. Biol. 2010, 4, 132:1–132:13.
[108]
Marbach, D.; Prill, R.; Schaffter, T.; Mattiussi, C.; Floreano, D.; Stolovitzky, G. Revealing strengths and weaknesses of methods for gene network inference. Proc. Natl. Acad. Sci. USA 2010, 107, 6286–6291, doi:10.1073/pnas.0913357107. 20308593
