Točnost pretraživanja, clustering i klasifikacija

diplomski rad

• Naslov (engleski): Search accuracy, clustering and classification
• Autor: Ivan Kapec
• Mentor: Pavle Goldstein (mentor)
• Član povjerenstva: Pavle Goldstein (predsjednik povjerenstva)
• Član povjerenstva: Rudi Mrazović (član povjerenstva)
• Član povjerenstva: Goran Muić (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2021-03-04, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu promatrao se problem traženja proteina iz iste proteinske familije i uspješnost primjene algoritama iz teorije grafova na taj problem. Konkretno, analizirala se isplativost korištenja algoritma za traženje najveće aproksimativne klike koji djeluje kao nadopuna iterativnom pretraživanju u klasifikaciji proteina. Rezultati korištenja navedenog aproksimativnog pristupa usporedeni su sa rezultatima algoritma za traženje egzaktne najveće klike i posebno, sa rezultatima početnog iterativnog pretraživanja proteoma. Jedna od glavnih mjera koja je korištena za usporedbu uspješnosti modela je F1-score, a negdje je u obzir uzeta i vremenska složenost. Postupak je proveden na proteomima talijinog uročnjaka, krumpira, šećerne repe i rajčice. Promatrao se učinak algoritama na manjim i na većim skupovima podataka. Dobiveni rezultati pokazuju da korištenje aproksimativnog algoritma bitno poboljšava uspješnost modela (F1-score), iako nalazi manji broj stvarno pozitivnih (TP) u odnosu na početno iterativno pretraživanje. Takoder, egzaktni algoritam očekivano postiže nešto bolje rezultate od aproksimativnog, ali je na većem broju podataka puno sporiji u izvršavanju.

Sažetak (engleski)

This paper covers the problem of identifying proteins belonging to the same protein family and explores the use of applying known graph theory algorithms to this problem. Specifically, it examines the benefits of maximum clique approximation, which serves as a supplement to iterative searching in protein classification. Results of using the aforementioned approximation approach were compared with the results of using the exact maximum clique algorithm, as well as with the results of the initial proteome iterative search. F1- score was the primary metric used for comparing model performance, while in some cases time complexity was also considered. The procedure was performed on several proteomes, namely thale cress, potato, tomato and sugar beet. Algorithmic effciency was measured on both small and large data sets. Results obtained demonstrate that the use of the approximation algorithm greatly improves model performance (F1-score), although it does retrieve a smaller number of true positives (TP) compared with the initial iterative search. Furthermore, the exact algorithm achieves somewhat better results than the approximation algorithm, but it is considerably slower on large data sets.

• Ključne riječi: teorija grafova; klasifikacija proteina; proteom; F1-score
• Ključne riječi (engleski): graph theory algorithms; protein classification; proteome; F1- score
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:350573
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-03-24 13:38:19