Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems

DOI10.1007/978-3-540-85238-4_24MaRDI QIDQ3599136zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, Till Tantau

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

bioinformaticscircuit classescomputational complexityhaplotypingperfect phylogenies

Mathematics Subject Classification ID

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

Recommendations

• Phylogeny- and parsimony-based haplotype inference with constraints
• Phylogeny- and parsimony-based haplotype inference with constraints
• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• Influence of tree topology restrictions on the complexity of haplotyping with missing data
• A linear-time algorithm for the perfect phylogeny haplotype problem

Cites work

• A decomposition theorem for partially ordered sets
• A polynomial case of the parsimony haplotyping problem
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Descriptive complexity
• Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms
• Haplotyping with missing data via perfect path phylogenies
• On the complexity of SNP block partitioning under the perfect phylogeny model
• Structure and importance of logspace-MOD class

Cited in

(11)

• On the complexity of SNP block partitioning under the perfect phylogeny model
• Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers
• Phylogeny- and parsimony-based haplotype inference with constraints
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Efficient computation of template matrices
• On the Approximability of Some Haplotyping Problems
• Phylogeny- and parsimony-based haplotype inference with constraints
• Influence of tree topology restrictions on the complexity of haplotyping with missing data
• A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem
• Algorithms and Computation
• The phasing of heterozygous traits: Algorithms and complexity

Describes a project that uses

Uses Software

• HAPLO

This page was built for publication: Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems

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