A particle swarm optimization algorithm for haplotype reconstruction based on minimum fragment removal model
Academic Article
Overview
Identity
Additional Document Info
View All
Overview
abstract
The individual haplotype reconstruction problem was studied by using the minimum fragment removal (MFR) model. Owing to the NP-hardness of the MFR model, a practical algorithm based on particle swarm optimization (PSO) for haplotype reconstruction, named P-MFR, was presented. A kind of short particle code was designed for the P-MFR by taking advantage of the low heterozygous frequencies of single nucleotide polymorphisms (SNPs). The experiments were conducted by using the haplotypes on the chromosomes 1 of 60 individuals in the CEPH sample, which were released by the International HapMap Project. The results indicate that P-MFR can obtain higher reconstruction rate than previous algorithms when solving the MFR model. Moreover, this kind of short particle code makes P-MFR efficient even for reconstructing long haplotypes.