Optimizing and integrating K-means and PSO algorithms for haplotype reconstruction using SNP maker information

Haplotype reconstruction is one of the main topics in genetic and bioinformatics studies. Construction haplotype directly through biological experiments is costly and cumbersome task. Therefore, haplotype reconstruction is generally done using algorithms and computational methods on genetic and genotype data. In this study, we present two algorithms, based upon minimal error correction model, to reconstruct haplotype from SNP and genotype data. The first algorithm is special case of K-Means algorithm that would select primary random centers with particular conditions. The second algorithm, is a combination of improved PSO and K-Means that we called up IPSOKM. The optimized algorithms were applied on real and simulated data. The results showed that haplotype reconstruction accuracy in comparing with general reconstruction haplotype algorithms, improved especially when there were gap and error. Overall, the presented algorithms could efficiently be used in human genetics as well as in plant and animal breeding studies.