A scatter search approach for protein folding problem in 2-d HP-model

Abstract

Proteinler hücre aktivitelerinden sorumlu karmaşık moleküllerdir. Her bir proteinbir amino asit zincirinden meydana gelir. Bu amino asit zincirleri doğada doğalşekillerinde katlanmış halde bulunurlar. Bir proteinin aktivitesi büyük oranda doğalüç boyutlu yapısı tarafından belirlenir. Bir proteinin en az serbest enerji yapısının bulunmasına protein katlanma problemi denir. Öte yandan, bir proteinin doğal şeklininbelirlenmesi kolay değildir. Özellikle, protein katlanma probleminin NP-zor olduğukanıtlanmıştır.Tıbbi ve genetik çalışmalar bu doğal yapıların bilinmesine dayandığından dolayıprotein moleküllerinin doğal şekillerinin bulunması önemlidir. Bu nedenle, bu konuüzerine bir çok çalışma ve yatırım yapılmıştır. Bilgisayar bilimi, yöneylem araştırması,bioinformatik, genetik ve tıbbi bilimler gibi birçok daldaki araştırmacılar bu probleminçüzülmesi ile ilgilidir. Hatta, farklı alanlar arasında yöntemlerin, bilginin ve deneyiminbirleştirilmesi için işbirligi yapılmaktadır. Bu alanlar arası uygulamalardan biride sezgisel üstü yöntemlerin HP-modelindeki en az serbest enerji yapısı için kafesmodelinde protein katlanma problemine uygulanmasıdır.Bizim çalışmamız HP-modelini kullanan 2 boyutlu protein katlanma problemiiçin dağınık arama ve path relinking üzerine dayalı sezgisel üstü bir algoritmanıngeliştirilmesidir. Literatürde, protein katlanma problemine sezgisel üstü yöntemlerinve dağınık aramanın çok bilinen uygulamaları bulunmaktadır. Biz HP-modelini kullanan2 boyutlu protein katlanma problemine dağınık aramanın elemanları için yeniadımlar ve işlemler tanımladık. Ayrıca, dağınık aramanın elemanları ve çözümlerindeğerlendirmeleri için yeni ölçümler gibi birçok uygulama seçeneği önerdik. Bu çalışmadaverimli bir arama algoritması için bu elemanların farklı eşleşmelerini tanımladık ve testedip, test sonuçlarını bildirdik. Bu sonuçlar literatürdeki sonuçlar kadar iyi olmasada, dağınık arama ve path relinking üzerine dayalı sezgisel üstü algoritma elemanlarının geniş bir k ümesini test ettik. Bu sayısal deneylerin ile gelecek araştırmalariçin yararlı olacak sonuçlar elde ettik.

Proteins are complex molecules performing vital cellular activities. Each protein iscomposed of an amino acid chain. These amino acid chains are found as folded in theirnative state in the nature. The activity of a protein is mostly dened by its native3 dimensional (3D) conformation. Determination of the native 3D conformation ofan amino acid chain is called the protein folding problem (PFP). On the other hand,determination of the native state of a protein is not easy. In particular, protein foldingproblem is proven to be NP-hard.Determination of native states of protein molecules is vital since most of the medicaland genetic studies depend on knowing these native conformations. Thereforemany studies and investments are made on this topic. Researchers in various eldssuch as biochemistry, biophysics, computer science, operations research, bioinformatics,genetics and medical sciences are interested in solving this problem. Even, thereare sometimes collaborations between dierent research areas to merge their techniques,knowledge and experience on this problem. One of these applications is theapplication of metaheuristics to protein folding problem in minimum free energy con-formation with HP-model based on a lattice structure, as a cooperation of all thesesciences.This study is on developing a metaheuristic algorithm based on scatter search andpath relinking for the 2D lattice based PFP utilizing HP-model according to minimumenergy conformation theory. There are applications of well-known metaheuristics aswell as scatter search to the PFP in the literature. We have introduced new movesand operators for the elements of scatter search for the PFP on 2D lattice HP-model.We have also proposed several application options for these element of the scattersearch application, as well as new measurements for the values of the solutions. Weintroduced and experimented on some combinations of these elements for an eectivesearch algorithm and give the test results in this study. Although the results arenot as good as the results in the literature, we have tested a wide set of heuristicelements based on scatter search and path relinking. The results of these experimentsare promising for further improvement on this topic.