A genetic algorithm with oscillating simulated annealing for 2D HP model

Abstract

Protein katlanması lineer bir amino asit zincirinin 3 boyutlu işlevsel öz haline katlanması sürecidir. Proteinin 3 boyutlu öz yapısını yalnızca amino asit serisini kullanarak bulmak şu anda hesaplamalı biyoloji dalındaki en zor problemlerden biri olmakla birlikte çok yoğun şekilde araştırılmaya devam edilmektedir. 2 boyutlu HP modeli protein katlanması problemi için basitleştirilmiş bir modeldir. Bu modelde indirgemeler, protein katlanması sürecindeki baskın gücün hidrofobisite olduğu varsayımı üzerine yapılmaktadır.Bu tezde, protein katlanması problemini 2 boyutlu HP modelinde çözmek için Genetik Algortima ve Benzetilmiş Tavlama algoritmalarının birleşiminden oluşan üstsezgisel bir metod sunuyoruz. Yöntemimiz literatürde tanımlanmış yerel arama metodlarından bazı bölümler kullanmaktadır. Tabu Arama' da kullanılan hafıza bölümü, yeni bir 1-nokta çaprazlama işlemcisi ve probleme özel bir diversifikasyon bölümü algoritmamızda bulunan parçaları oluşturmaktadır. Algoritmamıza ek olarak, HP modelin içerdiği bazı bilgiler ve bu bilgilerin bir algoritmada nasıl kullanılabileceğine dair bazı tartışmalar da tezin son kısmında sunulmaktadır.

Protein folding is the process of a linear chain of amino acids folding into a functional 3D native structure. The problem of predicting this 3D native structure given only the amino acids of a protein is one of the most challenging problems in computational biology and is still rigorously investigated. The Hydrophobic-Polar model is a simplified model for the protein folding process. This model is based on the assumption that hydrophobicity is the dominant force that drives the protein folding process.In this thesis we propose a meta-heuristic algorithm (GAOSA) that combines the well known Genetic Algorithm approach with Oscillating Simulated Annealing to address the protein folding problem in the simplified 2D Hydrophobic-Polar Model. Our approach makes use of the pull move neighborhood for the mutation operator, a brute force 1-point crossover operator, a memory component borrowed from Tabu Search and a problem specific diversification phase. We also provide some insights about the implications of the Hydrophobic-Polar Model and how these implications can be utilized in an algorithm.