On the complexity of SNP block partitioning under the perfect phylogeny model

DOI10.1016/j.disc.2008.04.002zbMath1181.92030OpenAlexW2154651106MaRDI QIDQ1045048

Roded Sharan, Tzvika Hartman, Till Nierhoff, Till Tantau, Jens Gramm

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.002

zbMATH Keywords

partitioning problemsperfect phylogeny haplotypingperfect path phylogeny

Mathematics Subject Classification ID

Problems related to evolution (92D15) Genetics and epigenetics (92D10) Complexity and performance of numerical algorithms (65Y20) Systems biology, networks (92C42)

Related Items (4)

Haplotyping with missing data via perfect path phylogenies ⋮ Influence of tree topology restrictions on the complexity of haplotyping with missing data ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems ⋮ Haplotype Inference Constrained by Plausible Haplotype Data

Cites Work

• Unnamed Item
• Unnamed Item
• Haplotyping with missing data via perfect path phylogenies
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• The hardness of 3-uniform hypergraph coloring
• Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers
• On the hardness of approximating minimization problems
• Parameterized and Exact Computation
• Efficient algorithms for inferring evolutionary trees

This page was built for publication: On the complexity of SNP block partitioning under the perfect phylogeny model