FINDING A LOWER BOUND FOR THE 2D  HP PROTEIN FOLDING PROBLEM USING ANT COLONY OPTIMIZATION

By

Dana Helmi Tawfiq Salameh

Supervisor

Dr. Sameh Al Shihabi

ABSTRACT

The prediction of the protein structure from its amino acid is called Protein Folding Problem(PFP). PFP triggered a wave of research devoted to  solve this Non-deterministic Polynomial–time hard (NP-hard) Combinatorial Optimization Problem (CO) in computational biology. PFP's importance lies in the deep relationship between the proteins' structures and their vital functions for human life.

Due to the complication  of  PFP,simplified models such as Dill's Hydrophobic-Polar (HP) model has become one of the major tools for  studying the protein structure in the Two-Dimensional(2D)space . Many optimization methods have been tried out to solve this fundamental problem such as Tabu search, Monte Carlo methods and Ant Colony Optimization (ACO).

This work presents a novel ants-based algorithm, Max-Min Ant System (MMAS), which is suggested by the foraging behavior of ants, to solve this 2D HP PFP. Each ant is able to construct a solution and look for the best one. But only a sole ant is allowed to update the pheromone which value is bounded between two imposed limits.

To construct solutions, ants are allowed to make two steps: one horizontal and the other is vertical, taking into account the distance between two consecutive hydrophobic amino acids in the sequence. In using this technique , small instances were solved and promising results are obtained; however, for larger instances that have two hydrophobic amino acids separated by more than two Polar amino acids, solution quality deteriorated which makes the method not comparable to the state-of-the-art ones. The reason for this deterioration is due to the fact that ants constructing solutions might need to take more than two possible moves, two of which might be in the same direction.

15.5.2013

 Master's degree in Industrial Engineering Department / Management

​University of Jordan- Engineering College

(2010 – 2013)  

3.89 out 4 "Excellent grade"