Paper Info
Title
Finding a most parsimonious or likely tree in a network with respect to an alignment
Abstract
Phylogenetic networks are often constructed by merging multiple conflicting phylogenetic 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.
Year
DOI
Venue
2017
10.1007/s00285-018-1282-2
Journal of Mathematical Biology
Keywords
Field
DocType
Phylogenetic tree, Phylogenetic network, Maximum parsimony, Maximum likelihood, NP-hardness, APX-hardness, 92D15, 68Q25, 92D20
Character evolution,Discrete mathematics,Combinatorics,Phylogenetic tree,Biconnected component,Tree rearrangement,Directed acyclic graph,Computational phylogenetics,Multiple sequence alignment,Mathematics,Phylogenetic network
Journal
Volume
Issue
ISSN
78
1-2
1432-1416
Citations 
PageRank 
References 
1
0.36
10
Authors
4
Name
Order
Citations
PageRank
Steven Kelk119325.60
Fabio Pardi2175.58
Celine Scornavacca321618.80
Leo van Iersel421524.58