A heuristic algorithm for individual haplotyping with minimum error correction

Haplotype is a pattern of Single Nucleotide Polymorphisms (SNP) 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 approach states to minimize the number of errors to be corrected so that the pair of haplotypes can be constructed through consensus of the fragments. We give a heuristic algorithm that searches through alternative solutions using a gain measure and stops whenever no better solution can be achieved. Time complexity of each iteration is O(m³k) for an m × k SNP matrix where m and k are the number of fragments (number of rows) and number of SNP sites (number of columns) respectively in a SNP matrix. Alternative gain measure is also given to reduce running time. Experimental results show that our algorithm outperforms the best known previous algorithm.