A simple characterization of the minimal obstruction sets for three-state perfect phylogenies

DOI10.1016/J.AML.2012.02.060zbMATH Open1250.92036arXiv1106.0874OpenAlexW2074185282MaRDI QIDQ450220FDOQ450220

David Fernández-Baca, Brad Shutters

Publication date: 13 September 2012

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Abstract: Lam, Gusfield, and Sridhar (2009) showed that a set of three-state characters has a perfect phylogeny if and only if every subset of three characters has a perfect phylogeny. They also gave a complete characterization of the sets of three three-state characters that do not have a perfect phylogeny. However, it is not clear from their characterization how to find a subset of three characters that does not have a perfect phylogeny without testing all triples of characters. In this note, we build upon their result by giving a simple characterization of when a set of three-state characters does not have a perfect phylogeny that can be inferred from testing all pairs of characters.

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

zbMATH Keywords

phylogeneticscomputational biologyperfect phylogeny

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Title not available (Why is that?)
• The complexity of reconstructing trees from qualitative characters and subtrees
• Efficient algorithms for inferring evolutionary trees
• Two strikes against perfect phylogeny
• Convex tree realizations of partitions
• Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three-State Characters
• Inferring Evolutionary History From DNA Sequences
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• The three-state perfect phylogeny problem reduces to 2-SAT

This page was built for publication: A simple characterization of the minimal obstruction sets for three-state perfect phylogenies

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