Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems

DOI10.1007/978-3-540-85238-4_24zbMath1173.68536OpenAlexW1576670503MaRDI QIDQ3599136

Till Tantau, Michael Elberfeld

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_24

zbMATH Keywords

computational complexitybioinformaticshaplotypingperfect phylogeniescircuit classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10)

Related Items

Phylogeny- and parsimony-based haplotype inference with constraints ⋮ Influence of tree topology restrictions on the complexity of haplotyping with missing data ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems

Uses Software

• HAPLO

Cites Work

• Unnamed Item
• Haplotyping with missing data via perfect path phylogenies
• On the complexity of SNP block partitioning under the perfect phylogeny model
• A polynomial case of the parsimony haplotyping problem
• A decomposition theorem for partially ordered sets
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Structure and importance of logspace-MOD class