Breakpoint graphs and ancestral genome reconstructions

Abstract

Recently completed whole-genome sequencing projects marked the transition from gene-based phylogenetic studies to phylogenomics analysis of entire genomes. We developed an algorithm MGRA for reconstructing ancestral genomes and used it to study the rearrangement history of seven mammalian genomes: human, chimpanzee, macaque, mouse, rat, dog, and opossum. MGRA relies on the notion of the multiple breakpoint graphs to overcome some limitations of the existing approaches to ancestral genome reconstructions. MGRA also generates the rearrangement-based characters guiding the phylogenetic tree reconstruction when the phylogeny is unknown.

Figure 1.

(A) Unichromosomal genome P = (+a +b −c) represented as a black-obverse cycle. (B) Unichromosomal genome Q = (+a −b +c) represented as a green-obverse cycle. (C) The breakpoint graph G(P, Q) with and without obverse edges.

Figure 2.

(A) A 2-break on edges (x₁, x₂) and (y₁, y₂) from the same chromosome corresponds to either a reversal, or a fission. (B) A 2-break on edges (x₁, x₂) and (y₁, y₂) from different chromosomes corresponds to a translocation/fusion. (C) A 2-break on edges (y₁, y₂) and (x₁, ∞) of a linear chromosome corresponds to a reversal affecting a chromosome end x₁ and creating a new chromosome end y₁. (D) A 2-break on edges (x₁, ∞) and (y₁, ∞) from different chromosomes models a fusion. Fissions can be modeled as 2-breaks operating on an irregular loop edge (∞, ∞) and an arbitrary regular edge in the genome.

Figure 3.

(A) A phylogenetic tree T with four linear genomes P₁, P₂, P₃, P₄ (represented as green, blue, red, and yellow graphs, respectively) at the leaves. The obverse edges are not shown. (B) The multiple breakpoint graph G(P₁, P₂, P₃, P₄) is a superposition of graphs representing genomes P₁, P₂, P₃, P₄. The multi-degrees of regular vertices vary from 1 (e.g., vertex b^h) to 3 (e.g., vertex e^h). (C) The same phylogenetic tree T with all intermediate genomes specified and a genome X selected as a root. A T-consistent transformation of X into P₁, P₂, P₃, P₄ can viewed as a transformation of the quadruple (X, X, X, X) into the quadruple (P₁, P₂, P₃, P₄), where a rearrangement at each step is applied to some copies of the same genome in the quadruple. A particular such transformation takes the following steps: (X, X, X, X) (X, X, Q₁, Q₁) (Q₃, Q₃, Q₁, Q₁) (Q₃, Q₃, Q₂, Q₂) (Q₃, Q₃, P₃, Q₂) (Q₃, Q₃, P₃, P₄) (P₁, Q₃, P₃, P₄) (P₁, P₂, P₃, P₄), where r₁ is a reversal in two copies of X; r₂ is a fission in two copies of X; r₃ is a reversal in both copies of Q₁; r₄ is a fission in one copy of Q₂; r₅ is a reversal in the other copy of Q₂; r₆ is a reversal in one copy of Q₃; and r₇ is a translocation in the other copy of Q₃.

Figure 4.

The breakspoint graph G(M,R,D,Q,H,C) (obverse edges are not shown) of six mammalian genomes: mouse (red edges), rat (blue edges), dog (green edges), macaque (violet edges), human (orange edges), and chimpanzee (yellow edges). The graph has 1357 × 2 = 2714 vertices labeled as nt or nh (where n is a synteny block number) and colored in 23 colors representing chromosomes in the human genome.

Figure 5.

The phylogenetic tree T of six mammalian genomes: mouse (red), rat (blue), dog (green), macaque (violet), human (orange), and chimpanzee (yellow) with a root X on the MRD + QHC branch. The branches are directed toward X and labeled with the corresponding pairs of complementary T-consistent multi-colors. The -consistent multi-color from each pair also labels the starting node of the corresponding directed branch. Note that the tree orientation may not necessarily correlate with the time scale, and the root genome X may not necessarily be a common ancestor of the leaf genomes.

Figure 6.

(Top panel) Processing good paths using a -consistent red–blue multi-color. (A) A good path on vertices x₁, x₂,…, x₆ is transformed into a cycle on the same vertices by extending it into x₀, x₁, x₂,…, x₆, x₇ and performing a 2-break on the multi-edges (x₀, x₁) and (x₆, x₇). (B) Transformation of a good cycle on 6 vertices into complete multi-edges with a 2-break on the multi-edges (x₁, x₂), (x₃, x₄) followed by a 2-break on the multi-edges (x₁, x₄), (x₅, x₆). (C) A 2-break on an irregular edge corresponds to a reversal involving chromosome ends. (D) A 2-break on two irregular edges corresponds to a fusion. (Bottom panel) Two ways of transforming a fair edge (x, y) into a good edge: (top) by a 2-break on yellow edges or (bottom) by a 2-break on green edges. In either case, the follow-up processing of the generated simple path results in the same graph with the complete multi-edge (x, y).

Figure 7.

The breakpoint graph G(M,R,D,Q,H,C) (the complete multi-edges are not shown) after MGRA Stage 1 (top panel) and after MGRA Stages 1–2 (bottom panel). The edge colors represent mouse (red), rat (blue), dog (green), macaque (violet), human (orange), and chimpanzee (yellow) genomes. Vertices are labeled and colored similarly to Figure 4.

Figure 8.

(Top panel) The breakpoint graph of the genomes MRD_CARs (cyan) and MRD′_CARs (orange) reconstructed by inferCARs (common adjacencies are not shown). (Bold edges) Reliable adjacencies (resolved by MGRA Stage 1); (dashed edges) “ambiguous joins” (see Ma et al. 2006) made by inferCARs. Vertex colors are coded as in Figure 4. (Bottom panel) A most parsimonious transformation of one connected component (containing vertices 658h and 652h) of the breakpoint graph G(M,R,D,Q,H,C) from Figure 4. (First panel from left) The initial component is transformed with (second panel) a 2-break in primates, (third panel) a 2-break in rodents, and (fourth panel) two 2-breaks in dog resulting from processing of a good D + MRQCH path.

Figure 9.

(Left panel) The primate–rodent–carnivore controversy: an alternative between the primate–rodent (green tree) and the primate–carnivore clades (red tree). (Right panel) The phylogenetic tree T of seven mammalian genomes: mouse (red), rat (blue), dog (green), macaque (violet), human (orange), chimpanzee (yellow), and opossum (brown). Since the opossum branch is subject to a controversy, the dashed branches represent possible variations, while the solid branches are confident and do not depend on the opossum branch.