Efficient error correction algorithms for gene tree reconciliation based on duplication, duplication and loss, and deep coalescence

Abstract

Background: Gene tree - species tree reconciliation problems infer the patterns and processes of gene evolution within a species tree. Gene tree parsimony approaches seek the evolutionary scenario that implies the fewest gene duplications, duplications and losses, or deep coalescence (incomplete lineage sorting) events needed to reconcile a gene tree and a species tree. While a gene tree parsimony approach can be informative about genome evolution and phylogenetics, error in gene trees can profoundly bias the results.

Results: We introduce efficient algorithms that rapidly search local Subtree Prune and Regraft (SPR) or Tree Bisection and Reconnection (TBR) neighborhoods of a given gene tree to identify a topology that implies the fewest duplications, duplication and losses, or deep coalescence events. These algorithms improve on the current solutions by a factor of n for searching SPR neighborhoods and n2 for searching TBR neighborhoods, where n is the number of taxa in the given gene tree. They provide a fast error correction protocol for ameliorating the effects of gene tree error by allowing small rearrangements in the topology to improve the reconciliation cost. We also demonstrate a simple protocol to use the gene rearrangement algorithm to improve gene tree parsimony phylogenetic analyses.

Conclusions: The new gene tree rearrangement algorithms provide a fast method to address gene tree error. They do not make assumptions about the underlying processes of genome evolution, and they are amenable to analyses of large-scale genomic data sets. These algorithms are also easily incorporated into gene tree parsimony phylogenetic analyses, potentially producing more credible estimates of reconciliation cost.

Figure 1

An TBR operation. Tree T' = TBR_T(v, x, y) results from T after performing single TBR operation.

Figure 2

The NNI adjacency graph. (a) The tree $\overline{G}$ is obtained from G by pruning and regrafting subtree G_v to the root of G. The vertex x ∈ V(G) is suppressed, and the new vertex above root in $\overline{G}$ is named x. (b) Two NNI operations NNI_G'(z') and NNI_G'(z) produce left-child G'_l and right-child G'_r of G' in $\mathcal{ X }$.