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

DOI10.1016/j.tcs.2012.01.015zbMath1242.92049OpenAlexW2128990847MaRDI QIDQ428852

Ilka Schnoor, Till Tantau, Michael Elberfeld

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

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

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
• The complexity of reconstructing trees from qualitative characters and subtrees
• A linear-time algorithm for the perfect phylogeny haplotype problem
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
• Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data
• Incomplete Directed Perfect Phylogeny
• The complexity of satisfiability problems

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