A computational view of population genetics.

*(English)*Zbl 0955.92023Summary: This paper contributes to the study of nonlinear dynamical systems from a computational perspective. These systems are inherently more powerful than their linear counterparts (such as Markov chains), which have had a wide impact in computer science, and they seem likely to play an increasing role in the future. However, there are as yet no general techniques available for handling the computational aspects of discrete nonlinear systems, and even the simplest examples seem very hard to analyze.

We focus in this paper a class of quadratic systems that are widely used as a model in population genetics and also in genetic algorithms. These systems describe a process where random matings occur between parental chromosomes via a mechanism known as “crossover”: i.e., children inherit pieces of genetic material from different parents according to some random rule. Our results concern two fundamental quantitative properties of crossover systems:

1. We develop a general technique for computing the rate of convergence to equilibrium. We apply this technique to obtain tight bounds on the rate of convergence in several cases of biological and computational interest. In general, we prove that these systems are “rapidly mixing,” in the sense that the convergence time is very small in comparison with the size of the state space.

2. We show that, for crossover systems, the classical quadratic system is a good model for the behavior of finite populations of small size. This stands in sharp control to recent results of J. S. Arora et al. and P. PudlĂˇk, who show that such a correspondence is unlikely to hold for general quadratic systems.

We focus in this paper a class of quadratic systems that are widely used as a model in population genetics and also in genetic algorithms. These systems describe a process where random matings occur between parental chromosomes via a mechanism known as “crossover”: i.e., children inherit pieces of genetic material from different parents according to some random rule. Our results concern two fundamental quantitative properties of crossover systems:

1. We develop a general technique for computing the rate of convergence to equilibrium. We apply this technique to obtain tight bounds on the rate of convergence in several cases of biological and computational interest. In general, we prove that these systems are “rapidly mixing,” in the sense that the convergence time is very small in comparison with the size of the state space.

2. We show that, for crossover systems, the classical quadratic system is a good model for the behavior of finite populations of small size. This stands in sharp control to recent results of J. S. Arora et al. and P. PudlĂˇk, who show that such a correspondence is unlikely to hold for general quadratic systems.