matf logo

 Matematički fakultet Univerziteta u Beogradu

Seminar Katedre za računarstvo i informatiku


Letnji semestar akademske 2019/2020. godine


Petak, 11. septembar 2020. u 18h, Svetog Nikole

Aleksandar Janjić, Matematički fakultet, Univerzitet u Beogradu
Probabilistička algebra i fazi klasifikacija u fazi relacionim bazama podataka zasnovanim na relaciji blizine
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Fazi relacioni modeli baza podataka, zasnovani na dobro definisanoj teoriji fazi skupova i fazi logici, pružaju mogućnost za prevazilaženje ograničenja tradicionalnog relacionog modela. Takvi modeli pojavili su se 80. tih godina 20. vijeka a nova dostignuća i primjene posljednjih godina unijeli su novi talas u istraživanja fazi baza podataka.

Jedan od prvih pokušaja da se postavi čvrsta teorijska osnova za proširenje sadržaja relacionih baza podataka nepotpunim i nepreciznim informacijama bio je fazi relacioni model Buckles-a i Petry-ja iz 1982 godine. Ova struktura zasnivala se na dva uopštenja tradicionalnog relacionog modela:

  1. komponenta torke je u opštem slučaju bilo koji neprazni podskup odgovarajućeg domena, a ne samo jedan element (odstupanje od 1NF) i
  2. na svakom domenu definisana je relacija sličnosti (refleksivna, simetrična i max-min tranzitivna, koja svakom paru elemenata iz domena pridružuje realni broj iz intervala [0,1]) i koja, zajedno sa operacijom pripajanja (eng. merge operacijom) predstavlja uopštenje eliminacije duplikata zasnovane na relaciji jednakosti u tradicionalnom relacionom modelu.

Validnost ključnih svojstava ovog modela omogućila je činjenica da je relacija sličnosti – relacija ekvivalencije. Ipak, strogost svojstva max-min tranzitivnosti relacije sličnosti komplikuje konstrukciju ove relacije za neke tipove domena. Krajem osamdesetih godina prošlog vijeka Shenoi i Melton su uopštili ovaj model i pokazali kako njegova glavna karakteristika - postojanje klasa ekvivalencije nad domenima atributa - može biti sačuvana i relacijom koja zadovoljava samo svojstva refleksivnosti i simetričnosti (relacija blizine, eng. proximity relation). Ova relaksacija relacije sličnosti omogućuje prirodniji način izražavanja odnosa među podacima linearno uređenih domena. Istovremeno, tranzitivno zatvorenje relacije blizine omogućuje uspostavljanje relacija ekvivalencije. Važna karakteristika Shenoi-Melton modela jeste da su relacije ekvivalencije definisane na takozvanim vremenskim domenima i da zavise od trenutnog sadržaja baze podataka. Ova karakteristika, zajedno s načinom na koji je relacija ekvivalencije konstruisana relacijom blizine, obezbjeđuje da je blizina elemenata dovoljan ali ne i potreban uslov za njihovu pripadnost istoj klasi ekvivalencije.

Fazi klasifikacija ima primjene u širokom spektru oblasti kao što su medicinska dijagnostika, obrada slika, analiza i predviđanje ponašanja potrošača, klasifikovanje tekstova prema temi, stavu, osjećanju i sl. U tekstuelnom obliku nalazi se mnogo korisne informacije – od mejlova, veb stranica, društvenih mreža, novinskih članaka, izvještaja o istraživanju tržišta, preko CV-ja, pisama žalbi potrošača i internih izvještaja. Za fazi klasifikaciju koriste se fazifikovane metode tradicionalne klasifikacije – metode zasnovane na pravilima kao i statističke metode mašinskog učenja – bajesovske mreže, regresija, kNN, SVM, a posljednjih godina sve više neuronske mreže i dubinske neuronske mreže (deep neural networks).

Predmet ove disertacije biće analiza i rešavanje sljedećih problema:

  • Definisanje probabilističke relacione algebre nad fazi relacionom bazom u kojoj su vrijednosti atributa predstavljene posibilističkom raspodjelom (raspodjelom mogućih vrednosti)
  • Definisanje fazi klasa ekvivalencije zasnovanih na relaciji blizine na način koji obezbjeđuje da je blizina elemenata ne samo dovoljan već i potreban uslov za njihovu pripadnost, sa određenim stepenom, istim klasama ekvivalencije; izgradnja upitnog jezika za rad sa fazi klasama ekvivelncije
  • Primjena fazi klasifikacije na kolekcije digitalizovanih tekstova


Sreda. 24. jun 2020. u 18h, Studentski trg (Sala 718)

Jasmina Jovanović, Matematički fakultet, Univerzitet u Beogradu
Razvoj prediktora za klasifikovanje sekvenci
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Ponavljajuće (repetitivne) sekvence (niske) predstavljaju delove sekvenci (podsekvence) koji se javljaju dva ili više puta. U zavisnosti od toga da li je podsekvenca kopije identična originalnoj, ili zajedno sa originalnom čini palindrom, ponovci mogu biti direktni ili obrnuti. Takođe ponovci mogu biti podeljeni u komplementarne i nekomplementarne ponovke u zavisnosti od toga da li ispunjavaju funkciju preslikavanja svih karaktera u njihove komplementarne karaktere. Statistički značajni ponovci predstavljaju podskup ponovaka sekvence za koje nije očekivano da će se pojaviti u nasumičnoj sekvenci iste dužine.

Biološki makromolekuli polimerne prirode (DNK, RNK, proteini) se mogu posmatrati kao niske karaktera. DNK se može predstaviti kao niska karaktera nad azbukom A = {A, C, G, T}, dok se aminokiselinska niska može posmatrati kao niska karaktera nad 20-oslovnom azbukom sačinjenom od oznaka amino kiselina. Dužina nukleotidnih sekvenci varira od nekoliko nukleotida do više stotina miliona nukleotida, dok dužina aminokiselinksih sekvenci varira od nekoliko desetina do više hiljada aminokiselina. Analiza sličnosti nukleotidnih i proteinskih sekvenci je važna u određivanju funkcionalnih, strukturnih i evolucionih odnosa između različitih taksonomskih kategorija i/ili drugih karakteristika organizama. Njena značajnost se takođe ogleda u određivanju kategorija novootkrivenih sekvenci, poređenjem sa sekvencama koje imaju poznate funkcije. Ove analize su najčešće korišćene i primenjivane u bioinformatici. Postoje različiti algoritmi za poređenje sekvenci, koji se mogu podeliti na algoritme zasnovane na poravnanju (globalna i lokalna poravnanja) ili bez poravnanja sekvenci. Takođe se mogu klasifikovati na metode za poravnanje parova (dve sekvence) i za višestruko poravnanje (sa više od dve sekvence). Više algoritama koje koriste tehnike dinamičkog programiranja (kao što su Needleman-Wunsch i Smith-Waterman), kao i heuristički algoritmi (FASTA, BLAST i ClustalW) su uspešno razvijeni u cilju rešavanja problema poravnanja sekvenci i analize sličnosti, koji se mogu, pored nukleotidnih i proteinskih, primeniti i na druge sekvence (na primer u lingvistici za analizu prirodnih jezika).

Do sada razvijeni i korišćeni algoritmi nisu zasnovani na različitim tipovima statistički značajnih ponovaka varijabilnih dužina. Predmet ove disertacije biće analiza nukleotidnih i proteinskih sekvenci i njihovih ponovaka u cilju razvoja novih modela za identifikovanje sličnosti sekvenci na osnovu izabranih ponovaka. Klasifikacija (do sada neklasifikovanih) ulaznih sekvenci bi se vršila formiranjem njihovih profila na osnovu ponovaka i poređenjem sa bazom profila sekvenci koje imaju poznate karakteristike. U formiranju klasifikacionog modela za identifikaciju sličnosti sekvenci biće korišćene metode istraživanja podataka (klasifikacija, klasterovanje i analiza teksta) na osnovu kojih će se omogućiti provera preciznosti dobijenih rezultata.


Sreda. 24. jun 2020. u 19h, Studentski trg (Sala 718)

Ana Jelović, Matematički fakultet, Univerzitet u Beogradu
Primena ponovaka u predviđanju T-ćelijskih epitopa
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Centralna oblast primene informatičkih metoda u imunologiji je analiza kontinualnih kratkih niski AK koje nastaju biološkom degradacijom proteina samog organizma ili stranih proteina, a koje imuni sistem može da prepozna. Osnovni zadatak imunog sistema je da stalno vrši prepoznavanje: sopstveno – nesopstveno i opasno – neopasno, a proteini koji se prepoznaju se nazivaju antigeni (Ag). Najselektivnija karika ovog prepoznavanja je specifični imuni sistem koji može da se prilagođava (adaptira) i čija su ključna komponenta T limfociti (T ćelije), od kojih potiče naziv ćelijski imunitet. T ćelije se dele u dve osnovne grupe: T-pomoćne (Th, od eng. T-helper) ćelije, koje pomažu ostalim belim krvnim ćelijama u imunim procesima, i T-citotoksične limfocite (ćelije) (CTL), koje direktno mogu da unište nuklearne ćelije organizma inficirane virusima i tumorske ili transplantirane ćelije. Ćelijski imuni odgovor započinje tako što u antigen- prezentujućim ćelijama (APC, od eng. antigen presenting cells) dolazi do razgradnje (proteolize) proteina na fragmente (peptide) i njihovog vezivanja sa MHC molekulima koji transportuju ove peptide na površinu APC i predstavljaju ih, u vidu MHC-peptid kompleksa T ćelijskim receptorima (TCR) koji se nalaze na površini T ćelija (kako Th, tako i CTL).

Poznavanje oba osnovna tipa T ćelijskog imunog odgovora neophodno je za uspešnu imunizaciju i dobijanje vakcina protiv zaraznih bolesti, tumora ili suzbijanje alergija i autoimunih bolesti. Osnovna odrednica za vrstu T ćelijskog imunog odgovora (Th ili CTL) je sama niska peptidnog epitopa i njen odnos prema domaćinu (vrsti organizma u kojoj se odvija imuni proces). Način imunizacije, i stanje organizma u kome se odvija imuni proces, odlučuju o tome da li će doći do imunog procesa, tj. da li će se jedan epitop moći okarakterisati kao imunogen ili ne i koja vrsta imunog odgovora će pretežno biti izazvana.

Eksperimentalna istraživanja T ćelijskih epitopa u cilju dijagnostike i terapije zaraznih bolesti i tumora, spadaju u najdugotrajnija i najskuplja biološka i klinička ispitivanja. Računarske metode, zasnovane na afinitetu vezivanja kontinualnih niski peptida za MHC molekule, što je ključni događaj selekcije T ćelijskih epitopa su danas veoma brojne i značajane su za dizajniranje sintetičkih vakcina protiv različitih bolesti. Računarske i matematičke metode su u ovom području ključne kako bi omogućile sistematično istraživanje i identifikovanje T – ćelijskih epitopa na velikom skupu podataka. Poznato je, međutim, da ove metode u velikoj meri precenjuju ili greše i u broju i u vrsti predviđenih epitopa, delom zbog polimorfnosti MHC molekula (alela), za koje ne postoji dovoljan broj eksperimentalnih podataka koji se koriste u treniranju alata za predviđanje. Stoga se često uvode druge vrste analiza koje bi imale za cilj da definišu molekularnu strukturu interakcije između epitopa i MHC alela ili sposobnost epitopa da dovede do aktivacije imunog odgovora. Često se unutar proteinskih niski nalaze kraće podniske, nastale unutrašnjim dupliranjem gena, koje se ponavljaju dva ili više puta. Ovakve podniske su označene kao ponovci (ponavljajuće niske ili eng. "repeats"). U zavisnosti od pojavljivanja unutar nukleotidne ili proteinske niske oni mogu biti "tandem repeats" sa dva ili više susednih ponovaka ili "interspersed repeat" (nesusedni ponovci). Prema redosledu slova ponavljajuće niske, ponovci mogu biti direktni, ili inverzni (palindromi ili eng. "mirror sequencies"). Ustanovljavanje eventualne povezanosti ponovaka i epitopa može olakšati nalaženje epitopa u proteinskim niskama.


Petak, 12. 6. 2020. u 18h, u sali 153 u Svetog Nikole

Mirko Spasić, Katedra za računarstvo i informatiku, Matematički fakultet, Univerzitet u Beogradu
Modelovanje upitnih jezika sa primenama u refaktorisanju i opimizaciji koda
predlog prijave teme doktorske disertacije

Prikaži apstrakt

U današnje vreme okruženi smo enormnom količinom podataka iz različitih oblasti koji stižu do nas sve češće putem aplikacija. Aplikacije pristupaju kako tradicionalnim bazama podataka, tako i drugim skladištima. Na primer, ideja Semantičkog veba je da podaci budu dostupni na vebu, definisani i povezani na način koji oslikava njihovo značenje (tehnologije RDF i OWL), i tako omogućava da budu čitljivi i računarima, ali ne samo za njihovo prikazivanje, već i za automatiziciju, integraciju i ponovno korišćenje u različitim aplikacijama. Za pristup podacima pohranjenim u bazi koriste se upitni jezici, gde je SQL standardni jezik za pristup tradicionalnim bazama, a SPARQL standard u RDF svetu. Unapređivanje kvaliteta koda bez promene njegove funkcionalnosti, u smislu refaktorisanja ili optimizacije, spada u svakodnevnu programersku aktivnost. Generalno prihvaćena praksa u ovoj oblasti podrazumeva da takve promene budu propraćene proverom da li je očuvano željeno ponašanje programa. Ova provera najčešće se vrši testiranjem. Međutim, u takvom scenariju, to može trajati dugo i pritom, testiranje ne garantuje odsustvo razlika u ponašanju između dve verzije koda. S druge strane, korišćenje alata za automatsku verifikaciju ekvivalentnosti koda može da dâ garanciju zadržavanja ponašanja programa pri refaktorisanju ili optimizaciji i od suštinskog je značaja za efikasan i pouzdan razvoj softvera. U cilju razvoja alata za automatsku verifikaciju ekvivalentnosti koda u aplikacijama koje koriste upitne jezike, potrebno je precizno modelovati semantiku ovih programskih jezika. Predmet ove doktorske disertacije biće moವelovanje osnovnih konstrukata upitnih jezika u teorijama logike prvoī reda, zahvaljujući kojim će, upotrebom odgovarajućih rešavača, biti moguće donošenje korisnih zaključaka o upitima. U cilju refaktorisanja ili optimizacije, u skladu sa zadatom semantikom, biće podržano utvrđivanje ekvivalentnosti ili nekog drugog odnosa između dva upita.

Prvi deo disertacije biće posvećen problemu sadržanosti upita (eng. query containment problem) u jeziku SPARQL. Ovaj problem, ali za upite nad relacionim bazama, postavljen je još 1977. godine kao problem utvrđivanja da li su svi rezultati jednog upita sadržani u skupu rezultata drugog upita nad bilo kojom bazom podataka. Ovo je jedan od fundamentalnih problema u oblasti baza podataka i u opštem slučaju je neodlučiv. Za neke klase upita ovaj problem je NP-kompletan i predstavlja veliki izazov za istraživače. Opis problema prirodno se prenosi na jezik SPARQL, koji je relativno nov, ali već ima istraživača koji se bave ovim problemom baš u ovom jeziku. Kako se upitni jezici koriste i u kombinaciji sa nekim programskim jezikom opšte namene, rezonovanje o takvim programima postaje daleko komplikovanije, jer uključuje semantike i imperativnih i deklarativnih jezika. Primena modelovanja upitnih jezika biće moguća i u ovim scenarijima, i drugi deo disertacije baviće se upravo time, na primeru SQL jezika ugrađenog u jezik C/C++ (eng. embedded SQL). Ovakvim pristupom omogućuje se automatsko rezonovanje o funkcionalnoj ekvivalentnosti C/C++ programa koji sadrže ugrađene SQL upite za pristup podacima, u cilju jednostavnijeg refaktorisanja i optimizacije takve vrste koda.


Petak, 12. 6. 2020. u 19h, u sali 153 u Svetog Nikole

Mirjana Maljković, Katedra za računarstvo i informatiku, Matematički fakultet, Univerzitet u Beogradu
Predviđanje alfabeta lokalne strukture proteina primenom metoda istraživanja podataka
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Proteini su linearni biološki polimeri sastavljeni od aminokiselina čiji broj i redosled određuju strukturu i funkciju proteina. Struktura proteina je definisana sa tri nivoa: (1) primarnom strukturom koja je određena redosledom aminokiselina povezanih peptidnom vezom koji se naziva i aminokiselinska sekvenca, (2) sekundarnom strukturom koju čine konformacije aminokiselina u određenom regionu polipeptidnog lanca i (3) trodimenzionalnom strukturom (3D) definisanom koordinatama atoma aminokiselina, koja se naziva tercijarna struktura. Pošto je eksperimentalno određivanje trodimenzionalne strukture proteina skupo i vremenski zahtevno, javila se potreba za razvojem programa koji na osnovu aminokiselinske sekvence predviđaju osobine 3D strukture.

3D struktura glavnog lanca proteina (eng. backbone) može da se opiše korišćenjem prototipova lokalne strukture proteina. Prototipovi se koriste za aproksimaciju lokalnih savijanja koja se javljaju u strukturi poznatih proteina, a određuju se na osnovu izdvojenih fragmenata uzastopnih aminokiselina u polipeptidnim lancima čija je 3D struktura poznata. Skup definisanih prototipova lokalne strukture čini biblioteku lokalnih struktura proteina, koja se još naziva i strukturni alfabet (eng. structural alphabet), dalje u tekstu SA. U dosadašnjim istraživanjima je izdvojeno nekoliko SA koji se razlikuju po svojstvima korišćenim za opis glavnog lanca proteina, metodama korišćenim za njihovo definisanje i broju aminokiselina koje čine fragment. Svaki SA je definisan kao skup od N prototipova dužine l aminokiselina. Za SA je bitno da njegovi prototipovi omogućavaju preciznu rekonstrukciju strukture proteina.

Jedan od najpoznatijih strukturnih alfabeta se naziva Proteinski Blokovi (eng. Protein Blocks), dalje u tekstu PB. Strukturni alfabet PB se sastoji od 16 prototipova koji su napravljeni na osnovu fragmenata od 5 uzastopnih aminokiselina. Do sada je razvijeno nekoliko alata različite preciznosti za predviđanje prototipova PB na osnovu aminokiselinske sekvence primenom različitih metoda klasifikacije. SA Proteinski Blokovi ima značajnu primenu u strukturnoj bioinformatici. Mnoga patološka stanja su rezultat poremećene proteinske funkcije, stoga je za farmakologiju od velikog značaja određivanje strukture i funkcije proteina. Predviđanje lokalne strukture glavnog lanca proteina je bitan faktor u preciznom određivanju globalne strukture proteina.

Predmet ove disertacije biće analiza postojećih strukturnih alfabeta, pravljenje modela za predviđanje prototipova strukturnog alfabeta Proteinski Blokovi, kao i razvoj novog strukturnog alfabeta i pravljenje modela za predviđanje prototipova novog strukturnog alfabeta.


Seminar

Seminar Katedre za računarstvo i informatiku vodi poreklo od Seminara za računarstvo i informatiku, osnovanog daleke 1977. godine. Od osnivanja Katedre, 1987. godine, Seminar radi, sa povremenim kraćim prekidima, pod sadašnjim imenom. Seminar je osnovao i prvi rukovodio njime prof. Nedeljko Parezanović. Kasniji rukovodioci Seminara bili su prof. Vojislav Stojković, prof. Gordana Pavlović- Lažetić, prof. Nenad Mitić, prof. Duško Vitas, prof. Miodrag Živković. Na Seminaru se izlažu naučni razultati iz različitih oblasti računarstva, istraživača sa Matematičkog fakulteta kao i gostujućih istraživača iz zemlje i inostranstva.

Sastanci se (uz izuzetke) održavaju svakog drugog četvrtka od 18h u prostorijama Matematičkog fakulteta na Studentskom trgu.


Aktuelni rukovodilac seminara je prof. Filip Marić.