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

dynamic programmingperfect phylogenyevolutionary treescombinatorial enumerationpolynomial delay algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) 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)

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

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)