Chemical reaction optimization for solving longest common subsequence problem for multiple string

Longest common subsequence (LCS) is a well-known NP-hard optimization problem that finds out the longest subsequence of each member of a given set of strings. In computational biology, sequence alignment is a fundamental technique to measure the similarity of biological sequences, such as DNA and genome sequences. A high sequence similarity often applied to molecular structural as well as functional similarities and can be used to determine whether (and how) sequences are related. Finding the longest common subsequence (LCS) is one way to measure the similarity of sequences. It has also applications in data compression, FPGA circuit minimization, and bioinformatics, etc. Exact algorithms are impractical since they fail to solve this problem for multiple instances of long lengths in polynomial time. There are some approximations, heuristic, and metaheuristic methods proposed to solve the problem. Chemical reaction optimization (CRO) is a new metaheuristic method that mimics the nature of chemical reaction into optimization problems. In this paper, we have proposed chemical reaction optimization technique to solve the longest common subsequence problem for multiple instances. Here, we have redesigned four elementary operators of CRO for LCS problem. Operators of CRO algorithm are used to explore the search space both locally and globally. A novel correction method has been designed to correct the solution. Correction method works after each search operator to ensure the validity of the changes made by operators. Both solution quality and execution time are considered while designing the operators and the correction method. Thus proposed system brings robustness, efficiency, and effectiveness while solving MLCS problem. Our approach is compared with hyper-heuristic, ant colony optimization, beam ant colony optimization, and memory-bound anytime algorithms. The experimental results in lengths of the returned common sequences show that our proposed algorithm gives either same or better results than all other algorithms in less execution time.