An Adaptive Particle Swarm Optimization Algorithm for Solving DNA Fragment Assembly Problem
Uma Maheswari Sankareswaran.
This paper proposes an efficient method to solve the DNA fragment assembly
problem using Adaptive Particle Swarm Optimization (APSO). The DNA fragment assembly for
shotgun sequencing has been under study with great significance and complexity. It refers to the
arrangement of the fragments in an accurate sequence. This fragment assembly problem is an
NP-hard combinatorial optimization problem. In this paper, three different methods namely
Constant Inertia Weight (CIW), Dynamically Varying Inertia Weight (DVIW) and An Adaptive
Particle Swarm Optimization (APSO) with Smallest Position Value (SPV) rule are proposed to
solve the DNA fragment assembly problem. The objective of the proposed method is to obtain
the maximum overlapping score by assembling the fragments. Particle swarm optimization
algorithm is used to analyze the impact of inertia weight, the cognitive and social components.
The PSO algorithm was simulated for each of the methods individually. The experimental
results are obvious that the proposed APSO method yields better overlap score when tested with different sized
benchmark instances. The proposed APSO method is effective and efficient in assembling the fragments and getting the
maximum overlap score when compared to other heuristic techniques.
Keywords: Adaptive particle swarm optimization, bioinformatics, DNA fragment assembly, inertia weight, smallest position
Rights & PermissionsPrintExport