Reconstruction of time-consistent species trees.
Gene evolution
Horizontal gene transfer
Polynomial-time algorithm
Species evolution
Time-consistency
Tree reconciliation
Journal
Algorithms for molecular biology : AMB
ISSN: 1748-7188
Titre abrégé: Algorithms Mol Biol
Pays: England
ID NLM: 101265088
Informations de publication
Date de publication:
2020
2020
Historique:
received:
29
05
2020
accepted:
25
07
2020
entrez:
27
8
2020
pubmed:
28
8
2020
medline:
28
8
2020
Statut:
epublish
Résumé
The history of gene families-which are equivalent to event-labeled gene trees-can to some extent be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are "biologically feasible" which is the case if one can find a species tree with which the gene tree can be reconciled in a time-consistent way. In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a time-consistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a "time-consistent" species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity.
Sections du résumé
BACKGROUND
BACKGROUND
The history of gene families-which are equivalent to event-labeled gene trees-can to some extent be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are "biologically feasible" which is the case if one can find a species tree with which the gene tree can be reconciled in a time-consistent way.
RESULTS
RESULTS
In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a time-consistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a "time-consistent" species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity.
Identifiants
pubmed: 32843891
doi: 10.1186/s13015-020-00175-0
pii: 175
pmc: PMC7439642
doi:
Types de publication
Journal Article
Langues
eng
Pagination
16Informations de copyright
© The Author(s) 2020.
Déclaration de conflit d'intérêts
Competing interestsThe authors declare that they have no competing interests.
Références
BMC Bioinformatics. 2011 Apr 28;12:124
pubmed: 21526987
BMC Bioinformatics. 2008 Dec 04;9:518
pubmed: 19055798
Nat Methods. 2016 May;13(5):425-30
pubmed: 27043882
IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):517-35
pubmed: 21233529
Front Genet. 2017 Oct 31;8:165
pubmed: 29163633
Algorithms Mol Biol. 2018 Feb 06;13:2
pubmed: 29441122
Trends Genet. 2000 May;16(5):227-31
pubmed: 10782117
J Math Biol. 2019 Jun;78(7):2015-2057
pubmed: 30968198
Bioinformatics. 2012 Jun 15;28(12):i283-91
pubmed: 22689773
IEEE/ACM Trans Comput Biol Bioinform. 2019 Jul-Aug;16(4):1077-1090
pubmed: 28622673
PLoS Comput Biol. 2015 May 28;11(5):e1004095
pubmed: 26020646
J Comput Biol. 2011 Jan;18(1):59-65
pubmed: 20715926
Genes (Basel). 2017 Sep 29;8(10):
pubmed: 28961181
Algorithms Mol Biol. 2017 Mar 11;12:4
pubmed: 28293276
Front Microbiol. 2018 May 15;9:973
pubmed: 29867876
J Comput Biol. 2009 Oct;16(10):1399-418
pubmed: 19754270
J Math Biol. 2018 Nov;77(5):1459-1491
pubmed: 29951855
PLoS Comput Biol. 2009 Jan;5(1):e1000262
pubmed: 19148271
Algorithms Mol Biol. 2020 Apr 09;15:5
pubmed: 32308731
J Math Biol. 2020 Apr;80(5):1459-1495
pubmed: 32002659
Algorithms Mol Biol. 2017 Aug 29;12:23
pubmed: 28861118
Nucleic Acids Res. 2008 Jan;36(Database issue):D250-4
pubmed: 17942413
PLoS One. 2014 Aug 19;9(8):e105015
pubmed: 25137074
J Math Biol. 2019 Aug;79(3):969-986
pubmed: 31111195
IEEE/ACM Trans Comput Biol Bioinform. 2017 May-Jun;14(3):587-599
pubmed: 28055898
Proc Natl Acad Sci U S A. 2015 Feb 17;112(7):2058-63
pubmed: 25646426
Genetics. 1992 Jul;131(3):753-60
pubmed: 1628816
J Math Biol. 2017 Jul;75(1):199-237
pubmed: 27904954
J Math Biol. 2013 Jan;66(1-2):399-420
pubmed: 22456957
Genome Res. 2003 Sep;13(9):2178-89
pubmed: 12952885
J Math Biol. 2020 Feb;80(3):865-953
pubmed: 31691135
BMC Bioinformatics. 2017 Mar 14;18(Suppl 3):76
pubmed: 28361686
Mol Biol Evol. 1983 Dec;1(1):57-66
pubmed: 6100986
Algorithms Mol Biol. 2016 Apr 16;11:4
pubmed: 27087831