| Particle swarm optimization (PSO) is a stochastic method originally proposed by Kennedy and Eberhart as a simulation of social behavior, inspired in part by observing flocking birds and schooling fish. Its capability as an effective optimizer has proven useful in a diverse range of fields.;One of the most important problems in computational biology is multiple sequence alignment (MSA), the process of arranging primary sequences of DNA, RNA, or protein to identify regions of similarity. Finding an exact solution has proven to be computationally intractable thus far, and most current algorithms are based on heuristics and settle for providing a quasi-optimal alignment.;Stochastic optimization and swarm intelligence techniques have emerged as a prevailing option for improving the computational cost of MSA. Research in applying PSO to MSA has been active for nearly fifteen years. While the results have been positive, open research questions and opportunities for further improvement remain plentiful.;This thesis presents a promising new approach, incorporating successful techniques from previous research and contributing multiple novel features. In particular, this research presents a new objective function, the Universal Partitioning Search (UPS), and introduces a novel correspondence mapping approach, which calculates particle distance and velocity by adapting the wavelet-based morphing technique used in computer graphics animation and image processing. Particular attention to detail is given to the initialization process to ensure the swarm starts with particles of sufficient quality. |
