Rearrangement Events on Circular Genomes

Abstract

Early literature on genome rearrangement modelling views the problem of computing evolutionary distances as an inherently combinatorial one. In particular, attention is given to estimating distances using the minimum number of events required to transform one genome into another. In hindsight, this approach is analogous to early methods for inferring phylogenetic trees from DNA sequences such as maximum parsimony-both are motivated by the principle that the true distance minimises evolutionary change, and both are effective if this principle is a true reflection of reality. Recent literature considers genome rearrangement under statistical models, continuing this parallel with DNA-based methods, with the goal of using model-based methods (for example maximum likelihood techniques) to compute distance estimates that incorporate the large number of rearrangement paths that can transform one genome into another. Crucially, this approach requires one to decide upon a set of feasible rearrangement events and, in this paper, we focus on characterising well-motivated models for signed, uni-chromosomal circular genomes, where the number of regions remains fixed. Since rearrangements are often mathematically described using permutations, we isolate the sets of permutations representing rearrangements that are biologically reasonable in this context, for example inversions and transpositions. We provide precise mathematical expressions for these rearrangements, and then describe them in terms of the set of cuts made in the genome when they are applied. We directly compare cuts to breakpoints, and use this concept to count the distinct rearrangement actions which apply a given number of cuts. Finally, we provide some examples of rearrangement models, and include a discussion of some questions that arise when defining plausible models.

Keywords: Combinatorics; Genome rearrangements; Phylogenetics.

Fig. 1

On the left is a drawing of the 5-region genome represented by the identity permutation $\left[\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 2& 3& 4& 5\end{array}\right]$, which we refer to as the reference genome. On the right is a drawing of the genome represented by $\sigma =\left[\begin{array}{ccccc}1& 2& 3& 4& 5\\ \overline{1}& 4& 3& \overline{5}& \overline{2}\end{array}\right]$. Alternate representations are summarised in Table 1

Fig. 2

Diagrams representing each of the $2n=2(5)=10$ instances of the example genome ${\mathcal{D}}_n\sigma$ arising from its dihedral symmetries. The bottom left diagram matches the instance $\sigma =\left[,\overline{1},,,4,,3,,,\overline{5},,,,\overline{2},\right]$ (also shown in Fig. 1). Positions run clockwise starting from position 1 in the top-right of the circle

Fig. 3

A graph representation of the Markov chain for a model of inversions on circular genomes with 3 oriented regions. Node labels are of the form $\mathbf{z}\sigma$ where $\mathbf{z}$ is the symmetry element and $\sigma$ is one particular instance of the genome (position paradigm, region $\to$ position) written in one-row notation. Lines between genomes show the probability of a rearrangement which transforms one into the other. The minimum number of steps needed to traverse the graph from one genome to another is the ‘inversion distance’. The edge weights are the same for any choice of probability mapping w, since with only three regions, every inversion of two regions can be written as an inversion of a single region

Fig. 4

An inversion represented by the permutation $\alpha =(3\overline{3})(2\overline{4})(\overline{2}4)$ (as in Example 4.3), applied to the reference genome (Color figure online)

Fig. 5

Different ways to reconnect three labelled segments to perform a rearrangement that requires 3 cuts (Color figure online)

Fig. 6

A diagram representing the identity rearrangement, and three representing rearrangements that require 2 cuts (Color figure online)

Fig. 7

Diagrams representing fission rearrangements, which we do not consider here (Color figure online)