ACO Implementation for Sequence Alignment with Genetic Algorithms
This is an incremental improvement for bioinformatics researchers, applying an existing meta-heuristic to a known problem with limited practical gains.
The paper tackled sequence alignment by implementing Ant Colony Optimization (ACO) with a genetic algorithm to evolve parameters, finding that ACO can be applied but is computationally expensive compared to Needleman-Wunsch.
In this paper, we implement Ant Colony Optimization (ACO) for sequence alignment. ACO is a meta-heuristic recently developed for nearest neighbor approximations in large, NP-hard search spaces. Here we use a genetic algorithm approach to evolve the best parameters for an ACO designed to align two sequences. We then used the best parameters found to interpolate approximate optimal parameters for a given string length within a range. The basis of our comparison is the alignment given by the Needleman-Wunsch algorithm. We found that ACO can indeed be applied to sequence alignment. While it is computationally expensive compared to other equivalent algorithms, it is a promising algorithm that can be readily applied to a variety of other biological problems.