On the complexity of several haplotyping problems

R. Cilibrasi, L.J.J. Iersel, van, S.M. Kelk, J.T. Tromp

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

61 Citations (Scopus)


We present several new 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, question 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 [15].
Original languageEnglish
Title of host publicationAlgorithms in bioinformatics : 5th international workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005 : proceedings
EditorsR. Casadio, G. Myers
Place of PublicationBerlin
ISBN (Print)3-540-29008-7
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'On the complexity of several haplotyping problems'. Together they form a unique fingerprint.

Cite this