Title: A heuristic algorithm for haplotype reconstruction from aligned weighted SNP fragments

Authors: Jingli Wu; Jianxin Wang; Jian'er Chen

Addresses: School of Information Science and Engineering, Central South University, Changsha, 410083, China; Department of Computer Science, Guangxi Normal University, Guilin, 541004, China ' School of Information Science and Engineering, Central South University, Changsha, 410083, China ' School of Information Science and Engineering, Central South University, Changsha, 410083, China; Department of Computer Science, Texas A&M University, College Station, TX 77843, USA

Abstract: Haplotyping problem has been the subject of extensive research in recent years, and is one of the hottest areas of Computational Biology today. In this paper, we study the single individual Single Nucleotide Polymorphism (SNP) haplotype reconstruction problem. A heuristic algorithm is proposed for assembling a pair of haplotypes from a set of aligned weighted SNP fragments. Computational experiments indicate that the algorithm is a good solution for the Weighted Minimum Letter Flips (WMLF) model, and gets better performance than previous works.

Keywords: single nucleotide polymorphism; haplotype reconstruction; weighted SNP fragments; weighted minimum letter flips; heuristics; bioinformatics; haplotyping.

DOI: 10.1504/IJBRA.2013.050743

International Journal of Bioinformatics Research and Applications, 2013 Vol.9 No.1, pp.13 - 24

Published online: 06 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article