Ant Colony Optimization Applied for Multiple Sequence Alignment


  • Simeon Tsvetanov*
  • Desislava Ivanova
  • Boris Zografov



The paper presents Multiple Sequence Alignment (MSA) as a computation problem and proposes Ant Colony Optimization (ACO) based solution. В  The MSA is widely applied in the area of bioinformatics and has high compute complexity, which is hard for solving, especially for huge data sets. В  Ant Colony Optimization (ACO) is metaheuristic method applied for solving different kind of combinatorial problems. The main idea of the developed program implementation for solving MSA as follow: The ant takes a sequence and moves in the area associated with each sequence, increasing the pheromone level when finds similarity in the position. В  Dynamic program analysis using Scalasca tool has been performed to define the bottlenecks in the code and the problematic areas has been optimized for parallel computation. В  The experimental results shows that the developed program could be successfully used for solving MSA problem. The parallelization achieves almost linear speedup and also contributes for increasing the quality of the solutions.

Author Biographies

Simeon Tsvetanov*

Desislava Ivanova

Boris Zografov






Conference Contributions