Dataset Information

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

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/.

SUBMITTER: Bansal MS

PROVIDER: S-EPMC3371857 | biostudies-literature | 2012 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Bansal Mukul S MS Alm Eric J EJ Kellis Manolis M

Bioinformatics (Oxford, England) 20120601 12

<h4>Motivation</h4>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 ...[more]

PMID: 22689773

Similar Datasets

Project description:BackgroundTwo non-homologous, isofunctional enzymes catalyze the penultimate step of chlorophyll a synthesis in oxygenic photosynthetic organisms such as cyanobacteria, eukaryotic algae and land plants: the light-independent (LIPOR) and light-dependent (POR) protochlorophyllide oxidoreductases. Whereas the distribution of these enzymes in cyanobacteria and land plants is well understood, the presence, loss, duplication, and replacement of these genes have not been surveyed in the polyphyletic and remarkably diverse eukaryotic algal lineages.ResultsA phylogenetic reconstruction of the history of the POR enzyme (encoded by the por gene in nuclei) in eukaryotic algae reveals replacement and supplementation of ancestral por genes in several taxa with horizontally transferred por genes from other eukaryotic algae. For example, stramenopiles and haptophytes share por gene duplicates of prasinophytic origin, although their plastid ancestry predicts a rhodophytic por signal. Phylogenetically, stramenopile pors appear ancestral to those found in haptophytes, suggesting transfer from stramenopiles to haptophytes by either horizontal or endosymbiotic gene transfer. In dinoflagellates whose plastids have been replaced by those of a haptophyte or diatom, the ancestral por genes seem to have been lost whereas those of the new symbiotic partner are present. Furthermore, many chlorarachniophytes and peridinin-containing dinoflagellates possess por gene duplicates. In contrast to the retention, gain, and frequent duplication of algal por genes, the LIPOR gene complement (chloroplast-encoded chlL, chlN, and chlB genes) is often absent. LIPOR genes have been lost from haptophytes and potentially from the euglenid and chlorarachniophyte lineages. Within the chlorophytes, rhodophytes, cryptophytes, heterokonts, and chromerids, some taxa possess both POR and LIPOR genes while others lack LIPOR. The gradual process of LIPOR gene loss is evidenced in taxa possessing pseudogenes or partial LIPOR gene compliments. No horizontal transfer of LIPOR genes was detected.ConclusionsWe document a pattern of por gene acquisition and expansion as well as loss of LIPOR genes from many algal taxa, paralleling the presence of multiple por genes and lack of LIPOR genes in the angiosperms. These studies present an opportunity to compare the regulation and function of por gene families that have been acquired and expanded in patterns unique to each of various algal taxa.

Project description:The rooting of phylogenetic trees permits important inferences about ancestral states and the polarity of evolutionary events. Recently, methods that reconcile discordance between gene-trees and species-trees-tree reconciliation methods-are becoming increasingly popular for rooting species trees. Rooting via reconciliation requires values for a particular parameter, the gene transfer to gene duplication ratio (T:D), which in current practice is estimated on the fly from discordances observed in the trees. To date, the accuracy of T:D estimates obtained by reconciliation analyses has not been compared to T:D estimates obtained by independent means, hence the effect of T:D upon inferences of species tree roots is altogether unexplored. Here we investigated the issue in detail by performing tree reconciliations of more than 10,000 gene trees under a variety of T:D ratios for two phylogenetic cases: a bacterial (prokaryotic) tree with 265 species and a fungal-metazoan (eukaryotic) tree with 31 species. We show that the T:D ratios automatically estimated by a current tree reconciliation method, ALE, generate virtually identical T:D ratios across bacterial genes and fungal-metazoan genes. The T:D ratios estimated by ALE differ 10- to 100-fold from robust, ALE-independent estimates from real data. More important is our finding that the root inferences using ALE in both datasets are strongly dependent upon T:D. Using more realistic T:D ratios, the number of roots inferred by ALE consistently increases and, in some cases, clearly incorrect roots are inferred. Furthermore, our analyses reveal that gene duplications have a far greater impact on ALE's preferences for phylogenetic root placement than gene transfers or gene losses do. Overall, we show that obtaining reliable species tree roots with ALE is only possible when gene duplications are abundant in the data and the number of falsely inferred gene duplications is low. Finding a sufficient sample of true gene duplications for rooting species trees critically depends on the T:D ratios used in the analyses. T:D ratios, while being important parameters of genome evolution in their own right, affect the root inferences with tree reconciliations to an unanticipated degree.

Dataset Information

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

Motivation

Results

Availability

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets