Fast ancestral gene order reconstruction of genomes with unequal gene content

Abstract

Background: During evolution, genomes are modified by large scale structural events, such as rearrangements, deletions or insertions of large blocks of DNA. Of particular interest, in order to better understand how this type of genomic evolution happens, is the reconstruction of ancestral genomes, given a phylogenetic tree with extant genomes at its leaves. One way of solving this problem is to assume a rearrangement model, such as Double Cut and Join (DCJ), and find a set of ancestral genomes that minimizes the number of events on the input tree. Since this problem is NP-hard for most rearrangement models, exact solutions are practical only for small instances, and heuristics have to be used for larger datasets. This type of approach can be called event-based. Another common approach is based on finding conserved structures between the input genomes, such as adjacencies between genes, possibly also assigning weights that indicate a measure of confidence or probability that this particular structure is present on each ancestral genome, and then finding a set of non conflicting adjacencies that optimize some given function, usually trying to maximize total weight and minimizing character changes in the tree. We call this type of methods homology-based.

Results: In previous work, we proposed an ancestral reconstruction method that combines homology- and event-based ideas, using the concept of intermediate genomes, that arise in DCJ rearrangement scenarios. This method showed better rate of correctly reconstructed adjacencies than other methods, while also being faster, since the use of intermediate genomes greatly reduces the search space. Here, we generalize the intermediate genome concept to genomes with unequal gene content, extending our method to account for gene insertions and deletions of any length. In many of the simulated datasets, our proposed method had better results than MLGO and MGRA, two state-of-the-art algorithms for ancestral reconstruction with unequal gene content, while running much faster, making it more scalable to larger datasets.

Conclusion: Studing ancestral reconstruction problems under a new light, using the concept of intermediate genomes, allows the design of very fast algorithms by greatly reducing the solution search space, while also giving very good results. The algorithms introduced in this paper were implemented in an open-source software called RINGO (ancestral Reconstruction with INtermediate GenOmes), available at https://github.com/pedrofeijao/RINGO .

Keywords: Ancestral reconstruction; Double-cut-and-join; Gene insertions and deletions; Genome rearrangement; InDels; Small parsimony problem.

Fig. 1

Breakpoint graph BP(A,B) of genomes A={∘1^t,1^h2^t,2^h3^t,3^h4^t,4^h∘,∘5^t,5^h6^t,6^h7^t,7^h∘} and B={1^h2^h,2^t3^h,3^t4^t,4^h1^t,∘6^t,6^h5^t,5^h7^h,7^t∘}. Edges of A are green, of B are blue

Fig. 2

Breakpoint graph BP(A,B) of circular genomes G _A=(1,−3,5) and G _B=(1,2,3,4), with adjacency sets A={1^h3^h,3^t5^t,1^t5^h} and B={1^h2^t,2^h3^t,3^h4^t,4^h1^t}. Edges of A are green, and of B are blue. There is one AA-path and two AB-paths

Fig. 3

The unique optimal completion C of BP(A,B) from Fig. 2, where A-open (B-open) vertices are joined by green (blue) double edges, closing the AA-path and linking both AB-paths, which makes d DCJ ind(A,B)=n−c=3. The orange edges M ^′={1^h2^t,2^h4^h, 4^t3^h,3^t1^t,5^t5^h} form a set of non-crossing chords covering all vertices of C. By Claim 2, M ^′ leads to an intermediate genome. Notice that S={5^t5^h} is an artificial singleton, that is, a circular chromosome with only unique genes of A. Therefore, M=M ^′−S={1^h2^t,2^h4^h,4^t3^h,3^t1^t}, representing the circular chromosome (1,2,−4,−3), is an intermediate genome. M is present in the optimal scenario $\mathcal{S}=\{M_0=A,M_1=(1,-3)$, M ₂=(1,2,−4,−3),M ₃=B}, composed by one deletion, one insertion, and one reversal (DCJ)

Fig. 4

Given a balanced bicoloured graph G (at left), a breakpoint graph is constructed (at right), with genomes $A=\left\{1^t{1}^h,2^t{2}^h,{\overline{2}}^t{\overline{2}}^h,3^t{3}^h,{\overline{3}}^t{\overline{3}}^h,4^t{4}^h\right\}$ (in blue), $B=\left\{1^t{1}^h,2^t{\overline{2}}^h,{\overline{2}}^t{2}^h,3^t{\overline{3}}^h,{\overline{3}}^t{3}^h,4^t{4}^h\right\}$ (in green) and $C=\left\{1^t{2}^t,{\overline{2}}^t{3}^t,{\overline{3}}^t{4}^t,1^h{3}^h,2^h{\overline{3}}^h,{\overline{2}}^h{4}^h\right\}$ (in red). In this example, M=B⊆A∪B is a median (in dashed orange edges)

Fig. 5

To find adjacency weights for node α on a tree T, a new tree T ^′ is created where α and its subtree T1 are removed, and T ^′ is rerooted at γ, the parent node of α. Then, Eq. (4) is applied to find weights for γ, which are then assigned to node α on the original tree T

Fig. 6

Quality of the adjacency reconstruction for each dataset, with single gene indels (I=1, top plot) and with indel size ∈[1,5] (I=5, bottom plot). Each column group represents the average results of RINGO (with custom adjacency weights and branch length estimation with ME), MLGO and MGRA on each dataset, with the percentage of true positives and false positives, when comparing the simulated adjacencies and the reconstructed adjacencies in all internal nodes of the simulated trees

Fig. 7

DCJ-Indel distance between the simulated and reconstructed genomes, with only single gene indels (I=1, top plot) and with indel size ∈[1,5] (I=5, bottom plot). Each column group represents the average distances of RINGO, MLGO and MGRA on each dataset