Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2012 Jun 15;28(12):i283-91.
doi: 10.1093/bioinformatics/bts225.

Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss

Mukul S Bansal  1 , Eric J Alm, Manolis Kellis
Affiliations

Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss

Mukul S Bansal et al. Bioinformatics. .

Abstract

Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.

Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods.

Availability: Our programs can be freely downloaded from http://compbio.mit.edu/ranger-dtl/.

PubMed Disclaimer

Figures

Fig. 1.
Fig. 1.
Simple DTL scenarios. (a) and (b) depict two possible reconciliations of G and S: the dotted arcs show the mapping formula image (with the leaf mapping being specified by the leaf labels on the gene tree), and the label at each internal node of G specifies the type of event represented by that node. The reconciliation in (a) requires two transfers and one loss and the one in (b) requires one duplication and two losses
See this image and copyright information in PMC

References

    1. Andam C.P., Gogarten J.P. Biased gene transfer in microbial evolution. Nat. Rev. Microbiol. 2011;9:543–555. - PubMed
    1. Arvestad L., et al. The gene evolution model and computing its associated probabilities. J. ACM. 2009;56:7:1–7:44.
    1. Bansal M.S., et al. Heuristics for the gene-duplication problem: a Θ(n) speed-up for the local search. In: Speed T.P., Huang H., editors. RECOMB. Vol. 4453. Berlin Heidelberg: Springer; 2007. pp. 238–252. ofLecture Notes in Computer Science.
    1. Bender M.A., et al. Lowest common ancestors in trees and directed acyclic graphs. J. Algor. 2005;57:75–94.
    1. Boc A., et al. Inferring and validating horizontal gene transfer events using bipartition dissimilarity. Syst. Biol. 2010;59:195–211. - PubMed

Publication types