A Third Strike Against Perfect Phylogeny

Autor: Mark Jones, Leo van Iersel, Steven Kelk
Přispěvatelé: DKE Scientific staff, RS: FSE DACS BMI
Jazyk: angličtina
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
0301 basic medicine
Property (philosophy)
Discrete Mathematics (cs.DM)
Perfect phylogeny
Existential quantification
Open problem
0102 computer and information sciences
Biology
01 natural sciences
Set (abstract data type)
Combinatorics
03 medical and health sciences
FOS: Mathematics
Genetics
Mathematics - Combinatorics
maximum parsimony
perfect phylogeny
phylogenetic tree
Quantitative Biology - Populations and Evolution
Phylogeny
Ecology
Evolution
Behavior and Systematics
local obstructions conjecture
Conjecture
ALGORITHMS
Populations and Evolution (q-bio.PE)
Classification
030104 developmental biology
Character (mathematics)
010201 computation theory & mathematics
Four gamete condition
FOS: Biological sciences
Combinatorics (math.CO)
Constant (mathematics)
Regular Articles
Computer Science - Discrete Mathematics
Zdroj: Systematic Biology, 68(5)
Systematic Biology, 68(5), 814-827. Oxford University Press
Systematic Biology
Systematic Biology, 68(5), 814-827
ISSN: 1063-5157
Popis: Perfect phylogenies are fundamental in the study of evolutionary trees because they capture the situation when each evolutionary trait emerges only once in history; if such events are believed to be rare, then by Occam's Razor such parsimonious trees are preferable as a hypothesis of evolution. A classical result states that 2-state characters permit a perfect phylogeny precisely if each subset of 2 characters permits one. More recently, it was shown that for 3-state characters the same property holds but for size-3 subsets. A long-standing open problem asked whether such a constant exists for each number of states. More precisely, it has been conjectured that for any fixed integer $r$, there exists a constant $f(r)$ such that a set of $r$-state characters $C$ has a perfect phylogeny if and only if every subset of at most $f(r)$ characters has a perfect phylogeny. In this paper, we show that this conjecture is false. In particular, we show that for any constant $t$, there exists a set $C$ of $8$-state characters such that $C$ has no perfect phylogeny, but there exists a perfect phylogeny for every subset of $t$ characters. This negative result complements the two negative results ("strikes") of Bodlaender et al. We reflect on the consequences of this third strike, pointing out that while it does close off some routes for efficient algorithm development, many others remain open.
This article has been accepted for publication in Systematic Biology Published by Oxford University Press
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje