Perpetual disequilibrium and the computational complexity of evolution

23 Apr 2021

Artem Kaznatcheev
Department of Biology
University of Pennsylvania

zoom recording

Abstract

We are comfortable viewing individual organisms as systems that are far from equilibrium. Some might even joke that if I am at thermodynamic equilibrium then I am dead. Yet, we are much less willing to give up the convenience of equilibrium analysis in our formal models. Especially in simple models of evolutionary dynamics.

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima. I have introduced a distinction between easy landscapes of traditional theory where local fitness peaks can be found in a moderate number of steps, and hard landscapes where finding local optima requires an infeasible amount of time. On hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but must follow a power-law that long-term evolution experiments have associated with unbounded growth in fitness. Thus, the constraint of computational complexity enables open-ended evolution and perpetual disequilibrium on finite landscapes. Knowing this constraint allows us to use the tools of theoretical computer science and combinatorial optimization to characterize the fitness landscapes that we expect to see in nature.

Finally, similar results of perpetual disequilibrium can be used in biological settings beyond fitness landscapes. For example, by looking at the computational complexity of the Markov processes underlying gene regulation.

current theory lunch schedule