A heuristic algorithm for minimum conflict individual haplotyping

Haplotype is a pattern of SNPs (Single Nucleotide Polymorphism) on a single chromosome. Constructing a pair of haplotypes from aligned and overlapping but intermixed and erroneous fragments of the chromosomal sequences is a nontrivial problem. Minimum error correction (MEC) model, which is the mostly used model, minimizes the number of errors to be corrected so that the pair of haplotypes can be constructed through consensus of the fragments. However, this model is effective only when the error rate of SNP fragments is low. To overcome this problem, Zhang et al. proposed a new model called Minimum Conflict Individual Haplotyping (MCIH) as an extension to MEC [1]. This new model uses both SNP fragment information and related genotype information for haplotype reconstruction. MCIH has already been proven to be a potential alternative in individual haplotyping. In this paper, we give a heuristic algorithm for MCIH that searches through alternative solutions using a gain measure and stops whenever no better solution can be achieved. Experimental results on real data show that our algorithm performs better than the best known algorithm for MEC and the algorithm for MCIH proposed by Zhang et al. [1].