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 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.
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01964467
Contributor : Fabio Pardi <>
Submitted on : Tuesday, January 8, 2019 - 5:29:27 PM
Last modification on : Tuesday, July 9, 2019 - 2:20:52 PM
Long-term archiving on : Tuesday, April 9, 2019 - 1:19:45 PM

File

finding_MPtree.pdf
Explicit agreement for this submission

Identifiers

Collections

Citation

Steven Kelk, Fabio Pardi, Celine Scornavacca, Leo van Iersel. Finding a most parsimonious or likely tree in a network with respect to an alignment. Journal of Mathematical Biology, Springer Verlag (Germany), 2019, 78 (1-2), pp.527-547. ⟨10.1007/s00285-018-1282-2⟩. ⟨lirmm-01964467⟩

Share

Metrics

Record views

257

Files downloads

112