Bio-inspired heuristic for optimizing protein structure alignment using distributed modified extremal optimization

Proteins with similar three-dimensional structures usually have similar biological functions and interactions in living organisms. Thus, detecting similar structures in proteins is presently one of the most attractive research topics in computational biology. Many techniques for the comparison of protein structures are based on protein structure alignment. This is similar to sequence alignment, and is one of the most effective methods for extracting similar structures. The contact map overlap (CMO) maximization problem (hereafter, the CMO problem) is formulated as a combinatorial optimization to find the optimal structure alignment. The CMO problem is known to be NP-hard; hence, a number of researchers have been developing heuristic approaches. In this paper, we propose a novel bio-inspired heuristic algorithm using distributed modified extremal optimization (DMEO) for the CMO problem. DMEO is a hybrid of population-based modified extremal optimization (PMEO) and distributed genetic algorithms inspired by the island model. In the island model, a population is divided into two or more sub-populations (called islands), and each island evolves separately. Islands can maintain different types of individuals at the end of alternation of generations. Therefore, DMEO can maintain more diversity than PMEO. The experiments compared the DMEO-based heuristic with the PMEO-based heuristic, and the results show that DMEO performs well for 25 out of 32 protein pairs.