article published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Andreas Pavlogiannis author 49704004-F248-11E8-B48F-1D18A9856A870000-0002-8943-0722 Ben Adlam author Martin Nowak author KrCh department Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project Quantitative Graph Games: Theory and Applications project Microsoft Research Faculty Fellowship project A fundamental question in biology is the following: what is the time scale that is needed for evolutionary innovations? There are many results that characterize single steps in terms of the fixation time of new mutants arising in populations of certain size and structure. But here we ask a different question, which is concerned with the much longer time scale of evolutionary trajectories: how long does it take for a population exploring a fitness landscape to find target sequences that encode new biological functions? Our key variable is the length, (Formula presented.) of the genetic sequence that undergoes adaptation. In computer science there is a crucial distinction between problems that require algorithms which take polynomial or exponential time. The latter are considered to be intractable. Here we develop a theoretical approach that allows us to estimate the time of evolution as function of (Formula presented.) We show that adaptation on many fitness landscapes takes time that is exponential in (Formula presented.) even if there are broad selection gradients and many targets uniformly distributed in sequence space. These negative results lead us to search for specific mechanisms that allow evolution to work on polynomial time scales. We study a regeneration process and show that it enables evolution to work in polynomial time. https://research-explorer.ista.ac.at/download/2039/4890/IST-2016-440-v1+1_journal.pcbi.1003818.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Public Library of Science2014 eng 00034301170001810.1371/journal.pcbi.1003818 109 https://research-explorer.ista.ac.at/record/9739 Chatterjee K, Pavlogiannis A, Adlam B, Nowak M. 2014. The time scale of evolutionary innovation. PLoS Computational Biology. 10(9), 7p. Chatterjee, K., Pavlogiannis, A., Adlam, B., &#38; Nowak, M. (2014). The time scale of evolutionary innovation. <i>PLoS Computational Biology</i>. Public Library of Science. <a href="https://doi.org/10.1371/journal.pcbi.1003818">https://doi.org/10.1371/journal.pcbi.1003818</a> K. Chatterjee, A. Pavlogiannis, B. Adlam, and M. Nowak, “The time scale of evolutionary innovation,” <i>PLoS Computational Biology</i>, vol. 10, no. 9. Public Library of Science, 2014. Chatterjee, Krishnendu, Andreas Pavlogiannis, Ben Adlam, and Martin Nowak. “The Time Scale of Evolutionary Innovation.” <i>PLoS Computational Biology</i>. Public Library of Science, 2014. <a href="https://doi.org/10.1371/journal.pcbi.1003818">https://doi.org/10.1371/journal.pcbi.1003818</a>. Chatterjee K, Pavlogiannis A, Adlam B, Nowak M. The time scale of evolutionary innovation. <i>PLoS Computational Biology</i>. 2014;10(9). doi:<a href="https://doi.org/10.1371/journal.pcbi.1003818">10.1371/journal.pcbi.1003818</a> K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Nowak, PLoS Computational Biology 10 (2014). Chatterjee, Krishnendu, et al. “The Time Scale of Evolutionary Innovation.” <i>PLoS Computational Biology</i>, vol. 10, no. 9, 7p, Public Library of Science, 2014, doi:<a href="https://doi.org/10.1371/journal.pcbi.1003818">10.1371/journal.pcbi.1003818</a>. 20392018-12-11T11:55:22Z2025-09-29T11:53:46Z