The evolution of the random reversal graph

Genomes are typically represented as signed permutations, where each integer corresponds to a single gene and its sign indicates the orientation of the gene. In this paper we study genome rearrangements via reversals (Sankoff and Blanchette, 1999) [20], flipping entire segments of genes and changing their orientations. This abstraction leads to the notion of the reversal graph in which two signed permutations are neighbors if they differ by one reversal. We identify the evolution of multiple genomes within the random reversal graph, i.e. the probability space consisting of subgraphs over signed permutations, obtained by selecting edges (reversals) with independent probability λn, which is an important framework for the analysis of genome rearrangements in the sense of relating the reversal rate λn with the global evolution of genomes. Our main result shows that the structure of the random reversal graph changes dramatically at λn=1/n+12. For λn=(1-∊)n+12, the random graph consists of components of size at most O(nlnn) a.s. and for (1+∊)n+12, there emerges a unique largest component of size ∼℘(∊)·2n·n! a.s., where ℘(∊) is the survival probability of a certain branching process. This “giant” component is furthermore dense in the reversal graph.