A clustering algorithm for the single individual haplotyping problem

Everybody wants to know the difference between his genes and others´. The development of the biotechnology makes this more and more feasible. The PCR-based shotgun technology can produce large collection of aligned short fragments of (portions of/all) the chromosome of some individual. How to reconstruct the two haplotype strings (paternal and maternal) from these fragments is the key problem in this process. This computational problem is called the single individual haplotyping problem. Many algorithms have been proposed in the literature for the simplified models of it. Different from these existing algorithms, in this paper we present a clustering algorithm for this problem itself, not any derived models. Through computational experiments on the real human chromosome data, we confirm that this is a good idea.