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

DOI10.1016/J.AML.2012.02.060MaRDI QIDQ450220zbMATH OpenOpenAlexFDO

Authors Brad Shutters, David Fernández-Baca

Publication date 13 September 2012

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

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)

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.

Recommendations

• Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters
• Publication:4886095
• The three-state perfect phylogeny problem reduces to 2-SAT
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• scientific article; zbMATH DE number 1615277

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• Convex tree realizations of partitions
• Efficient algorithms for inferring evolutionary trees
• Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters
• Inferring Evolutionary History From DNA Sequences
• The complexity of reconstructing trees from qualitative characters and subtrees
• The three-state perfect phylogeny problem reduces to 2-SAT
• Two strikes against perfect phylogeny

Cited in

(1)

• Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters

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)