Solving haplotype assembly problem by applying particle swarm optimization

We propose the development of a sophisticated Particle Swarm Optimization (PSO) basedmethodology for reconstructing Single Individual Haplotypes (SIH). Haplotypes, representing an arrayof genetic variances on individual chromosomes, encapsulate crucial insights pertinent to the correlationbetween genomic sequences and pathological conditions. The identification of haplotypes in diploidorganism is recognized as a computationally intensive task for which existing laboratory methods comewith a high cost and depend on specialized apparatus. The task at hand entails the assembly of numerousDNA sequence fragments, each fragment partially revealing the composite haplotype. The pivot of thisresearch is the efficient bi-partitioning of these fragments, minimizing inaccuracies as quantified by theMinimum Error Correction (MEC) metric. This problem is classified as NP-hard, a complexity levelthat has spurred numerous heuristic-based solution endeavors. Our proposed two-tiered methodharnesses the PSO algorithm, a technique inspired by the social behavior of organisms. The initial phaseinvolves the clustering of fragments utilizing a defined metric distance, effectively organizing themajority of the data. The ensuing phase capitalizes on PSO's rapid convergence properties to enhancethe preliminary bi-partitioning achievements. The method is applied to various benchmark datasets,PSO showed significant promise. Through meticulous experimentation and analysis, it has beenempirically ascertained that the PSO-based framework facilitates reliable SIH reconstruction,corroborating the algorithm's potential effectiveness in addressing this complex issue.

کلیدواژه ها:

Haplotype reconstruction ، Particle swarm optimization ، Minimum Error Correction ، Graph Partitioning