Točnost pretraživanja, clustering i klasifikacija

master's thesis

• Title (english): Search accuracy, clustering and classification
• Author: Ivan Kapec
• Mentor: Pavle Goldstein (mentor)
• Committee member: Pavle Goldstein (predsjednik povjerenstva)
• Committee member: Rudi Mrazović (član povjerenstva)
• Committee member: Goran Muić (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-03-04, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: teorija grafova; klasifikacija proteina; proteom; F1-score
• Keywords (english): graph theory algorithms; protein classification; proteome; F1- score
• Language: croatian
• URN:NBN: urn:nbn:hr:217:350573
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-03-24 13:38:19