Lecture Notes in Computer Science, 2004, Volume 3240/2004, 266-277, DOI: 10.1007/978-3-540-30219-3_23

Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction

Alessandro Panconesi and Mauro Sozio

View Related Documents

Abstract

We study the single individual SNP haplotype reconstruction problem. We introduce a simple heuristic and prove experimentally that is very fast and accurate. In particular, when compared with a dynamic programming of [8] it is much faster and also more accurate. We expect Fast Hare to be very useful in practical applications. We also introduce a combinatorial problem related to the SNP haplotype reconstruction problem that we call Min Element Removal. We prove its NP-hardness in the gapless case and its O(log n)-approximability in the general case.

Fulltext Preview

Image of the first page of the fulltext document