Chemical reaction optimization for pairwise sequence alignment

Pairwise sequence alignment is one of the fundamental problems in bioinformatics, which constitutes the basis of various other applications including phylogenetic tree estimation, secondary structure prediction, and critical residue identification. In this paper, we utilize Chemical Reaction Optimization (CRO), a general-purpose metaheuristic for global optimization, to solve the pairwise sequence alignment problem. We focus on the four elementary reactions of CRO, i.e., on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis, to meet with the requirements of pairwise alignment. Our proposed method, namely, PSA-CRO, is evaluated by traditional benchmarks and artificially generated sequences. The experimental results show that PSA-CRO is highly competitive and outperforms many other existing methods in terms of alignment accuracy and computational complexity. Copyright © 2015 American Scientific Publishers All rights reserved.