Seminar Katedre za računarstvo i informatiku, 12. april 2018.

• 10. April,  2018
• Komentari (0)

Naredni sastanak Seminara biće održan u četvrtak, 12. aprila 2018. u sali 718 Matematičkog fakulteta sa početkom u 18:15 časova.

Predavač: dr Aleksandar Kartelj

Naslov predavanja: PARTICIONISANjE RETKIH BIOLOŠKIH MREŽA NA K-PLEX PODMREŽE

Apstrakt: U mreži, k-plex predstavlja podskup od n čvorova takav da je je stepen svakog čvora podmreže indukovane tim podskupom čvorova najmanje n-k. Problem k-plex maksimalnog težinskog particionisanja po granama (Max-EkPP) je NP-težak problem koji podrazumava pronalaženje k-plex particionisanja ulazne mreže takvog da je suma težina svih grana u dobijenim indukovanim k-plex podmrežama maksimalna. Rešavanje Max-EkPP ima značajnu ulogu u otkrivanju novih informacija u velikih retkim biološkim mrežama. U radu je predstavljena metoda promenljivih okolina (engl. variable neighborhood method - VNS) za rešavanje problema Max-EkPP. Eksperimentalna testiranja su izvršena nad realnim metaboličkim mrežama i nad drugim dostupnim test skupovima iz literature. Predložena VNS metoda potvrđuje sva optimalna rešenja dobijena modelom celobrojnog linearnog programiranja. Za sva ostala rešenja iz literature, za koja ne postoji potvrda optimalnosti, VNS ili dostiže najbolje poznato rešenje ili ga poboljšava. VNS je takođe testiran nad test problemima velikih dimenzija koji prethodno nisu razmatrani u literaturi.

---