A practical algorithm based on particle swarm optimization for haplotype reconstruction

作者:

Highlights:

摘要

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.

论文关键词:Algorithm,Single nucleotide polymorphisms,Haplotype,The minimum error correction,Particle swarm optimization

论文评审过程:Received 1 April 2008, Revised 25 May 2008, Accepted 1 December 2008, Available online 24 December 2008.

论文官网地址:https://doi.org/10.1016/j.amc.2008.12.040