Sex as an algorithm: the theory of evolution under the lens of computation

Abstract

Looking at the mysteries of evolution from a computer science point of view yields some unexpected insights.

References

1. Aldous, D. and Vazirani, U. 'Go with the winners' algorithms. In Proceedings of the 35^th Annual IEEE Symposium on Foundations of Computer Science (1994). 492--501.
2. Arora, S., Hazan, E. and Kale, S. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing 8, 1 (2012), 121--164.
3. Athreya, K. and Ney, P. Branching Processes. Springer, 1972.
4. Babbage, C. The Ninth Bridgewater Treatise. 2^nd edn. John Murray, London, 1838.
5. Barton, N.H., Novak, S. and Paixão, T. Diverse forms of selection in evolution and computer science. In Proceedings of the National Academy of Sciences 111, 29 (2014), 10398--10399.
6. Bell, G. The Masterpiece of Nature: The Evolution and Genetics of Sexuality. University of California Press, Berkeley, CA, 1982.
7. Chastain, E., Livnat, A., Papadimitriou, C. and Vazirani, U. Algorithms, games, and evolution. In Proceedings of the National Academy of Sciences 111, 29 (2014), 10620--10623.
8. Darwin, C. On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. Murray, London, 1859.
9. Feldman, M.W. Otto, P. and Christiansen, F.B. Population genetic perspectives on the evolution of recombination. Annual Review of Genetics 30 (1997), 261--295.
10. Fisher, R.A. The Genetical Theory of Natural Selection. The Clarendon Press, Oxford, U.K., 1930.
11. Fryxell, K.J. and Moon, W.-J. CpG mutation rates in the human genome are highly dependent on local GC content. Molecular Biology and Evolution 22 (2005), 650--658.
12. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.
13. Graur, D. and Li, W.-H. Fundamentals of Molecular Evolution. Sinauer Associates, Sunderland, MA, 2000.
14. Holland, J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. U Michigan Press, 1975.
15. Johnson, D.S., Papadimitriou, C.H., and Yannakakis, M. How easy is local search? J. Computer and System Sciences 37, 1 (1988), 79--100.
16. Jong, K.A.D. Evolutionary Computation: A Unified Approach. MIT Press, Cambridge MA, 2006.
17. Kanade, V. Evolution with recombination. In Proceedings of the 52^nd Annual IEEE Symposium on Foundations of Computer Science, (2011), 837--846.
18. Kearns, M. Efficient noise-tolerant learning from statistical queries. J. ACM 45, 6 (1998), 983--1006.
19. Kimura, M. and Ohta, T. The average number of generations until fixation of a mutant gene in a finite population. Genetics 61, 3 (1969), 763.
20. Kirkpatrick, S., Gelatt, Jr, C.D. and Vecchi, M.P. Optimization by simulated annealing. Science 220 (1983), 671--680.
21. Lewontin, R.C. and Hubby, J.L. A molecular approach to the study of genic heterozygosity in natural populations; amount of variation and degree of heterozygosity in natural populations of Drosophila pseudoobscura. Genetics 54 (1966), 595--609.
22. Livnat, A. Interaction-based evolution: How natural selection and nonrandom mutation work together. Biology Direct 8, 1 (2013), 24.
23. Livnat, A., Feldman, M.W., Papadimitriou, C. and Pippenger, N. On the advantage to sexual species in diversification rates. Unpublished manuscript.
24. Livnat, A., Papadimitriou, C., Dushoff, J. and Feldman, M.W. A mixability theory for the role of sex in evolution. In Proceedings of the National Academy of Sciences 105, 50 (2008), 19803--19808.
25. Livnat, A., Papadimitriou, C. and Feldman, M.W. An analytical contrast between fitness maximization and selection for mixability. J. Theoretical Biology 273, 1 (2011), 232--234.
26. Livnat, A., Papadimitriou, C., Pippenger, N. and Feldman, M.W. Sex, mixability, and modularity. In Proceedings of the National Academy of Sciences 107, 4 (2010), 1452--1457.
27. Lynch, V.J., Leclerc, R.D., May, G. and Wagner, G.P. Transposon-mediated rewiring of gene regulatory networks contributed to the evolution of pregnancy in mammals. Nature Genetics 43 (2011), 1154--1159.
28. Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 1996.
29. Motwani, R. and Raghavan, P. Randomized Algorithms. Cambridge University Press, 1995.
30. Nagylaki, T., Hofbauer, J. and Brunovský, P. Convergence of multilocus systems under weak epistasis or weak selection. J. Mathematical Biology 38, 2 (1999), 103--133.
31. Nevo, E., Beiles, A. and Ben-Shlomo, R. The evolutionary significance of genetic diversity: Ecological, demographic and life history correlates. Lecture Notes in Biomathematics 53 (1984), 13--213.
32. Papadimitriou, C. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
33. Rabani, Y. Rabinovich, Y. and Sinclair, A. A computational view of population genetics. In Proceedings of the 27^th Annual ACM Symposium on Theory of Computing, (1995), 83--92.
34. Stearns, S.C. and Hoekstra, R.F. Evolution: An Introduction. Oxford University Press, New York, 2005.
35. Valiant, L. Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World. Basic Books, 2013.
36. Valiant, L.G. Evolvability. J. ACM 56, 1 (2009), 3.
37. Von Neumann, J. and A. W. Burks, A.W. Theory of self-reproducing automata. IEEE Transactions on Neural Networks 5, 1 (1966), 3--14.
38. Williams, G.C. Adaptation and Natural Selection, 8th edition. Princeton University Press, 1996.
39. Wright, S. Evolution in Mendelian populations. Genetics 16 (1931), 97--159.
40. Wright, S. The distribution of gene frequencies in populations. In Proceedings of the National Academy of Sciences of the United States of America, 23, 6 (1937), 307--320.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Genomics

      • Computational genomics