A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies

DOI10.1137/S0097539794279067MaRDI QIDQ4376199zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Tandy J. Warnow

Publication date 10 February 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794279067

zbMATH Keywords

combinatorial enumerationdynamic programmingevolutionary treesperfect phylogenypolynomial delay algorithms

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Publication:4886095
• Incomplete Directed Perfect Phylogeny
• Two strikes against perfect phylogeny
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• Hypothesis testing in perfect phylogeny for a bounded number of characters

Cited in

(34)

• PULLPRU: a practical approach to estimate phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion
• Unique perfect phylogeny is intractable
• Character-based phylogeny construction and its application to tumor evolution
• Sharp upper and lower bounds on a restricted class of convex characters
• Enumeration of binary trees compatible with a perfect phylogeny
• Finding optimal triangulations parameterized by edge clique cover
• A linear-time algorithm for the perfect phylogeny haplotype problem
• Efficient approximation of convex recolorings
• scientific article; zbMATH DE number 1615277 (Why is no real title available?)
• On the Generality of Phylogenies from Incomplete Directed Characters
• Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters
• Phenotype space and kinship assignment for the simpson index
• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
• Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms
• Efficient computation of template matrices
• An algorithm for construction of all perfect phylogeny matrices
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• A simple characterization of the minimal obstruction sets for three-state perfect phylogenies
• Incomplete Directed Perfect Phylogeny
• scientific article; zbMATH DE number 910918 (Why is no real title available?)
• When and how the perfect phylogeny model explains evolution
• Two strikes against perfect phylogeny
• Parameterized and Exact Computation
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• Research in Computational Molecular Biology
• Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• Tree reconstruction from multi-state characters
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Incomplete directed perfect phylogeny in linear time
• Improved approximation algorithm for convex recoloring of trees
• The compatibility of binary characters on phylogenetic networks: Complexity and parameterized algorithms
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation

This page was built for publication: A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies

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