Reconstructing rearrangement phylogenies of natural genomes

Abstract

Background: We study the classical problem of inferring ancestral genomes from a set of extant genomes under a given phylogeny, known as the Small Parsimony Problem (SPP). Genomes are represented as sequences of oriented markers, organized in one or more linear or circular chromosomes. Any marker may appear in several copies, without restriction on orientation or genomic location, known as the natural genomes model. Evolutionary events along the branches of the phylogeny encompass large scale rearrangements, including segmental inversions, translocations, gain and loss (DCJ-indel model). Even under simpler rearrangement models, such as the classical breakpoint model without duplicates, the SPP is computationally intractable. Nevertheless, the SPP for natural genomes under the DCJ-indel model has been studied recently, with limited success.

Methods: Building on prior work, we present a highly optimized ILP that is able to solve the SPP for sufficiently small phylogenies and gene families. A notable improvement w.r.t. the previous result is an optimized way of handling both circular and linear chromosomes. This is especially relevant to the SPP, since the chromosomal structure of ancestral genomes is unknown and the solution space for this chromosomal structure is typically large.

Results: We benchmark our method on simulated and real data. On simulated phylogenies we observe a considerable performance improvement on problems that include linear chromosomes. And even when the ground truth contains only one circular chromosome per genome, our method outperforms its predecessor due to its optimized handling of the solution space. The practical advantage becomes also visible in an analysis of seven Anopheles taxa.

Keywords: Ancestral reconstruction; Double-cut-and-join; Genome rearrangement; Integer linear programming; Small parsimony.

Fig. 1

A genome of five markers $1_1$, $1_2$, $2_1$, $3_1$, $4_1$ on a single linear chromosome

Fig. 2

Capping-Free Multi-Relational Diagram for two genomes on an unresolved homology (${\equiv }_1$) with families $\{1_1,1_2,1_3,1_4\},$ $\{2_1,2_2\},\{3_1,3_2\},\{4_1\},\{5_1\}.$

Fig. 3

Acrshort*cfmrd for the two genomes of Fig. 2 on a resolved homology (${\equiv }_2$) with families $\{1_1,1_3\}$, $\{1_2,1_4\}$, $\{2_1,2_2\}$, $\{3_1,3_2\}$, $\{4_1\}$, $\{5_1\}$. Note that (${\equiv }_2$) is a matching on (${\equiv }_1$)

Fig. 4

Left: A degenerate genome. Right: A linearization of it

Fig. 5

Left: This degenerate genome is not linearizable because of missing telomeres. Right: The genome becomes linearizable when adding telomeres. One linearization is that of Fig. 4

Algorithm 1

Capping-free Small Parsimony

Fig. 6

Solving times for SPP-DCJ and SPP-DCJ-v2 on simulated genomes with increasing numbers of telomeres. Solid lines represent corresponding median values

Fig. 7

Solving times for SPP-DCJ and SPP-DCJ-v2 on genomes generated by ZOMBI on a range of trees with increasing branch lengths with ancestral adjacencies inferred by DecoSTAR. Solid lines represent corresponding median values

Fig. 8

Mean precision, recall and F1 score for default and safer linearization mode for varying tree scales. Transparent ranges indicate minimum to maximum range of the five tested samples per step

Fig. 9

Average pre-processing and solving times of 50 samples for variants of SPP-DCJ-v2. NN - no additional pre-processing, IN - initial solution precomputed, IB - initial solution and lower bounds precomputed

Fig. 10

Cladogram for seven Anopheles taxa

Fig. 11

Gaps reported by gurobi with increasing solving times for SPP-DCJ and variants of SPP-DCJ-v2 until a time limit of 720 minutes. Right: Zoomed in on the first 25 minutes. NN - no additional pre-processing, IN - initial solution precomputed, IB - initial solution and lower bounds precomputed, IBF - initial solution and lower bounds precomputed, with variable ancestral family sizes