Academic year 2024/25

Proteini su linearni polimeri izgrađeni od aminokiselina, čiji redosled definiše njihovu prostornu strukturu i biološku funkciju. Iako mnogi proteini usvajaju stabilnu trodimenzionalnu konformaciju, značajan broj proteina ili njihovih delova ostaje delimično ili potpuno neuređen, bez fiksne 3D strukture. Neuređeni delovi proteina predstavljaju izazov za savremene metode predviđanja strukture, ali su istovremeno ključni za razumevanje regulatornih i interaktivnih funkcija u ćelijskim procesima. Trenutni modeli, uključujući različite vrste strukturnih alfabeta kao i AlphaFold program, imaju ograničenu preciznost u ovim regionima, što otvara prostor za dalja istraživanja.

Predlog teme doktorske teze obuhvata istraživanje neuređenih regiona u proteinima i njihovog neposrednog okruženja, kao i razvoj metoda za njihovu precizniju prostornu karakterizaciju. Imajući u vidu da neuređeni proteini (IDP) i njihovi regioni predstavljaju važan biološki fenomen sa značajnom ulogom u regulaciji, signalizaciji i patogenezi, ali da su slabo obuhvaćeni klasičnim modelima u kojima se predviđa struktura, istraživanje će biti usmereno na poboljšanje njihovog strukturnog opisa korišćenjem računarskih metoda.

Biće razvijen model koji kombinuje, za proteine iz DisProt baze, informacije dobijene iz strukturnog alfabeta Protein Blocks, predviđene 3D strukture iz AlphaFold programa, kao i dodatne osobine poput prisustva strukturnih ponovaka i fluktuirajućih granica između uređenih i neuređenih delova. Model će biti treniran i testiran na skupu proteina iz DisProt baze, koji sadrži eksperimentalno utvrđene neuređene regione. Na osnovu formiranog modela biće razvijen i meta-prediktor za određivanje neuređenih regiona proteina. Istraživanje će uključiti primenu različitih metoda istraživanja podataka u cilju pronalaženja karakterističnih obrazaca i prelaznih zona između strukturno različitih regiona proteina.

Očekivani rezultati obuhvataju poboljšanje pouzdanosti predviđanja neuređenih delova proteina i bolju definiciju njihovog trodimenzionalnog konteksta. Pored toga, očekuje se identifikacija strukturnih obrazaca koji mogu poslužiti za funkcionalnu karakterizaciju ovih regiona. Razvijen model i rezultati biće provereni upoređivanjem sa postojećim programima za predviđanje neuređenih regiona.

Доминацијски проблеми на графовима припадају класи НП тешких проблема и интензивно су проучавани, како теоријски, тако и практично, пре свега због њихове широке примене у областима као што су друштвене мреже, биоинформатика, рутирање у мрежама и истраживање података на графовима. Предлог теме докторске тезе обухвата развој метода за ефикасно решавање различитих варијанти доминацијских проблема, са посебном пажњом усмереном на графове великих димензија. Биће решавани следећи проблеми: проблем минималне тежинске тоталне доминације (MWTDS), минималне тежинске независне доминације (MWIDS), к јаке римске доминације (KSRDS), као и основни проблем минималне доминације (MDS). За проблем MWTDS биће развијена метода променљивих околина (VNS) уз инкрементално рачунање функције прилагођености. Биће предложена примена на убрзавање ширења информација на друштвеним мрежама. Код MWIDS проблема је планиран развој два ILP модела и похлепног алгоритма. Проблем KSRDS ће бити решаван применом VNS-а уз статистички приступ провере квазидопустивости на великим инстанцама. Биће предложена примена проблема у оптимизацији распореда ватрогасних ресурса. Код MDS проблема биће развијени хибридни алгоритми засновани на комбинацији различитих приступа међу којима су: проналажење заједница у графовима, ILP модели, пристрасна локална претрага, уз могућност унапређења коришћењем метода машинског учења. Очекивани резултати обухватају побољшање најбољих познатих резултата на разматраним проблемима, поготово на инстанцама великих димензија, као и предлог оригиналних примена. Сви алгоритми ће бити темељно упоређени са резултатима из литературе на постојећим (енг. benchmark) и новоуведеним скуповима инстанци, уз одговарајућу статистичку анализу.

Optimizacije vođene profilima (eng. profiile-guided optimizations) značajno doprinose generisanju efikasnih programa. Profili programa su informacije o izvršavanju programa, na primer broj izvršavanja grana u naredbama grananja, broj poziva funkcija, verovatnoće poziva virtuelnih metoda i slično. Dinamičko profajliranje je standardni način za prikupljanje profila, pokretanjem programa i praćenjem načina na koji se on izvršava. Dinamičkim profjaliranjem prikupljaju se precizni profili, ali je dinamičko prikupljanje profila često vremenski i memorijski zahtevno, kompikuje proces generisanja optimizovanih programa i zahteva odgovarajuće reprezentativne ulaze koje je često veoma izazovno pronaći. Alternativa dinamičkim profajlerima jesu statički profajleri. Statički profajleri predviđaju profile izvršavanja programa bez pokretanja programa, na osnovu statičkih atributa kojima se opisuju delovi progama.

Predlog teme doktorske teze obuhvata razvoj stačkog profjalera GraalSP zasnovanog na tehnikama mašinskog učenja. GraalSP koristi grafovsku međureprezentaciju visokog nivoa za definisanje atributa kojima se karakterišu delovi programa. Uz to, GraalSP polu-automatizuje proces definisanja ovih atributa. GraalSP podržava sve programske jezike koji se kompajliraju na Java bajtkod, na primer jezike Java, Scala i Kotlin. Za predviđanje profila, eksperimentisano je sa različitim modleima mašinskog učenja i najbolji rezultati su dobijeni korišćenjem XGBoost modela koji je zasnovan na stablima odlučivanja koji je stoga i integrisan u GraalSP. Pored toga, GraalSP koristi i dodatne heuristike za korekciju predviđenih profila kako bi korigovao neprecizna predviđanja modela koja mogu biti rezultat odudarajućih podataka (eng. outliers) i voditi do degradacije performansi. GraalSP je implementiran i integrisan u kompajler GraalVM Native Image, čime je ostvareno ubrzavanje vremena izvršavanja programa koji se prevode korišćenjem ovog kompajlera za 7.46% u poređenju sa podrazumevanom konfiguracijom kompajlera.