On the existence of a cherry-picking sequence

DOI10.1016/J.TCS.2017.12.005MaRDI QIDQ1694728zbMATH OpenOpenAlexFDO

Authors Janosch Döcker, Simone Linz

Publication date 6 February 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.04127

zbMATH Keywords

2P2N-3-SATcherry-picking sequenceintermezzophylogenetic treetemporal phylogenetic network

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Combinatorics in computer science (68R05) Problems related to evolution (92D15)

Abstract: Recently, the minimum number of reticulation events that is required to simultaneously embed a collection P of rooted binary phylogenetic trees into a so-called temporal network has been characterized in terms of cherry-picking sequences. Such a sequence is a particular ordering on the leaves of the trees in P. However, it is well-known that not all collections of phylogenetic trees have a cherry-picking sequence. In this paper, we show that the problem of deciding whether or not P has a cherry-picking sequence is NP-complete for when P contains at least eight rooted binary phylogenetic trees. Moreover, we use automata theory to show that the problem can be solved in polynomial time if the number of trees in P and the number of cherries in each such tree are bounded by a constant.

Recommendations

• Deciding the existence of a cherry-picking sequence is hard on two trees
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Novel phylogenetic network distances based on cherry picking
• On cherry-picking and network containment
• Combining Networks Using Cherry Picking Sequences

Cites work

• Bounding the number of hybridisation events for a consistent evolutionary history
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Computing the minimum number of hybridization events for a consistent evolutionary history
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• Introduction to algorithms.
• On the complexity of computing the temporal hybridization number for two phylogenies

Cited in

(2)

• Deciding the existence of a cherry-picking sequence is hard on two trees
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies

This page was built for publication: On the existence of a cherry-picking sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1694728)