Bioinformatic Game Theory and Its Application to Biological Affinity Networks

Bo Deng, Brittney Hinds, Ximeng Zheng, Etsuko N. Moriyama

Department of Mathematics, University of Nebraska-Lincoln, Lincoln, USA.
School of Biological Sciences and Center for Plant Science Innovation, University of Nebraska-Lincoln, Lincoln, USA.
School of Biological Sciences, University of Nebraska-Lincoln, Lincoln, USA.

DOI: 10.4236/am.2013.410A2010                

Abstract

The exact evolutionary history of any set of biological taxa is unknown, and all phylogenetic reconstructions are approximations. The problem becomes harder when one must consider a mix of vertical and lateral phylogenetic signals. In this paper we propose a game theoretic approach to constructing biological networks. The key hypothesis is that evolution is driven by distinct mechanisms that seek to maximize two competing objectives, taxonomic conservation and diversity. One branch of the mathematical theory of games is brought to bear. It translates this evolutionary game hypothesis into a mathematical model in two-player zero-sum games, with the zero-sum assumption conforming to one of the fundamental constraints in nature in mass and energy conservation. We demonstrate why and how a mechanistic and localized adaptation to seek out greater information for conservation and diversity may always lead to a global Nash equilibrium in phylogenetic affinity. Our game theoretic method, referred to as bioinformatic game theory, is used to construct network clusters. As an example, we applied this method to clustering of a multidomain protein family. The protein clusters identified were consistent with known protein subfamilies, indicating that this game-theoretic approach provides a new framework in biological sequence analysis, especially in studying gene-genome and domain-protein relationships.

Keywords

Bioinformatic Game Theory; Biological Network; Evolutionary Game Theory; Nash Dynamics; BNN Equations

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Doolittle, “Phylogenetic Classification and the Universal Tree,” Science, Vol. 284, No. 5423, 1999, pp. 2124-2129. http://dx.doi.org/10.1126/science.284.5423.2124
[2]	S. Halary, J. W. Leigh, B. Cheaib, P. Lopez and E. Bapteste, “Network Analyses Structure Genetic Diversity in Independent Genetic Worlds,” Proceedings of the National Academy of Sciences, Vol. 107, No. 1, 2010, pp. 127-132.
[3]	P. H. A. Sneath, “Reticulate Evolution in Bacteria and Other Organisms: How Can We Study It?” Journal of Classification, Vol. 17, No. 2, 2000, pp. 159-163. http://dx.doi.org/10.1007/s003570000014
[4]	D. Posada and K. Crandall, “Intraspecific Gene Genealogies: Trees Grafting into Networks,” Trends in Ecology and Evolution, Vol. 16, No. 1, 2001, pp. 37-45. http://dx.doi.org/10.1016/S0169-5347(00)02026-7
[5]	M. Eigen, R. Winkler-Oswatitsch and A. Dress, “Statistical Geometry in Sequence Space: A Method of Quantitative Comparative Sequence Analysis,” Proceedings of the National Academy of Sciences, USA, Vol. 85, No. 16, 1988, pp. 5913-5917. http://dx.doi.org/10.1073/pnas.85.16.5913
[6]	V. Makarenkov and P. Legendre, “From a Phylogenetic Tree to a Reticulated Network,” Journal of Computational Biology, Vol. 11, No. 1, 2004, pp. 195-212. http://dx.doi.org/10.1089/106652704773416966
[7]	D. Bryant and V. Moulton, “Neighbor-Net: An Agglomerative Method for the Construction of Phylogenetic Networks,” Molecular Biology and Evolution, Vol. 21, No. 2, 2004, pp. 255-265. http://dx.doi.org/10.1093/molbev/msh018
[8]	D. H. Huson and C. Scornavacca, “A Survey of Combinatorial Methods for Phylogenetic Networks,” Genome Biology and Evolution, Vol. 3, 2011, pp. 23-35. http://dx.doi.org/10.1093/gbe/evq077
[9]	P. Legendre and V. Makarenkov, “Reconstruction of Biogeographic and Evolutionary Networks Using Reticulograms,” Systematic Biology, Vol. 51, No. 2, 2002, pp. 199-216. http://dx.doi.org/10.1080/10635150252899725
[10]	C. Holloway and R. Beiko, “Assembling Networks of Microbial Genomes Using Linear Programming,” BMC Evolutionary Biology, Vol. 10, 2010, p. 360. http://dx.doi.org/10.1186/1471-2148-10-360
[11]	R. Beiko, W. Doolittle and R. Charlebois, “The Impact of Reticulate Evolution on Genome Phylogeny,” Systematic Biology, Vol. 57, No. 6, 2008, pp. 844-856. http://dx.doi.org/10.1080/10635150802559265
[12]	B. Boussau, L. Guéuen and M. Gouy, “Accounting for Horizontal Gene Transfers Explains Conflicting Hypotheses Regarding the Position of Aquificales in the Phylogeny of Bacteria,” BMC Evolutionary Biology, Vol. 8, 2008, p. 272. http://dx.doi.org/10.1186/1471-2148-8-272
[13]	T. Cavalier-Smith, “Rooting the Tree of Life by Transition Analyses,” Biology Direct, Vol. 1, 2006, p. 19. http://dx.doi.org/10.1186/1745-6150-1-19
[14]	G. Lima-Mendez, J. Van Helden, A. Toussaint and R. Leplae, “Reticulate Representation of Evolutionary and Functional Relationships between Phage Genomes,” Molecular Biology and Evolution, Vol. 25, No. 4, 2008, pp. 762-777. http://dx.doi.org/10.1093/molbev/msn023
[15]	R. Luce and H. Raiffa, “Games and Decisions: Introduction and Critical Survey,” Dover Press, Mineola, 1989.
[16]	J. Nash, “Equilibrium Points in N-Person Games,” Proceedings of the National Academy of Sciences, Vol. 36, No. 1, 1950, pp. 48-49. http://dx.doi.org/10.1073/pnas.36.1.48
[17]	J. Nash, “Non-Cooperative Games,” The Annals of Mathematics, Vol. 54, No. 2, 1951, pp. 286-295. http://dx.doi.org/10.2307/1969529
[18]	G. W. Brown and J. von Neumann, “Solutions of Games by Differential Equations,” In: H. W. Kuhn and A. W. Tucker, Eds., Contributions to the Theory of Games I, Princeton University Press, Princeton, 1950, pp. 73-79.
[19]	J. Hofbauer, “Deterministic Evolutionary Game Dynamics,” Proceedings of Symposia in Applied Mathematics, Vol. 69, 2011, pp. 61-79. http://dx.doi.org/10.1090/psapm/069/2882634
[20]	D. Graur and W. H. Li, “Fundamentals of Molecular Evolution,” 2nd Edition, Sinauer Associates, Inc., Sunderland, 2000.
[21]	E. V. Koonin, L. Aravind and A. S. Kondrashov, “The Impact of Comparative Genomics on Our Understanding of Evolution,” Cell, Vol. 101, No. 6, 2000, pp. 573-576. http://dx.doi.org/10.1016/S0092-8674(00)80867-3
[22]	K. Forslund and E. L. Sonnhammer, “Evolution of Protein Domain Architectures,” Methods in Molecular Biology, Vol. 856, 2012, pp. 187-216. http://dx.doi.org/10.1007/978-1-61779-585-5_8
[23]	C. Vogel, S. A. Teichmann and J. Pereira-Leal, “The Relationship between Domain Duplication and Recombination,” Journal of Molecular Biology, Vol. 346, No. 1, 2005, pp. 355-365. http://dx.doi.org/10.1016/j.jmb.2004.11.050
[24]	S. R. Eddy, “A Probabilistic Model of Local Sequence Alignment that Simplifies Statistical Significance Estimation,” PLoS Computational Biology, Vol. 4, No. 5, 2008, Article ID: e1000069. http://dx.doi.org/10.1371/journal.pcbi.1000069
[25]	R. D. Finn, J. Clements and S. R. Eddy, “HMMER Web Server: Interactive Sequence Similarity Searching,” Nucleic Acids Research, Vol. 39, 2011, pp. W29-W37.
[26]	R. D. Finn, J. Mistry, J. Tate, P. Coggill, A. Heger, J. E. Pollington, O. L. Gavin, P. Gunasekaran, G. Ceric, K. Forslund, S. R. Eddy, E. L. L. Sonnhammer and A. Bateman, “The Pfam Protein Families Database,” Nucleic Acids Research, Vol. 38, Suppl. 1, 2010, pp. D211-D222. http://dx.doi.org/10.1093/nar/gkp985
[27]	S. F. Altschul, W. Gish, W. Miller, E. W. Myers and D. J. Lipman, “Basic Local Alignment Search Tool,” Journal of Molecular Biology, Vol. 215, No. 3, 1990, pp. 403410.
[28]	A. Marchler-Bauer, S. Lu, J. B. Anderson, F. Chitsaz, M. K. Derbyshire, C. DeWeese-Scott, J. H. Fong, L. Y. Geer, R. C. Geer, N. R. Gonzales, M. Gwadz, D. I. Hurwitz, J. D. Jackson, Z. Ke, C. J. Lanczycki, F. Lu, G. H. Marchler, M. Mullokandov, M. V. Omelchenko, C. L. Robertson, J. S. Song, N. Thanki, R. A. Yamashita, D. Zhang, N. Zhang, C. Zheng and S. H. Bryant, “CDD: A Conserved Domain Database for the Functional Annotation of Proteins,” Nucleic Acids Research, Vol. 39, Database Issue, 2011, D225-D229. http://dx.doi.org/10.1093/nar/gkq1189
[29]	J. Maynard Smith, “The Theory of Games and the Evolution of Animal Conflicts,” Journal of Theoretical Biology, Vol. 47, No. 1, 1974, pp. 209-221. http://dx.doi.org/10.1016/0022-5193(74)90110-6
[30]	J. Maynard Smith, “Evolution and the Theory of Games,” Cambridge University Press, Cambridge, 1982. http://dx.doi.org/10.1017/CBO9780511806292
[31]	J. Hofbauer and W. H. Sandholm, “Stable Games and Their Dynamics,” Journal of Economic Theory, Vol. 144, No. 4, 2009, pp. 1665-1693. http://dx.doi.org/10.1016/j.jet.2009.01.007
[32]	J. von Neumann, “On the Theory of Games of Strategy,” In: A. W. Tucker and R. D. Luce, Eds., Contributions to the Theory of Games, Vol. 24, Princeton University Press, Princeton, 1959.
[33]	J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior,” Princeton University Press, Princeton, 1944.
[34]	H. W. Kuhn and A. W. Tucker, “Contributions to the Theory of Games,” Princeton University Press, Princeton, 1950.
[35]	I. Griva, S. Nash and A. Sofer, “Linear and Nonlinear Optimization,” Society for Industrial Mathematics, 2009. http://dx.doi.org/10.1137/1.9780898717730