A highly accurate heuristic algorithm for the haplotype assembly problem

BMC Genomics

Research

Lusheng Wang¹  Fei Deng¹  Wenjuan Cui¹ 

[1] Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong;

关键词: Initial Solution;    Benchmark Dataset;    Dynamic Programming Algorithm;    Maximum Coverage;    Vote Procedure;   

DOI  :  10.1186/1471-2164-14-S2-S2

来源: Springer

【 摘 要 】

BackgroundSingle nucleotide polymorphisms (SNPs) are the most common form of genetic variation in human DNA. The sequence of SNPs in each of the two copies of a given chromosome in a diploid organism is referred to as a haplotype. Haplotype information has many applications such as gene disease diagnoses, drug design, etc. The haplotype assembly problem is defined as follows: Given a set of fragments sequenced from the two copies of a chromosome of a single individual, and their locations in the chromosome, which can be pre-determined by aligning the fragments to a reference DNA sequence, the goal here is to reconstruct two haplotypes (h1, h2) from the input fragments. Existing algorithms do not work well when the error rate of fragments is high. Here we design an algorithm that can give accurate solutions, even if the error rate of fragments is high.ResultsWe first give a dynamic programming algorithm that can give exact solutions to the haplotype assembly problem. The time complexity of the algorithm is O(n × 2t × t), where n is the number of SNPs, and t is the maximum coverage of a SNP site. The algorithm is slow when t is large. To solve the problem when t is large, we further propose a heuristic algorithm on the basis of the dynamic programming algorithm. Experiments show that our heuristic algorithm can give very accurate solutions.ConclusionsWe have tested our algorithm on a set of benchmark datasets. Experiments show that our algorithm can give very accurate solutions. It outperforms most of the existing programs when the error rate of the input fragments is high.

【 授权许可】

Unknown   
© Deng et al.; licensee BioMed Central Ltd. 2013. This article is published under license to BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.