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

završni rad

• Naslov (engleski): An Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem
• Autor: Tesa Jurišić
• Mentor: Josipa Pina Milišić (mentor)
• Član povjerenstva: Josipa Pina Milišić (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Anamari Nakić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2020-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: optimizacija kolonijom mrava; problem savijanja proteina; hidrofobno-polarni model savijanja proteina
• Ključne riječi (engleski): ant colony optimization; protein folding problem; hydrophobic-polar protein folding model
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:793880
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 15:13:30