Self Generating Metaheuristics in Bioinformatics: The Proteins Structure Comparison Case

Abstract

In this paper we describe the application of a so called “Self-Generating” Memetic Algorithm to the Maximum Contact Map Overlap problem (MAX-CMO). The maximum overlap of contact maps is emerging as a leading modeling technique to obtain structural alignment among pairs of protein structures. Identifying structural alignments (and hence similarity among proteins) is essential to the correct assessment of the relation between proteins structure and function. A robust methodology for structural comparison could have impact on the process of rational drug design.

The Self-Generating Memetic Algorithm we present in this work evolves concurrently both the solutions (i.e. proteins alignments) and the local search move operators that it needs to solve the problem instance at hand. The concurrent generation of local search strategies and solutions allows the Memetic Algorithm to produce better results than those given by a Genetic Algorithm and a Memetic Algorithm with human-designed local searchers. The approach has been tried in four different data sets (1 data set composed of randomly generated proteins and the other 3 data sets with real world proteins) with encouraging results.