title: HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction.
abstract: Haplotype is a pattern of single nucleotide polymorphisms (SNPs) 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 aims 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 (HMEC) 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 (3) 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 an SNP matrix. Alternative gain measure is also given to reduce running time. We have compared our algorithm with other methods in terms of accuracy and running time on both simulated and real data, and our extensive experimental results indicate the superiority of our algorithm over others.
authors.affiliation: Department of Computer Science, University of Texas at Austin, Austin, TX 78712, USA.
authors.forename: Md Shamsuzzoha
authors.initials: MS
authors.lastname: Bayzid
authors.affiliation: Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA.
authors.forename: Md Maksudul
authors.initials: MM
authors.lastname: Alam
authors.affiliation: Department of Computer Science and Engineering, Univerity of California, Riverside, CA 92521, USA.
authors.forename: Abdullah
authors.initials: A
authors.lastname: Mueen
authors.affiliation: Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka 1000, Bangladesh.
authors.forename: Md Saidur
authors.initials: MS
authors.lastname: Rahman