The Research Of Sequence Alignment Based On Hybrid Chemical Reaction Optimization Algorithm

Sequence alignment is a basic method for information processing in bioinformatics research.It is of great significance for sequence analysis,the prediction of the structure and function of sequence,and the construction of the evolutionary tree.Whether the pairwise sequence alignment or multiple sequence alignment,them can be seen as a mathematical optimization problem.With the rapid growth of data in biological molecular sequence data,it is more and more difficult to find overall optimal alignment.The researchers apply heuristic algorithm on this optimization problem to find the best approximation solution,such as genetic algorithm,ant colony algorithm.While chemical reaction optimization is a new method,which mimics the motion process of molecular in chemical reaction to search the optimal solution.CRO has successfully solved some classic optimization problem,so this article solves the sequence alignment with CRO,and provides a platform to solve the problem of multiple sequence alignment.The research which used chemical reaction optimization to solve sequences alignment is one beneficial attempt,and it provides a new tool of sequence alignment for sequence analysis.Firstly it introduces the concept and related knowledge of sequence alignment,and elaborates the existing classic pairwise sequence alignment algorithm and compares them in this paper.According to the mathematical model of pairwise sequence alignment,this paper proposes a new algorithm HCRO-PAS(Hybrid Chemical Reaction Optimization for Pairwise Sequence Alignment)based on the CRO algorithm framework.CRO is a mete-heuristic method by mimicking the energy change of the molecular motion in chemical reaction.And it seek the solution space by four basic operations:on-wall ineffective collision,decomposition,inter-molecular ineffective collision and synthetic.On-wall ineffective collision and inter-molecular ineffective collision can be searched for local optimal solution,and decomposition and synthesis are used to expand the search space to obtain the global optimal value as much as possible.Finally it found the molecular structure of the minimum potential energy in the system.Because CRO only keep the molecular structure of the current minimum PE in each iteration process,it make the search maybe easily fall into local optimal solution.This paper put forward a hybrid CRO solution for solve pairwise sequence alignment by introducing simulated annealing algorithm and adding Metropolis accepted standard to the process of group updating in the general CRO.HCRO-PAS algorithm designs the specific operation of CRO according the practical problem,and a model of parallel CRO has been designed to speed up the algorithm in this paper.In order to verify the feasibility of the above algorithms,this paper apply hybrid CRO algorithm on pairwise sequence alignment,and compare the results with the classic NW algorithm in the fitness value.It can be seen from the results the proposed method is effectiveness,and in a certain range of sequence length,the proposed algorithm can achieve very good alignment precision.