Twin Removal in Genetic Algorithms for Protein Structure Prediction Using Low-Resolution Model

This paper presents the impact of twins and the measures for their removal from the population of genetic algorithm (GA) when applied to effective conformational searching. It is conclusively shown that a twin removal strategy for a GA provides considerably enhanced performance when investigating solutions to complex ab initio protein structure prediction (PSP) problems in low-resolution model. Without twin removal, GA crossover and mutation operations can become ineffectual as generations lose their ability to produce significant differences, which can lead to the solution stalling. The paper relaxes the definition of chromosomal twins in the removal strategy to not only encompass identical, but also highly correlated chromosomes within the GA population, with empirical results consistently exhibiting significant improvements solving PSP problems.

1 Introduction

The ab initio protein structure prediction (PSP) problem [1] essentially involves investigating the folding relationship of a linear chain of amino acids into a three-dimensional (3D) structure based on the properties and appearance pattern of amino acids. The folding relationship can be extremely complex [2], [3], [4], [5], [6], [7], [8], [9], [10], and to unravel this convoluted relation, lattice models such as the hydrophobic-hydrophilic (HP) model [11] have been widely applied. In the HP model, the copolymer chains of H (hydrophobic) and P (polar or hydrophilic) monomers are configured as self-avoiding-walks (SAW) favoring H-H interaction in a 2D square or a 3D cube lattice or a face-centered-cube (FCC) arrangement [12]. These simple or low-resolution models allow the development, testing, and comparison of various search algorithms that we have studied in this paper. The low-resolution model is applied within a hierarchical approach [13], [14], [15], [16], [17] to locate potential (backbone) conformation of the folded protein quickly and reliably [18] within the complex and convoluted search landscape before being explored further by a more realistic model. The approach is especially suitable for the computationally expensive ab initio prediction. The rationale behind the low-resolution model [3], [11], [19], [20], [21], [22], [23], [24], [25] and its current applications are widely available elsewhere [16], [26], [27], [28], [29], [30], [31].