HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction

Bayzid, Md. Shamsuzzoha; Alam, Md. Maksudul; Mueen, Abdullah; Rahman, Md. Saidur

HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction

dc.contributor.author	Bayzid, Md. Shamsuzzoha	en
dc.contributor.author	Alam, Md. Maksudul	en
dc.contributor.author	Mueen, Abdullah	en
dc.contributor.author	Rahman, Md. Saidur	en
dc.contributor.department	Computer Science	en
dc.date.accessioned	2017-09-18T09:47:42Z	en
dc.date.available	2017-09-18T09:47:42Z	en
dc.date.issued	2013-01-28	en
dc.date.updated	2017-09-18T09:47:42Z	en
dc.description.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 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.	en
dc.description.version	Published version	en
dc.format.mimetype	application/pdf	en
dc.identifier.citation	Md. 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/291741	en
dc.identifier.doi	https://doi.org/10.1155/2013/291741	en
dc.identifier.uri	http://hdl.handle.net/10919/78994	en
dc.language.iso	en	en
dc.publisher	Hindawi	en
dc.rights	Creative Commons Attribution 4.0 International	en
dc.rights.holder	Copyright © 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.	en
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	en
dc.title	HMEC: A Heuristic Algorithm for Individual Haplotyping with Minimum Error Correction	en
dc.title.serial	ISRN Bioinformatics	en
dc.type	Article - Refereed	en
dc.type.dcmitype	Text	en