A practical algorithm based on particle swarm optimization for haplotype reconstruction

摘要

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.