Algoritam optimizacije kolonijom mrava za problem dvodimenzionalnog hidrofobno-polarnog savijanja proteina

undergraduate thesis

• Title (english): An Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem
• Author: Tesa Jurišić
• Mentor: Josipa Pina Milišić (mentor)
• Committee member: Josipa Pina Milišić (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Anamari Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-07-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Bjelančevine ili proteini su kemijske tvari koje upravljaju svim životnim procesima stanice. Izgrađene su od dvadeset različitih aminokiselina, međusobno povezanih poput karika u lancu. Redoslijed i broj tih karika određuje specifične osobine svake bjelančevine. Mogućnost pouzdanog i efikasnog predviđanja proteinske strukture iz informacija o aminokiselinskoj sekvenci predstavlja vrlo izazovan problem u području bioinformatike, a njegovo efikasno rješavanje znatno bi pojednostavilo tumačenje podataka prikupljenih projektom humanog genoma. Poznato je da se navedeni problem može formulirati u obliku NP-teškog problema kombinatorne optimizacije te ga je stoga zgodno rješavati primjenom odabranih heurističkih
metoda. U ovom završnom radu fokusiramo se na problem dvodimenzionalnog hidrofobno-polarnog (2D HP) savijanja proteina čije rješenje ćemo tražiti pomoću algoritma optimizacije kolonijom mrava, skraćeno ACO (eng. Ant Colony Optimization). ACO je iterativni proces u kojem populacija jednostavnih agenata ("mrava"), na temelju zajedničke memorije koja sadrži iskustvo iz prethodnih iteracija, opetovano konstruira moguća rješenja. Rezultate dobivene primjenom ACO algoritma usporedit ćemo s benchmark testovima koji su dostupni u suvremenoj znanstvenoj literaturi. Konačno, diskutirat ćemo utjecaj različitih parametara modela na efikasnost izvođenja odabranog algoritma.

Abstract (english)

Proteins are organic compounds that govern all the life processes of a cell. They are made up of twenty different amino-acids, interconnected like links in a chain. The order and number of these links determines the specific characteristics of each protein. The ability to reliably and efficiently predict protein structure from amino-acid sequence information is a very challenging problem in the field of bioinformatics, and its efficient resolution would greatly simplify the interpretation of human genome project data. It is well known that the mentioned problem can be formulated in the form of NP-hard combinatorial optimization problem, and therefore it is convenient to solve it using selected heuristic methods. In this bachelor thesis, we focus on the problem of two-dimensional hydrophobic-polar (2D HP) protein folding, the solution of which we will look for using the Ant Colony Optimization (ACO) algorithm. ACO is an iterative process in which a population of simple agents ("ants"), based on shared memory that contains experience from previous iterations, repeatedly constructs possible solutions. The solutions obtained by applying the ACO algorithm to the 2D HP protein folding problem will be compared with the benchmark tests available in the modern scientific literature. Finally, we will discuss the impact of different model parameters on the performance of the selected algorithm.

• Keywords: optimizacija kolonijom mrava; problem savijanja proteina; hidrofobno-polarni model savijanja proteina
• Keywords (english): ant colony optimization; protein folding problem; hydrophobic-polar protein folding model
• Language: croatian
• URN:NBN: urn:nbn:hr:168:793880
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 15:13:30