Akademska 2019/20. godina

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.

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.

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.

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.

Fokus disertacije usmeren je na zadatak klasifikacije teksta, koji pripada jednom od zadataka oblasti obrade prirodnih jezika. U predavanju će biti prikazana četiri klasifikaciona problema u kontekstu obrade prirodnih jezika: problem validacije bilingvalnih parova višečlanih leksema, problem određivanja dobrih primera upotrebe rečeničnih odrednica, problem identifikacije autora kratkih tekstova, kao i problem analize osećanja u kratkim porukama.

Klasifikacija bilingvalnih parova leksema Primeri višečlanih leksemskih jedinica su: „predikatska logika“, „digitalne biblioteke“, „skup za obučavanje“, itd. Disertacija će se baviti problemom validacije prevoda bilingvalnih parova, tako da su klase dobar prevod i loš prevod. Na primer, neka je ulazni skup D1 = {((predikatska logika, mathematics), loš),((digitalne biblioteke, digital libraries), dobar), . . . ,((skup za obučavanje, training set), dobar)}. Atributi koji mogu biti korisni pokazatelji da je u pitanju dobar prevod su: vrste reči u obe lekseme („predikatska logika“ sadrži pridev i imenicu, dok je mathematics samo imenica), postojanje zajedničke podniske određene dužine (kod para „digitalne biblioteke“ i digital libraries to je podniska „digital“), broj reči u obe lekseme, itd.

Klasifikacija dobrih primera upotrebe rečničkih odrednica U svakom rečniku, elektronskom ili papirnom, korisno je da uz rečničku odrednicu stoji i primer kako se ona koristi u jeziku. U ovom slučaju klasifikacije, zadatak je svakom primeru dati ocenu podobnosti, odnosno automatski zaključiti da li je primer dobar ili loš. Na primer, za odrednicu „računar“, dobri primeri upotrebe su rečenice „Celodnevno sedenje uz računar može izazvati krivljenje kičme“ ili „Fon Nojman je autor arhitekture modernog računara“, ali ne i „Lenovo računar.“ jer nije dovoljno informativno. Atributi koji mogu biti korisni pokazatelji koliko dobro tekst ilustruje upotrebu rečničke odrednice su: pozicija rečničke odrednice u primeru, vrsta reči rečnike odrednice, dužina teksta, broj reči, broj cifara, broj imenica, broj prideva, broj glagola, broj pokaznih zamenica, broj ličnih zamenica, broj znakova interpunkcije, broj tehničkih oznaka i skraćenica, itd.

Klasifikacije kratkih poruka u odnosu na autora U disertaciji će se razmatrati dva slučaja klasifikacije kratkih poruka. U prvom slučaju, klase su autori poruka, a zadatak je svakoj poruci dodeliti njenog autora iz tog fiksnog skupa. Ovaj problem naziva se identifikacija autorstva. Na primer, neka je poznato da pošiljalac poruke može biti ili osoba A ili osoba B. Zadatak identifikacije autorstva, u tom slučaju, je konstrukcija matematičkog modela koji će za kratku poruku proceniti da li je šalje osoba A ili osoba B. Atributi koji mogu biti korisni diskriminatori autorstva su: dužina poruke, broj reči, broj cifara, broj imenica, broj prideva, broj glagola, broj znakova interpunkcije, upotreba emotograma, upotreba određenih skraćenica, i slično.

Klasifikacija kratkih poruka u odnosu na stav i raspoloženje Drugi problem klasifikacije nad kratkim porukama koji će se razmatrati u tezi naziva se analiza raspoloženja i stavova, odnosno analiza sentimenata. Ako se krene od pretpostavke da SMS poruka nosi u sebi pozitivan ili negativan stav o nekoj stvari, ali i da može biti isključivo informativna, klase mogu biti: pozitivan, negativan i neutralan stav. Na primer, za kratku poruku „Pada kiša.“ stav je neutralan i poruka je informativne prirode, dok bi se za poruku „Jao ne, opet kiša!!!“ moglo reći da njen autor nema pozitivan stav. Atributi koji mogu biti korisni diskriminatori sentimenata su: broj emotograma koji predstavljaju srećno, tužno, neutralno, zbunjeno ili neko drugo stanje, dužina poruke, broj prideva, broj uzvičnika, broj upitnika, broj tačaka, i slično.