Bayzid, Md. ShamsuzzohaAlam, Md. MaksudulMueen, AbdullahRahman, Md. Saidur2017-09-182017-09-182013-01-28Md. Shamsuzzoha Bayzid, Md. Maksudul Alam, Abdullah Mueen, and Md. Saidur Rahman, “HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction,” ISRN Bioinformatics, vol. 2013, Article ID 291741, 10 pages, 2013. doi:10.1155/2013/291741http://hdl.handle.net/10919/78994Haplotype 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 for an SNP matrix where and 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.application/pdfenCreative Commons Attribution 4.0 InternationalArticle - Refereed2017-09-18Copyright © 2013 Md. Shamsuzzoha Bayzid et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.https://doi.org/10.1155/2013/291741