A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
DOI10.1137/S0097539794279067zbMATH Open0885.68073OpenAlexW2075495614MaRDI QIDQ4376199FDOQ4376199
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
Recommendations
dynamic programmingperfect phylogenyevolutionary treescombinatorial enumerationpolynomial delay algorithms
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)
Cited In (34)
- 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
- Title not available (Why is that?)
- A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
- 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
- Phenotype space and kinship assignment for the simpson index
- A simple characterization of the minimal obstruction sets for three-state perfect phylogenies
- 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
- Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples
- Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Two strikes against perfect phylogeny
- 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)
