Exploring and mapping the universe of evolutionary graphs

Abstract

Population structure can be modelled by evolutionary graphs, which can have a substantial, but very subtle influence on the fate of the arising mutants. Individuals are located on the nodes of these graphs, competing with each other to eventually take over the graph via the links. Many applications for this framework can be envisioned, from the ecology of river systems and cancer initiation in colonic crypts to biotechnological search for optimal mutations. In all these applications, it is not only important where and when novel variants arise and how likely it is that they ultimately take over, but also how long this process takes. More concretely, how is the probability to take over the population related to the associated time? We study this problem for all possible undirected and unweighted graphs up to a certain size. To move beyond the graph size where an exhaustive search is possible, we devise a genetic algorithm to find graphs with either high or low fixation probability and either short or long fixation time and study their structure in detail searching for common themes. Our work unravels structural properties that maximize or minimize fixation probability and time, which allows us to contribute to a first map of the universe of evolutionary graphs.