Particle swarm optimization for SNP haplotype reconstruction problem

摘要

The haplotype reconstruction based on aligned single nucleotide polymorphism (SNP) fragments is to conclude a pair of haplotypes from located polymorphism data. Known computational model of this problem is minimum error correction (MEC) that has been proved to be NP-complete by Lippert et al., but there are few practical algorithms for it. In this paper, we design a heuristic algorithm based on particle swarm optimization (PSO) which was proposed by Kennedy and Eberhart to solve the problem. Extensive computational experiments indicate that the designed PSO algorithm achieves a higher accuracy than the genetic algorithm (GA) designed by Ruisheng Wang to the MEC model in most cases.