A particle swarm optimization algorithm for haplotype reconstruction based on minimum fragment removal model Academic Article uri icon

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.

published proceedings

  • Gaojishu Tongxin/Chinese High Technology Letters

author list (cited authors)

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

complete list of authors

  • Wu, J||Chen, J||Wang, J

publication date

  • February 2009