Influence of tree topology restrictions on the complexity of haplotyping with missing data

DOI10.1016/J.TCS.2012.01.015MaRDI QIDQ428852zbMATHOpenAlexFDO

Authors Michael Elberfeld, Ilka Schnoor, Till Tantau

Publication date 25 June 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.01.015

zbMATH Keywords

computational complexitycomputational biologyfixed-parameter algorithmshaplotypingphylogenies

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• Parameterized and Exact Computation
• Haplotyping with missing data via perfect path phylogenies
• Phylogeny- and parsimony-based haplotype inference with constraints
• Phylogeny- and parsimony-based haplotype inference with constraints

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A linear-time algorithm for the perfect phylogeny haplotype problem
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Haplotyping with missing data via perfect path phylogenies
• Incomplete Directed Perfect Phylogeny
• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• On the complexity of SNP block partitioning under the perfect phylogeny model
• The complexity of reconstructing trees from qualitative characters and subtrees
• The complexity of satisfiability problems

Cited in

(5)

• Computational Science – ICCS 2005
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Parameterized and Exact Computation
• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• Haplotype Inferring Via Galled-Tree Networks Is NP-Complete

Describes a project that uses

Uses Software

• HAPLO

This page was built for publication: Influence of tree topology restrictions on the complexity of haplotyping with missing data

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