Name
Abstract | ||
|---|---|---|
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]. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11557067_11 | WABI |
Keywords | Field | DocType |
restricted case,imperfectly sequenced haplotype data,results concern,open problem,haplotyping problem,ungapped case,related problem,polynomial time algorithm,polynomial-time algorithm,genotype data,combinatorial problem,error correction | Discrete mathematics,Combinatorics,Open problem,Computer science,Bipartite graph,Haplotype,Combinatorial optimization,Error detection and correction,Time complexity,Minimum error correction,Polynomial method | Conference |
Volume | ISSN | ISBN |
3692 | 0302-9743 | 3-540-29008-7 |
Citations | PageRank | References |
37 | 2.69 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rudi Cilibrasi | 1 | 128 | 13.21 |
| Leo van Iersel | 2 | 215 | 24.58 |
| Steven Kelk | 3 | 193 | 25.60 |
| John Tromp | 4 | 124 | 12.85 |