A practical algorithm based on particle swarm optimization for haplotype reconstruction Academic Article

abstract

• The minimum error correction (MEC) model is an important computational model for haplotype reconstruction problem. Owing to the NP-hardness of the MEC model, Qian et al. presented a particle swarm optimization (PSO) algorithm to solve the model, and the length of a particle code is equal to the number of SNP fragments. However, there are hundreds and thousands of SNP fragments in practical applications, the PSO algorithm based on this kind of long particle code cannot obtain high reconstruction rate efficiently. In this paper, a kind of short particle code is proposed by taking advantage of the low heterozygous frequencies of single nucleotide polymorphisms (SNPs), and a practical particle swarm optimization algorithm P-MEC based on this kind of particle code is presented. Experimental results indicate that P-MEC algorithm can get higher reconstruction rate than the particle swarm optimization algorithm designed by Qian et al. to the MEC model. Moreover, this kind of short particle code makes P-MEC algorithm efficient even for reconstructing long haplotypes. 2008 Elsevier Inc. All rights reserved.

authors

• Chen, Jianer

published proceedings

• APPLIED MATHEMATICS AND COMPUTATION

author list (cited authors)

• Wu, J., Wang, J., & Chen, J.

citation count

• 9

complete list of authors

• Wu, Jingli||Wang, Jianxin||Chen, Jian’er

publication date

• February 2009

publisher

• Elsevier  Publisher

published in

• Applied Mathematics and Computation  Journal

keywords

• Algorithm
• Haplotype
• Particle Swarm Optimization
• Single Nucleotide Polymorphisms
• The Minimum Error Correction

Digital Object Identifier (DOI)

• 10.1016/j.amc.2008.12.040

start page

• 363

end page

• 372

volume

• 208

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.amc.2008.12.040