CoChat
Sign Up
Cited by 77Genomics and Phylogenetic StudiesGenome Rearrangement AlgorithmsChromosomal and Genetic Variations

Most parsimonious reconciliation in the presence of gene duplication, loss, and deep coalescence using labeled coalescent trees

Open access
Wu, Yi-Chieh, Rasmussen, Matthew D., Bansal, Mukul S., Kellis, Manolis·2014·Genome Research
DOI 10.1101/gr.161968.113PMC PMC3941112
Open this paper in CoChat — free accountOpen PDF

Abstract

Accurate gene tree-species tree reconciliation is fundamental to inferring the evolutionary history of a gene family. However, although it has long been appreciated that population-related effects such as incomplete lineage sorting (ILS) can dramatically affect the gene tree, many of the most popular reconciliation methods consider discordance only due to gene duplication and loss (and sometimes horizontal gene transfer). Methods that do model ILS are either highly parameterized or consider a restricted set of histories, thus limiting their applicability and accuracy. To address these challenges, we present a novel algorithm DLCpar for inferring a most parsimonious (MP) history of a gene family in the presence of duplications, losses, and ILS. Our algorithm relies on a new reconciliation structure, the labeled coalescent tree (LCT), that simultaneously describes coalescent and duplication-loss history. We show that the LCT representation enables an exhaustive and efficient search over the space of reconciliations, and, for most gene families, the least common ancestor (LCA) mapping is an optimal solution for the species mapping between the gene tree and species tree in an MP LCT. Applying our algorithm to a variety of clades, including flies, fungi, and primates, as well as to simulated phylogenies, we achieve high accuracy, comparable to sophisticated probabilistic reconciliation methods, at reduced run time and with far fewer parameters. These properties enable inferences of the complex evolution of gene families across a broad range of species and large data sets.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1101/gr.161968.113

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • DLCpar (search) employs an iterative search for a locally optimal solution, which can differ from the globally optimal solution.

    “DLCpar (search) instead employs an iterative search for a locally optimal solution, which can differ from the globally optimal solution.”

    From OrthoFinder: phylogenetic orthology inference for comparative genomics (2019) · cites this paper as [32]

    The Methods section describes DLCpar as searching over all possible most-parsimonious reconciliations, and the Discussion says it explores the reconciliation space exhaustively. The paper instead attributes a hill-climbing, heuristic search to DLCoalRecon. It does not describe DLCpar as an iterative search that may stop at a local optimum. (LLM, conf=0.89)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

  • DLCpar (full) can have large runtimes even for relatively small gene trees.

    “DLCpar (full) considers the complete space of possible reconciliations to find the maximum parsimony solution under the DLC model but can have large runtimes even for relatively small gene trees.”

    From OrthoFinder: phylogenetic orthology inference for comparative genomics (2019) · cites this paper as [32]

    The Results (Biological data set of 16 fungal genomes; page unavailable) report that DLCpar runtimes can be long, but say the average is highly skewed by large gene families. The paper supports exhaustive reconciliation search; it does not establish the claim that runtimes can be large even for relatively small gene trees. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • The novel OrthoFinder method outperformed all methods other than DLCpar (full) in terms of accuracy on two independent simulated datasets.

    “In terms of accuracy, the novel OrthoFinder method outperformed all methods other than DLCpar (full) (Fig. 5a, Additional file 1: Table S2).”

    From OrthoFinder: phylogenetic orthology inference for comparative genomics (2019) · cites this paper as [32]

    The Results section on simulated data sets compares DLCpar with DLCoalRecon and MPR on fly and primate data sets. Searches for OrthoFinder and “DLCpar (full)” found no passage evaluating OrthoFinder, so this copy cannot verify the attributed accuracy ranking. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 59

  1. Åkerborg Ö, Sennblad B, Arvestad L, Lagergren J 2009 Simultaneous Bayesian gene tree reconstruction and reconciliation analysis. Proc Natl Acad Sci 106: 5714– 5719 19299507 PMC2667006
  2. Arvestad L, Berglund A-C, Lagergren J, Sennblad B 2004 Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution. In Proceedings of the eighth annual international conference on research in computational molecular biology, RECOMB '04, pp. 326–335. ACM, New York
  3. Avise JC, Robinson TJ 2008 Hemiplasy: A new term in the lexicon of phylogenetics. Syst Biol 57: 503– 507 18570042
  4. Bansal MS, Alm EJ, Kellis M 2012 Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 28: i283– i291 22689773 PMC3371857
  5. Boussau B, Szöllosi GJ, Duret L, Gouy M, Tannier E, Daubin V 2013 Genome-scale coestimation of species and gene trees. Genome Res 23: 323– 330 23132911 PMC3561873
  6. Butler G, Rasmussen MD, Lin MF, Santos MA, Sakthikumar S, Munro CA, Rheinbay E, Grabherr M, Forche A, Reedy JL, 2009 Evolution of pathogenicity and sexual reproduction in eight Candida genomes. Nature 459: 657– 662 19465905 PMC2834264
  7. Chang W-C, Eulenstein O 2006 Reconciling gene trees with apparent polytomies. In Lecture notes in computer science (ed. Chen DZ, Lee D), Vol. 4112, pp. 235–244. Springer, Berlin
  8. Chen K, Durand D, Farach-Colton M 2000 NOTUNG: A program for dating gene duplications and optimizing gene family trees. J Comput Biol 7: 429– 447 11108472
  9. Datta RS, Meacham C, Samad B, Neyer C, Sjölander K 2009 Berkeley phog: Phylofacts orthology group prediction web server. Nucleic Acids Res 37: W84– W89 19435885 PMC2703887
  10. David LA, Alm EJ 2011 Rapid evolutionary innovation during an archaean genetic expansion. Nature 469: 93– 96 21170026
  11. Degnan JH 2013 Anomalous unrooted gene trees. Syst Biol 62: 574– 590 23576318
  12. Degnan JH, Rosenberg NA 2006 Discordance of species trees with their most likely gene trees. PLoS Genet 2: e68 16733550 PMC1464820
  13. Degnan JH, Rosenberg NA 2009 Gene tree discordance, phylogenetic inference and the multispecies coalescent. Trends Ecol Evol 24: 332– 340 19307040
  14. Degnan JH, DeGiorgio M, Bryant D, Rosenberg NA 2009 Properties of consensus methods for inferring species trees from gene trees. Syst Biol 58: 35– 54 20525567 PMC2909780
  15. Degnan JH, Rosenberg NA, Stadler T 2012 A characterization of the set of species trees that produce anomalous ranked gene trees. IEEE/ACM Trans Comput Biol Bioinform 9: 1558– 1568 22868677
  16. Doyon J-P, Chauve C, Hamel S 2008 Algorithms for exploring the space of gene tree/species tree reconciliations. In Lecture notes in computer science (ed. Nelson CE, Vialette S), Vol. 5267, pp. 1–13. Springer, Berlin 21464510
  17. Doyon J-P, Chauve C, Hamel S 2009 Space of gene/species trees reconciliations and parsimonious models. J Comput Biol 16: 1399– 1418 19754270
  18. Doyon J-P, Scornavacca C, Gorbunov KY, Szöllősi GJ, Ranwez V, Berry V 2011 An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers. In Lecture notes in computer science (ed. Tannier E), Vol. 6398, pp. 93–108. Springer, Berlin
  19. Doyon J-P, Chauve C, Hamel S 2012 An efficient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework. IEEE/ACM Trans Comput Biol Bioinfor 9: 26– 39 21464510
  20. Drummond A, Rambaut A 2007 Beast: Bayesian evolutionary analysis by sampling trees. BMC Evol Biol 7: 214 17996036 PMC2247476
  21. Dubb L 2005 “A likelihood model of gene family evolution.” PhD thesis, University of Washington, Seattle
  22. Durand D, Hallórsson BV, Vernot B 2006 A hybrid micro-macroevolutionary approach to gene tree reconstruction. J Comput Biol 13: 320– 335 16597243
  23. Gascuel O 1997 BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data. Mol Biol Evol 14: 685– 695 9254330
  24. Górecki P, Eulenstein O 2011 A linear time algorithm for error-corrected reconciliation of unrooted gene trees. In Lecture notes in computer science (ed. Chen J, et al.), Vol. 6674, pp. 148–159. Springer, Berlin
  25. Guindon S, Gascuel O 2003 A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Syst Biol 52: 696– 704 14530136
  26. Hahn M 2007 Bias in phylogenetic tree reconciliation methods: Implications for vertebrate genome evolution. Genome Biol 8: R141 17634151 PMC2323230
  27. Hahn MW, De Bie T, Stajich JE, Nguyen C, Cristianini N 2005 Estimating the tempo and mode of gene family evolution from comparative genomic data. Genome Res 15: 1153– 1160 16077014 PMC1182228
  28. Huang H, Knowles LL 2009 What is the danger of the anomaly zone for empirical phylogenetics? Syst Biol 58: 527– 536 20525606
  29. Huerta-Cepas J, Dopazo H, Dopazo J, Gabaldon T 2007 The human phylome. Genome Biol 8: R109 17567924 PMC2394744
  30. Koonin EV 2005 Orthologs, paralogs, and evolutionary genomics. Annu Rev Genet 39: 309– 338 16285863
  31. Kubatko LS, Degnan JH 2007 Inconsistency of phylogenetic estimates from concatenated data under coalescence. Syst Biol 56: 17– 24 17366134
  32. Lafond M, Swenson KM, El-Mabrouk N 2012 An optimal reconciliation algorithm for gene trees with polytomies. In Lecture notes in computer science (ed. Raphael B, Tang J), Vol. 7534, pp. 106–122. Springer, Berlin
  33. Li H, Coghlan A, Ruan J, Coin LJ, Hériché JK, Osmotherly L, Li R, Liu T, Zhang Z, Bolund L, 2006 TreeFam: A curated database of phylogenetic trees of animal gene families. Nucleic Acids Res 34: D572– D580 16381935 PMC1347480
  34. Liu L, Edwards SV 2009 Phylogenetic analysis in the anomaly zone. Syst Biol 58: 452– 460 20525599
  35. Liu L, Pearl DK 2007 Species trees from gene trees: Reconstructing Bayesian posterior distributions of a species phylogeny using estimated gene tree distributions. Syst Biol 56: 504– 514 17562474
  36. Liu K, Raghavan S, Nelesen S, Linder CR, Warnow T 2009 Rapid and accurate large-scale coestimation of sequence alignments and phylogenetic trees. Science 324: 1561– 1564 19541996
  37. Lynch M, Conery JS 2000 The evolutionary fate and consequences of duplicate genes. Science 290: 1151– 1155 11073452
  38. Mi H, Muruganujan A, Thomas PD 2013 Panther in 2013: Modeling the evolution of gene function, and other gene attributes, in the context of phylogenetic trees. Nucleic Acids Res 41: D377– D386 23193289 PMC3531194
  39. Ohno S 1970 Evolution by gene duplication. Springer-Verlag, New York
  40. Pamilo P, Nei M 1988 Relationships between gene trees and species trees. Mol Biol Evol 5: 568– 583 3193878
  41. Peterson ME, Chen F, Saven JG, Roos DS, Babbitt PC, Sali A 2009 Evolutionary constraints on structural similarity in orthologs and paralogs. Protein Sci 18: 1306– 1315 19472362 PMC2774440
  42. Rannala B, Yang Z 2003 Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci. Genetics 164: 1645– 1656 12930768 PMC1462670
  43. Rasmussen MD, Kellis M 2007 Accurate gene-tree reconstruction by learning gene- and species-specific substitution rates across multiple complete genomes. Genome Res 17: 1932– 1942 17989260 PMC2099600
  44. Rasmussen MD, Kellis M 2011 A Bayesian approach for fast and accurate gene tree reconstruction. Mol Biol Evol 28: 273– 290 20660489 PMC3002250
  45. Rasmussen MD, Kellis M 2012 Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Res 22: 755– 765 22271778 PMC3317157
  46. Ronquist F, Huelsenbeck JP 2003 MrBayes 3: Bayesian phylogenetic inference under mixed models. Bioinformatics 19: 1572– 1574 12912839
  47. Rosenberg NA 2002 The probability of topological concordance of gene trees and species trees. Theor Popul Biol 61: 225– 247 11969392
  48. Scornavacca C, Paprotny W, Berry V, Ranwez V 2013 Representing a set of reconciliations in a compact way. J Bioinform Comput Biol 11: 1250025 23600816
  49. Stamatakis A 2006 RAxML-VI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 22: 2688– 2690 16928733
  50. Tajima F 1983 Evolutionary relationship of DNA sequences in finite populations. Genetics 105: 437– 460 6628982 PMC1202167
  51. Than CV, Rosenberg NA 2011 Consistency properties of species tree inference by minimizing deep coalescences. J Comput Biol 18: 1– 15 21210728
  52. Tofigh A, Hallett M, Lagergren J 2011 Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans Comput Biol Bioinform 8: 517– 535 21233529
  53. Vernot B, Stolzer M, Goldman A, Durand D 2007 Reconciliation with non-binary species trees. J Comput Biol 15: 981– 1006 18808330 PMC3205801
  54. Vilella AJ, Severin J, Ureta-Vidal A, Heng L, Durbin R, Birney E 2009 EnsemblCompara GeneTrees: Complete, duplication-aware phylogenetic trees in vertebrates. Genome Res 19: 327– 335 19029536 PMC2652215
  55. Wu T, Zhang L 2011 Structural properties of the reconciliation space and their applications in enumerating nearly-optimal reconciliations between a gene tree and a species tree. BMC Bioinformatics 12: S7 22151151 PMC3283320
  56. Wu Y-C, Rasmussen MD, Bansal MS, Kellis M 2013 Treefix: Statistically informed gene tree error correction using species trees. Syst Biol 62: 110– 120 22949484 PMC3526801
  57. Zhang L 2011 From gene trees to species trees II: Species tree inference by minimizing deep coalescence events. IEEE/ACM Trans Comput Biol Bioinform 8: 1685– 1691 21576759
  58. Zheng Y, Zhang L 2013 Effect of incomplete lineage sorting on tree-reconciliation-based inference of gene duplication. In Lecture notes in computer science (ed. Cai Z, et al.), Vol. 7875, pp. 261–272. Springer, Berlin 26356016
  59. Zmasek CM, Eddy SR 2002 Rio: Analyzing proteomes by automated phylogenomics using resampled inference of orthologs. BMC Bioinformatics 3: 14 12028595 PMC116988

Cited by

Sorted by citations

Authors
Wu, Y.-C., Rasmussen, M. D., Bansal, M. S., & Kellis, M.
Affiliations
  • MIT Computer Science and Artificial Intelligence Laboratory (US)
  • Cornell University (US)
  • Broad Institute (US)
Corresponding author
  • Wu, Yi-Chieh
  • Kellis, Manolis
ORCID
Venue
Genome Research
Publisher
Cold Spring Harbor Laboratory
Published
2013-12-05
Volume
24
Issue
3
Pages
475-486
ISSN
1088-9051 (ISSN-L)
DOI
10.1101/gr.161968.113
PMC
PMC3941112
OpenAlex
W2120836981
Cited by
77
References
1
Citations by year
2026: 4 · 2025: 6 · 2024: 3 · 2023: 7 · 2022: 8 · 2021: 6 · 2020: 9 · 2019: 7 · 2018: 7 · 2017: 8 · 2016: 3 · 2015: 4 · 2014: 5
Type
posted content
Language
en
Open access
Locations
  • Genome Research (publishedVersion)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by-nc)
  • PubMed Central (publishedVersion, cc-by-nc)
  • PubMed (publishedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
  • HighWire Press Open Archive (submittedVersion)
Funders
  • National Science Foundation (0644282, CAREER)
  • National Institutes of Health
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
  • Life Sciences › Agricultural and Biological Sciences › Plant Science › Chromosomal and Genetic Variations
Keywords
gene tree-species tree reconciliation, gene duplication, gene loss, incomplete lineage sorting, gene family evolution
MeSH terms
Algorithms, Animals, Diptera, Fungi, Genes, Multigene Family, Models, Genetic, Phylogeny, Primates, Species Specificity, Genome, Gene Deletion, Evolution, Molecular, Gene Duplication, Gene Transfer, Horizontal

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review