An improved chemical reaction optimization algorithm for solving the shortest common supersequence problem. (October 2020)

• Record Type: Journal Article
• Authors: Luo, Fei; Chen, Cheng; Fuentes, Joel
• Is Part Of: Computational biology and chemistry. Volume 88(2020)
• Publication Date: 2020-10
• Subjects: Chemical reaction optimization -- Shortest common supersequence -- Heuristic algorithm -- NP-hard; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2020.107327
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: This paper presents a novel chemical reaction optimization (CRO) based algorithm dubbed IMCRO, to solve the shortest common supersequence (SCS) problem. IMCRO extends and improves the CRO_SCS framework with the introduction of inter-molecular ineffective collisions (Fig. 1(a)) and decomposition (Fig. 1(b)) in two of the four reactions of CRO. Highlights A novel CRO algorithm dubbed IMCRO, aimed for better performance and efficiency to solve the SCS problem is proposed. IMCRO extends and improves the CRO_CSC framework with the introduction of two new operators for decomposition and inter-molecular ineffective collisions in two of the four reactions of CRO. The typical SCS datasets are exploited in the experiments in comparison with heuristic algorithms. Abstract: The shortest common supersequence (SCS) problem is a classical NP-hard problem, which is normally solved by heuristic algorithms. One important heuristic that is inspired by the process of chemical reactions in nature is the chemical reaction optimization (CRO) and its algorithm known as CRO_SCS. In this paper we propose a novel CRO algorithm, dubbed IMCRO, to solve the SCS problem efficiently. Two new operators are introduced in two of the four reactions of the CRO: a new circular shift operator is added to the decomposition reaction, and a new two-step crossover operator is included in the inter-molecular ineffective collision reaction. Experimental results show that IMCRO achieves better performance on random and real sequences than well-known heuristic algorithms such as the ant colony optimization, deposition and reduction, enhanced beam search, and CRO_SCS. Additionally, it outperforms its baseline CRO_SCS for DNA instances, averaging a SCS length reduction of 1.02, with a maximum length reduction of up to 2.1.