dorsal/arxiv
View SchemaOn the Complexity of Several Haplotyping Problems
| Authors | Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0505023 |
| URL | https://arxiv.org/abs/q-bio/0505023 |
Abstract
In this paper we present a collection of results pertaining to haplotyping. The first set of results concerns the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype data. More specifically, we show that an interesting, restricted case of Minimum Error Correction (MEC) is NP-hard, point out problems in earlier claims about a related problem, and present a polynomial-time algorithm for the ungapped case of Longest Haplotype Reconstruction (LHR). Secondly, we present a polynomial time algorithm for the problem of resolving genotype data using as few haplotypes as possible (the Pure Parsimony Haplotyping Problem, PPH) where each genotype has at most two ambiguous positions, thus solving an open problem posed by Lancia et al in "Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms."
{
"annotation_id": "3beef3ad-4487-4f66-b468-fcc3d89a7346",
"date_created": "2026-03-02T18:01:31.813000Z",
"date_modified": "2026-03-02T18:01:31.813000Z",
"file_hash": "91013ac146a189a3b66a2f3b930cb412a877959ab7b7737a0ceb1b281ab082e3",
"private": false,
"record": {
"abstract": "In this paper we present a collection of results pertaining to haplotyping.\nThe first set of results concerns the combinatorial problem of reconstructing\nhaplotypes from incomplete and/or imperfectly sequenced haplotype data. More\nspecifically, we show that an interesting, restricted case of Minimum Error\nCorrection (MEC) is NP-hard, point out problems in earlier claims about a\nrelated problem, and present a polynomial-time algorithm for the ungapped case\nof Longest Haplotype Reconstruction (LHR). Secondly, we present a polynomial\ntime algorithm for the problem of resolving genotype data using as few\nhaplotypes as possible (the Pure Parsimony Haplotyping Problem, PPH) where each\ngenotype has at most two ambiguous positions, thus solving an open problem\nposed by Lancia et al in \"Haplotyping Populations by Pure Parsimony: Complexity\nof Exact and Approximation Algorithms.\"",
"arxiv_id": "q-bio/0505023",
"authors": [
"Rudi Cilibrasi",
"Leo van Iersel",
"Steven Kelk",
"John Tromp"
],
"categories": [
"q-bio.GN"
],
"title": "On the Complexity of Several Haplotyping Problems",
"url": "https://arxiv.org/abs/q-bio/0505023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cfd467eb-cb8a-4b40-9f75-b3f33a1223fa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}