Back to Search
Start Over
Deciding the existence of a cherry-picking sequence is hard on two trees.
- Source :
-
Discrete Applied Mathematics . May2019, Vol. 260, p131-143. 13p. - Publication Year :
- 2019
-
Abstract
- Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence , a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and temporal phylogenetic networks, our result proves that it is NP-complete to determine the existence of a temporal phylogenetic network that contains topological embeddings of both trees. The hardness result also greatly strengthens previous inapproximability results for the minimum temporal-hybridization number problem. This is the optimization version of the problem where we wish to construct a temporal phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and that has a minimum number of indegree-2 nodes, which represent events such as hybridization and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter tractability results in this area are likely to ensure the continued relevance of the temporal phylogenetic network model. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 260
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 136343943
- Full Text :
- https://doi.org/10.1016/j.dam.2019.01.031