Deciding the existence of a cherry-picking sequence is hard on two trees
| Autor: | Janosch Döcker, Steven Kelk, Leo van Iersel, Simone Linz |
|---|---|
| Přispěvatelé: | DKE Scientific staff, RS: FSE DACS BMI |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Binary number Combinatorics Phylogenetic networks Phylogenetics Elimination orders Computer Science - Data Structures and Algorithms NP-hardness Quantitative Biology::Populations and Evolution Discrete Mathematics and Combinatorics Data Structures and Algorithms (cs.DS) Satisfiability Equivalence (formal languages) Quantitative Biology - Populations and Evolution Mathematics COMPLEXITY Phylogenetic tree Applied Mathematics Populations and Evolution (q-bio.PE) Temporal networks Phylogenetic network Quantitative Biology::Genomics Taxon FOS: Biological sciences Horizontal gene transfer TEMPORAL HYBRIDIZATION NUMBER MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics, 260, 131-143. Elsevier Discrete Applied Mathematics, 260 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.01.031 |
| Popis: | 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. Fixed some tiny things. Accepted for journal publication |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect