A Polynomial-Time Algorithm for Near-Perfect Phylogeny

DOI10.1137/S0097539799350839MaRDI QIDQ4429677zbMATH OpenFDO

Authors Jens Lagergren, David Fernández-Baca

Publication date 28 September 2003

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

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

zbMATH Keywords

algorithmsparsimonyphylogenycomputational biologySteiner treeperfect phylogenyevolutionary treescharacter-based methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Mathematical biology in general (92B99)

Recommendations

• scientific article; zbMATH DE number 2102787
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• Publication:4886095
• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees

Cited in

(18)

• Research in Computational Molecular Biology
• Parameterized and Exact Computation
• Incomplete directed perfect phylogeny in linear time
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Optimal Completion of Incomplete Gene Trees in Polynomial Time Using OCTAL
• 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
• Approximation algorithms for the fixed-topology phylogenetic number problem
• A colored graph approach to perfect phylogeny with persistent characters
• Additive approximation for near-perfect phylogeny construction
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples
• Efficient approximation of convex recolorings
• Approximation algorithms for tree alignment with a given phylogeny
• Parameterized algorithms for the Steiner arborescence problem on a hypercube
• scientific article; zbMATH DE number 2102787 (Why is no real title available?)

This page was built for publication: A Polynomial-Time Algorithm for Near-Perfect Phylogeny

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