Phylogeny- and parsimony-based haplotype inference with constraints

DOI10.1016/j.ic.2011.03.009zbMath1237.92045OpenAlexW2079446158MaRDI QIDQ418170

Till Tantau, Michael Elberfeld

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.03.009

zbMATH Keywords

polynomial-time algorithmsfixed-parameter algorithmsmaximum parsimonyperfect phylogeny

Mathematics Subject Classification ID

Problems related to evolution (92D15) Complexity and performance of numerical algorithms (65Y20)

Cites Work

• Unnamed Item
• Haplotyping with missing data via perfect path phylogenies
• Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices
• The complexity of reconstructing trees from qualitative characters and subtrees
• A linear-time algorithm for the perfect phylogeny haplotype problem
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• Haplotype Inferring Via Galled-Tree Networks Is NP-Complete
• Extended Islands of Tractability for Parsimony Haplotyping
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• Haplotype Inference Constrained by Plausible Haplotype Data
• Complete Parsimony Haplotype Inference Problem and Algorithms

This page was built for publication: Phylogeny- and parsimony-based haplotype inference with constraints