Academic year 2018/19

Enorman rast količine podataka koji potiču iz bioloških istraživanja, koji se svakodnevno pronalaze i čuvaju u raznim bazama podataka, kao i specifičnost i kompleksnost samih bioloških podataka, dovela je do potrebe razvoja sofisticiranih računarskih metoda pomoću kojih bi se ti podaci struktuirali, pohranjivali, analizirali i tumačili. Stoga je u naučnoj oblasti bioinformatike posljednjih godina fokus stavljen na razvoj matematičkih i računarskih modela i metoda kojim bi se zadaci obrade bioloških podataka rješavali na što efikasniji način.

Potreba za sistematskim pristupom izučavanja određenih bioloških struktura (kao što su proteini ili metaboliti), kao i veza između njih, dovela je do formiranja bioloških mreža, koje se dalje analiziraju u cilju dobijanja korisnih bioloških informacija. Predstavljanje bioloških procesa u vidu mreže omogućava jasnije sagledavanje kompletnog procesa i konteksta u kojem se dešava, a omogućava lakše izvođenje novih saznanja i zaključaka. Biološke mreže su apstraktan prikaz bioloških sistema, koji sadrži većinu važnih karakteristika. Čvorovima u mreži odgovaraju komponente biološkog sistema, a grane između čvorova predstavljaju veze ili zavisnosti između komponenti.

Predmet istraživanja ove doktorske disertacije biće particionisanje velikih bioloških mreža na manje podmreže, kao i grupisanje čvorova mreže u određene kategorije. Particionisanje mreže se vrši po različitim kriterijumima koji osiguravaju da podmreže imaju određena topološka svojstva, dok se grupisanjem pronalaze biološkim elementi sa sličnim funkcijama. Podmreže dobijene kao rezultat particionisanja će dalje biti analizirane sa biološkog aspekta i predstavljaće osnov za: prepoznavanje značajnih grupa čvorova (proteina/metabolita) u mreži, kao i razvoj novih ili unapređenje postojećih alata za biološku, funkcionalnu i molekulsku anotaciju proteina. U okviru disertacije razmatraće se četiri problema. Problem particionisanja rijetkih bioloških mreža na međusobno povezane podmreže, tzv. k-plex podmreže koje se formalno definišu na sljedeći način. Neka je dat graf G=(V,E). Podgraf od n čvorova grafa G je k-plex ako je svaki čvor susjedan sa bar (n-k) čvorova u tom grafu. Problem k-plex maksimalnog težinskog particionisanja po granama (engl. maximum edge-weight k-plex partitioning problem -- Max-EkPP) je problem koji podrazumijeva pronalaženje k-plex particionisanja ulaznog težinskog grafa takvog da je suma težina svih grana u dobijenim indukovanim k-plex podgrafovima maksimalna.

Nad listom metaboličkih reakcija posmatra se problem predikcije uloge metabolita u metaboličkim reakcijama. Motivacija za rješavanje problema predikcije je u tome što dobijena saznanja mogu doprinijeti boljem razumijevanju metaboličkih putanja (engl. metabolic pathways). Identifikacija uloge metabolita u reakciji se koristi za dobijanje novih saznanja o vezi između metabolita na osnovu njihovog učešća u zajedničkoj reakciji.

Klasterovanjem velikih mreža dimenzija strukture se smanjuje, a funkcionalnosti se očuvaju u gusto povezanim komponentama. Jedan od poznatih problema u ovoj oblasti je particionisanje velike mreže na manje visoko povezane (engl. highly connected) podmreže uklanjanjem što je moguće manje grana. Za podmrežu sa n čvorova kažemo da je visoko povezana ako je stepen svakog čvora bar n/2. Dobijene podmreže predstavljaju grupe bioloških elemenata sa sličnim funkcijama.

Problem dodavanja što je moguće manje grana u graf da bi se određeni skupovi čvorova povezali formalno se definiše na sljedeći način. Dat je neusmjeren graf G=(V,E), gdje je V skup čvorova, a E skup grana i kolekcija C podskupova skupa V. Potrebno je naći skup dodatnih grana E’ minimalne kardinalnosti takav da je svaki podgraf grafa G=(V,E∪ E’) koji je indukovan čvorovima iz podskupa Ci. Dobijene grane za određenu biološku mrežu predstavljaju osnov za dalju identifikaciju značajnih grupa bioloških elemenata.

U ovom izlaganju za navedene probleme particionisanja i grupisanja u biološkim mrežama biće prikazani postojeći i neki unaprijeđeni i novorazvijeni modeli, koji bi omogućili primjenu različitih statističkih i optimizacionih tehnika za njihovo rješavanje.

Očuvanje nacionalnog kulturnog nasleđa je od izuzetnog značaja za razumevanje identiteta grupe ili pojedinca. Konvencija UNESCO iz 2003. godine prepoznaje različite domene u kojima se nematerijalno kulturno nasleđe može manifestovati. To su tradicije govora i izražavanja, izvođenje umetničkih dela, društvena dešavanja, rituali, praznični događaji, znanje i njegova primena u vezi prirode i svega oko nas, kao i razvoj i primena zanatskih veština. Srpsko kulturno nasleđe je specifičan spoj više različitih tradicija i naracija: slovenske, vizantijske, starobalkanske, herojske, nacional-romantičarske, prosvećeno-evropske. Primenom informacionih tehnologija i digitalizacije kao rezultat u domenu kulturnog nasleđa je stvaranje digitalnih baza podataka o nematerijalnoj kulturnoj baštini. S druge strane, kako je postalo jednostavnije proizvođenje digitalnih multimedijalnih dokumenata, to je takvih dokumenata sve više, i često je nemoguće upravljati njima, efikasno pretraživati i dobavljati relevantne podatake ili cele dokumenate bez uspostavljanja odgovarajuće organizacije. Pod organizacijom se smatra smeštanje dokumenata u multimedijalnu bazu podataka, uz definisanje odgovarajuće strukture za opis metapodataka i označavanje dokumenata po relevantnim metapodacima.

Predmet istraživanja ove doktorske disertacije biće razvoj adekvatnog dizajna i implementacije multimedijalne baze podataka nematerijalnog kulturnog nasleđa dela Balkana kao i automatska anotacija sadržaja ove multimedijalne baze kao osnova za uspešnu tematsku pretragu i pretragu po metapodacima. Doktorska disertacija će se baviti i povezivanjem sadržaja baze sa geolokacijskim informacijama na mapi, kao i prostorno-vremenskom pretragom. Istraživanje je motivisano multimedijalnom kolekcijom koja predstavlja rezultat petnaestogodišnjeg terenskog istraživanja koje su izveli istraživači Balkanološkog instituta SANU. Istraživači su intervujisali lokalno stanovništvo na različitim lokacijama u području Balkana. Kolekcija se sastoji od audio i video materijala, fotografija, rukopisa i tekstualnih protokola. Protokoli su dokumenti u vidu nestruktuiranog ili polustruktuiranog teksta koji imaju za cilj da opišu određeni audio ili video materijal.

U disertaciji će biti primenjene metodologije razvoja objektno-orijentisane (PostgreSQL) baze podataka za upravljanje metapodacima o multimedijalnim materijalima i XML baze podataka koja će omogućiti pretraživanje protokola i informacija ekstrahovanih iz njih. Za rad sa geolokacijskim podacima koristiće se metodologije prostorne baze podataka (PostGIS). Za obradu protokola koristiće se metoda obrade prirodnih jezika zasnovana na konačnim transduktorima. Biće razvijena biblioteka konačnih transduktora za ekstrakciju i anotaciju metapodataka i sadržaja koji se odnosi na neke od tema karakterističnih za nematerijalno kulturno nasleđe. Ova metoda koristi jezičke resurse poput jezičkih rečnika reči u osnovnom i izvedenim oblicima. Formirano znanje u fazi analize protokola primenićemo u izgradnji konačnih transduktora. Za klasifikaciju multimedijalnog materijala prema sadržaju protokola primeniće se metoda mašinskog učenja zasnovana na različitim tipovima n-grama nad odgovarajućom vrećom reči. Biće razvijen i sistem za anotaciju i organizovanje samih multimedijalnih dokumenata u pretraživu formu kao i za njihov prikaz. Multimedijalna baza kulturnog nasleđa biće primenjena na pretraživanje po metapodacima kao i po sadržaju, uz razvoj interaktivne -vremenske mape.

Teorija kompleksnih mreža bavi se proučavanjem strukture kompleksnih sistema sastavljenih od velikog broja elemenata između kojih postoje izrazito jake nelinearne interakcije. Matematičku osnovu za proučavanje strukture kompleksnih sistema predstavlja teorija grafova, dok za analiziranje dinamičkih procesa važnu primenu imaju metode statističke fizike. Struktura kompleksnog sistema predstavlja se mrežom tako da se elementi sistema preslikavaju na čvorove u mreži, a interakcije između elemenata su predstavljene kao grane između čvorova. U odnosu na jednostavne ili slučajno generisane mreže, kompleksne mreže ispoljavaju veliku nehomogenost pri distribuciji grana. Karakteristično je da se javlja visoka koncentracija grana u okviru pojedinih grupa čvorova i istovremeno niska koncentracija grana između čvorova u različitim grupama. Ovakve grupe čvorova se nazivaju klasteri (moduli, zajednice) i vrlo često imaju zajedničke osobine i uloge u kompleksnom sistemu. Problem pronalaženja ovakvih grupa u kompleksnim mrežama naziva se problem klasterovanja na kompleksnim mrežama. Razvijanje metoda za rešavanje ovog problema i njihova primena su od velikog značaja za razumevanje dinamike i evolucije kompleksnih sistema. Osim toga, mogu omogućiti bolju vizualizaciju i pružiti neophodne informacije o pojedinačnim čvorovima i njihovim ulogama u mreži. Na primer, pojedini čvorovi u klasteru mogu imati ulogu u povezivanju klastera sa ostatkom mreže, dok drugi čvorovi mogu imati ulogu kontrolisanja i stabilizacije klastera.

Najzastupljeniji pristup za klasterovanje na kompleksnim mrežama se ogleda u definisanju funkcije, koja meri kvalitet particionisanja mreže, i konstruisanju metoda za pronalaženje particije za koju se dostiže maksimalna vrednost definisane funkcije. Ovakvim pristupom problem klasterovanja se svodi na problem kombinatorne optimizacije i u tom slučaju na raspolaganju je širok spektar postojećih metoda optimizacije. Od definisanih mera kvaliteta, najpopularnija je modularnost (engl. modularity) koju su 2004. godine definisali Mark Njuman i Mišel Girvan. Modularnost klastera predstavlja razliku između stvarnog broja grana unutar klastera i očekivanog broja grana unutar klastera u mreži sa čvorovima istog stepena, a slučajno postavljenim granama. Modularnost mreže predstavlja zbir modularnosti svih klastera. Kako je traženje particije mreže sa najvećom vrednošću modularnosti NP-težak problem i broj mogućih particija raste eksponencijalno u odnosu na broj čvorova za rešavanje problema razvijaju se heurističke metode.

U okviru izlaganja biće predstavljena ADVNDS metoda (engl. Ascent-Descent Variable Neighborhood Decomposition Search) koja je razvijena za maksimizaciju modularnosti mreže. U cilju efikasne primene za klasterovanje na kompleksnim mrežama velikih dimenzija metoda ima dodatni mehanizam za dekompoziciju problema na manje potprobleme i unapređeni mehanizam za prevazilaženje lokalnih maksimuma modularnosti korišćenjem kriterijuma za povremeno prihvatanje lošijeg rešenja od trenutno razmatranog. Pored toga biće predstavljena funkcija za merenje kvaliteta particionisanja mreže, koja bi trebalo da prevaziđe nedostatke uočene detaljnom analizom modularnosti.

Decenije rada su uložene u razvijanje efikasnih računa, struktura podataka, algoritama i heuristika za automatske dokazivače za logiku prvog reda. Dokazivači za logike višeg reda zaostaju u pogledu efikasnosti.

Rad koji predstavljam prikazuje implementaciju dokazivača za logiku višeg reda baziranog na vrlo napredom superpozicionom dokazivaču E. Ovaj red objašnjava jedan način na koji se prilagodjavaju strukture podataka, algoritmi i heuristike kako bi se podržala logika višeg reda bez lambda izraza, formalizam koji podržava parcijalnu aplikaciju i primenjene promenljive. Naš pristup pokazuje dve bitne prednosti u odnosu na razvoj dokazivača za logiku višeg reda ispočetka: zadržavamo visoke performanse dokazivača za logiku prvog reda i uspevamo da rešimo i do 15% više problema u odnosu na tradicionalni pristupe zasnovane na prevođenju u logiku prvog reda. Logika višeg reda bez lambda izraza predstavlja prvi korak ka proširenjima na druge logike višeg reda.

U predavanju će biti prikazana tri klasifikaciona problema u kontekstu obrade prirodnih jezika: problem validacije bilingvalnih parova višečlanih leksema, problem identifikacije autora kratkih tekstova, kao i problem analize osećanja u kratkim porukama.

Jedan od ciljeva disertacije je razvijanje potpuno automatizovanog softverskog sistema za generisanje bilingvalne domenske terminologije. Što se resursa tiče, ovaj sistem oslanjao bi se samo na postojanje paralelnih, domenskih tekstova i, ne i nužno, liste domenskih pojmova na izvornom, engleskom jeziku. Sistem bi koristio postojeći alat LeXimir za ekstrakciju domenske terminologije na ciljnom, srpskom jeziku, a u slučaju nepostojanja liste domenskih pojmova na izvornom jeziku, koristio bi i postojeći alat FlexiTerm za ekstrakciju domenskih termina iz engleskog jezika. Sistem bi implementirao novi metod generisanja bilingvalne liste domenskih termina, uz automatsku validaciju dobijenih parova, kao i naknadno proširenje primerima upotrebe.

Drugi problem odnosi se na identifikaciju autora proizvoljnog kratkog teksta (SMS, Viber, Twitter itd.). U ovom slučaju, važno je modelovati sadržaj dokumenta na najadekvatniji način, odnosno prepoznati skup atributa koji najbolje karakterišu dati dokument i koji ga diskriminišu u odnosu na ostale dokumente te kolekcije.

Analiza stavova i raspoloženja kod kratkih tekstova, poput poruka sa različitih socijalnih mreža ili klijenata za razmenu poruka, predstavlja svojevrstan izazov. Takve poruke nose značajno manju količinu informacija u odnosu na, na primer, forumske diskusije. Uočen je trend da autori kratkih poruka teže ka tome da kroz specifičnu upotrebu znakova interpunkcije, ponavljanja slova i simbola, pisanjem samo velikim slovima, upotrebom specijalizovanih skraćenica i emotograma, ostvaruju sličnost pisanog sa govornim jezikom. Na taj način, autori izražavaju sebe, svoje stav i svoja osećanja.