Protein Structure Prediction Using Parallel Linkage Investigating Genetic Algorithms

The tertiary structure determines the protein’s functionality. Genetic algorithms (GAs) are stochastic search routines that are capable of providing solutions to intractable problems. The use of GAs plays an important part in the search for near optimal solutions in large search spaces. The PSP solution landscape is so large and complex that deterministic methods flounder due to the combinatoric issues involved with enumerating these massive search spaces. This makes the GA an ideal candidate for finding solutions to the PSP problem. This is an engineering investigation into the effectiveness and efficiency of the Linkage Learning GA (LLGA) applied to the PSP problem. The LLGA implementations takes explicit advantage of “tight linkages” early enough in its algorithmic processing to overcome the disruptive effects of crossover. The LLGA is integrated with the previously developed and tested AFIT CHARMm energy model software. Furthermore, a parallel version, pLLGA, is developed using a data partitioning scheme to “farm out” the CHARMm evaluations. Portability across AFIT’s heterogeneous ABC Beowulf system, distributed networks, and massively parallel platforms is accomplished through the use of object-oriented C++ and the Message Passing Interface (MPI). This model improves the efficiency of the LLGA algorithm. Ramachandran developed constraints are incorporated into the LLGA to exploit domain knowledge in order to improve the effectiveness of the search technique. This approach, constrained-LLGA (cLLGA), has been parallelized using the same decomposition as the pLLGA. This new implementation is called the constrained-parallel LLGA (cpLLGA).