{
  "annotation_id": "f4d2054c-6880-404b-9768-830248f63cd3",
  "date_created": "2026-03-02T18:01:31.357000Z",
  "date_modified": "2026-03-02T18:01:31.357000Z",
  "file_hash": "6f2accbe84f026520bfc2c1a6ccc26a6b7bca96e1f2b4a82c5cb67313f55af10",
  "private": false,
  "record": {
    "abstract": "We present several new results pertaining to haplotyping. These results\nconcern the combinatorial problem of reconstructing haplotypes from incomplete\nand/or imperfectly sequenced haplotype fragments. We consider the complexity of\nthe problems Minimum Error Correction (MEC) and Longest Haplotype\nReconstruction (LHR) for different restrictions on the input data.\nSpecifically, we look at the gapless case, where every row of the input\ncorresponds to a gapless haplotype-fragment, and the 1-gap case, where at most\none gap per fragment is allowed. We prove that MEC is APX-hard in the 1-gap\ncase and still NP-hard in the gapless case. In addition, we question earlier\nclaims that MEC is NP-hard even when the input matrix is restricted to being\ncompletely binary. Concerning LHR, we show that this problem is NP-hard and\nAPX-hard in the 1-gap case (and thus also in the general case), but is\npolynomial time solvable in the gapless case.",
    "arxiv_id": "q-bio/0508012",
    "authors": [
      "Rudi Cilibrasi",
      "Leo van Iersel",
      "Steven Kelk",
      "John Tromp"
    ],
    "categories": [
      "q-bio.GN",
      "q-bio.QM"
    ],
    "doi": "10.1007/s00453-007-0029-z",
    "title": "On the Complexity of the Single Individual SNP Haplotyping Problem",
    "url": "https://arxiv.org/abs/q-bio/0508012"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "b856e810-0cdd-40c2-80c5-bb658f8eed4b",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}