Back to Search
Start Over
Finding a most parsimonious or likely tree in a network with respect to an alignment
- Source :
- Journal of Mathematical Biology, Journal of Mathematical Biology, Springer Verlag (Germany), 2019, 78 (1-2), pp.527-547. ⟨10.1007/s00285-018-1282-2⟩, Journal of Mathematical Biology, 2019, 78 (1-2), pp.527-547. ⟨10.1007/s00285-018-1282-2⟩, Journal of Mathematical Biology, 78(1-2), 527-547. Springer Verlag
- Publication Year :
- 2018
- Publisher :
- Springer Science and Business Media LLC, 2018.
-
Abstract
- International audience; Phylogenetic networks are often constructed by merging multiple conflicting phyloge-netic signals into a directed acyclic graph. It is interesting to explore whether a network constructed in this way induces biologically-relevant phylogenetic signals that were not present in the input. Here we show that, given a multiple alignment A for a set of taxa X and a rooted phylogenetic network N whose leaves are labelled by X , it is NP-hard to locate a most parsimonious phylogenetic tree displayed by N (with respect to A) even when the level of N-the maximum number of reticulation nodes within a biconnected component-is 1 and A contains only 2 distinct states. (If, additionally, gaps are allowed the problem becomes APX-hard.) We also show that under the same conditions, and assuming a simple binary symmetric model of character evolution, finding a most likely tree displayed by the network is NP-hard. These negative results contrast with earlier work on parsimony in which it is shown that if A consists of a single column the problem is fixed parameter tractable in the level. We conclude with a discussion of why, despite the NP-hardness, both the parsimony and likelihood problem can likely be well-solved in practice.
- Subjects :
- Character evolution
Genetic Speciation
RECOMBINATION
92D20
[SDV.BID.SPT]Life Sciences [q-bio]/Biodiversity/Systematics, Phylogenetics and taxonomy
01 natural sciences
Article
010305 fluids & plasmas
Evolution, Molecular
APX-hardness
Set (abstract data type)
Combinatorics
03 medical and health sciences
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
0103 physical sciences
NP-hardness
Animals
Humans
MAXIMUM-LIKELIHOOD
Phylogeny
030304 developmental biology
Mathematics
Phylogenetic network
0303 health sciences
Multiple sequence alignment
Models, Genetic
Phylogenetic tree
Applied Mathematics
68Q25
Computational Biology
Mathematical Concepts
Directed acyclic graph
[SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM]
Agricultural and Biological Sciences (miscellaneous)
Tree (graph theory)
EVOLUTION
92D15
Maximum parsimony
MODEL
Modeling and Simulation
[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
BAYESIAN-INFERENCE
Algorithms
Maximum likelihood
Subjects
Details
- ISSN :
- 14321416 and 03036812
- Volume :
- 78
- Database :
- OpenAIRE
- Journal :
- Journal of Mathematical Biology
- Accession number :
- edsair.doi.dedup.....bea0ae5829be6be5023a6aafb42e7b2f