Evolutionary graph theory
Encyclopedia
Evolutionary graph theory is an area of research lying at the intersection of graph theory
, probability theory
, and mathematical biology
. Evolutionary graph theory is an approach to studying how topology
affects evolution
of a population
. That the underlying topology can substantially affect the results of the evolutionary process is seen most clearly in a paper by Erez Lieberman
, Christoph Hauert and Martin Nowak
.
In evolutionary graph theory, individuals occupy vertices
of a weighted directed graph
and the weight wi j of an edge from vertex i to vertex j denotes the probability of i replacing j. The weight corresponds to the biological notion of fitness
where fitter types propagate more readily.
One property studied on graphs with two types of individuals is the fixation probability, which is defined as the probability that a single, randomly placed mutant of type A will replace a population of type B. According to the isothermal theorem, a graph has the same fixation probability as the corresponding Moran process
if and only if it isothermal, thus the sum of all weights that lead into a vertex is the same for all vertices. This probability is
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, and mathematical biology
Mathematical biology
Mathematical and theoretical biology is an interdisciplinary scientific research field with a range of applications in biology, medicine and biotechnology...
. Evolutionary graph theory is an approach to studying how topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
affects evolution
Evolution
Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth...
of a population
Population
A population is all the organisms that both belong to the same group or species and live in the same geographical area. The area that is used to define a sexual population is such that inter-breeding is possible between any pair within the area and more probable than cross-breeding with individuals...
. That the underlying topology can substantially affect the results of the evolutionary process is seen most clearly in a paper by Erez Lieberman
Erez Lieberman
Erez Lieberman-Aiden is a fellow at the Harvard Society of Fellows and visiting faculty member at Google. He has conducted pioneering work on mathematical and computational approaches to the study of biological evolution, as well as other forms of evolution through mutation and selection,...
, Christoph Hauert and Martin Nowak
Martin Nowak
Martin A. Nowak is Professor of Biology and Mathematics and Director of the Program for Evolutionary Dynamics at Harvard University.-Career:Martin Nowak studied biochemistry and mathematics at the University of Vienna, and earned his Ph. D. in 1989, working with Peter Schuster on quasi-species...
.
In evolutionary graph theory, individuals occupy vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of a weighted directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
and the weight wi j of an edge from vertex i to vertex j denotes the probability of i replacing j. The weight corresponds to the biological notion of fitness
Fitness (biology)
Fitness is a central idea in evolutionary theory. It can be defined either with respect to a genotype or to a phenotype in a given environment...
where fitter types propagate more readily.
One property studied on graphs with two types of individuals is the fixation probability, which is defined as the probability that a single, randomly placed mutant of type A will replace a population of type B. According to the isothermal theorem, a graph has the same fixation probability as the corresponding Moran process
Moran process
A Moran process, named after Patrick Moran, is a stochastic process used in biology to describe finite populations. It can be used to model variety-increasing processes such as mutation as well as variety-reducing effects such as genetic drift and natural selection...
if and only if it isothermal, thus the sum of all weights that lead into a vertex is the same for all vertices. This probability is
-
where r is the relative fitness of the invading type. Thus, a complete graphComplete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
with equal weights describes a Moran process.
Graphs can be classified into amplifiers of selection and suppressors of selection. If the fixation probability of a single advantageous mutation
is higher than the fixation probability of the corresponding Moran processMoran processA Moran process, named after Patrick Moran, is a stochastic process used in biology to describe finite populations. It can be used to model variety-increasing processes such as mutation as well as variety-reducing effects such as genetic drift and natural selection...
then the graph is an amplifier, otherwise a suppressor of selection. One example of the suppressor of selection is a linear process where only vertex i-1 can replace vertex i (but not the other way around). In this case the fixation probability is 
(where N is the number of vertices) since this is the probability that the mutation arises in the first vertex which will eventually replace all the other ones. Since 
for all r greater than 1, this graph is by definition a suppressor of selection.
Evolutionary graph theory may also be studied in a dual formulation, as a coalescing random walk.
Also evolutionary gamesEvolutionary game theoryEvolutionary game theory is the application of Game Theory to evolving populations of lifeforms in biology. EGT is useful in this context by defining a framework of contests, strategies and analytics into which Darwinian competition can be modelled. It originated in 1973 with John Maynard Smith...
can be studied on graphs where again an edge between i and j means that these two individuals will play a game against each other.
Closely related stochastic processes include the voter model, which was introduced by Clifford and Sudbury (1973) and independently by Holley and Liggett (1975), and which has been studied extensively.
External links
A virtual laboratory for studying evolution on graphs:http://www.univie.ac.at/virtuallabs/Moran/