A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
From MaRDI portal
Publication:4376199
DOI10.1137/S0097539794279067zbMath0885.68073OpenAlexW2075495614MaRDI QIDQ4376199
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
dynamic programmingcombinatorial enumerationevolutionary treesperfect phylogenypolynomial delay algorithms
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Sharp upper and lower bounds on a restricted class of convex characters ⋮ Enumeration of binary trees compatible with a perfect phylogeny ⋮ Efficient approximation of convex recolorings ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples ⋮ A simple characterization of the minimal obstruction sets for three-state perfect phylogenies ⋮ Unnamed Item ⋮ PULLPRU: a practical approach to estimate phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion ⋮ Improved approximation algorithm for convex recoloring of trees ⋮ Convex recolorings of strings and trees: Definitions, hardness results and algorithms ⋮ Tree reconstruction from multi-state characters ⋮ Character-based phylogeny construction and its application to tumor evolution
