Counting small patterns in networks

Tomaž Hočevar (Avtor), Janez Demšar (Mentor)

Povzetek

Omrežja pogosto uporabljamo za vizualizacijo in analizo relacij med pari entitet, ki jih predstavimo z množico vozlišč, povezave med njimi pa predstavljajo relacije. Ena izmed relacij v bioinformatiki, ki jo pogosto modeliramo z omrežji, so interakcije med pari proteinov. Nedavne študije v zvezi z lokalno strukturo takih omrežij so uporabljale majhne povezane vzorce s 4 ali 5 vozlišči, ki jim rečemo tudi grafki. Vozlišča grafkov se običajno delijo v orbite glede na njihovo "vlogo" oz. simetrije. Kolikokrat neko vozlišče v omrežju nastopa v vsaki izmed orbit, predstavlja neke vrste podpis lokalne strukture v okolici vozlišča. Z zanašanjem na predpostavko, da je lokalna struktura vozlišča povezana z njegovo funkcijo v omrežju, je raziskovalcem uspelo z uporabo grafkov napovedati nove funkcije proteinov. Glavna ovira pristopov na osnovi grafkov je običajno v času, ki ga zahteva štetje grafkov. Ta omejitev je vedno bolj izrazita zaradi vedno večje količine razpoložljivih podatkov. Disertacija se posveča izboljšavi obstoječih metod za štetje grafkov. Te namreč delujejo na osnovi enostavnega izčrpnega naštevanja vseh grafkov v omrežju. V disertaciji predstavljen algoritem Orca prešteje grafke, ne da bi jih naštel, kot to počnejo ostale metode. Izkorišča povezave med frekvencami orbit za pripravo sistema enačb, ki ga sestavi izredno učinkovito. Orca za štetje grafkov velikosti k našteje zgolj grafke velikosti k-1. Tako doseže pohitritev, ki je sorazmerna največji stopnji vozlišča v omrežju. V praksi to pomeni, da prešteje grafke v večjih omrežjih proteinskih interakcij 50 do 100-krat hitreje. Algoritem Orca je bil v osnovi razvit za štetje grafkov in orbit vozlišč velikosti 4 in 5. Pristop smo uspešno prilagodili tudi štetju orbit povezav z enakimi prihranki glede časa izvajanja. Rešitev je možno posplošiti za štetje poljubno velikih grafkov. V ta namen smo identificirali potrebne pogoje in dokazali, da jih je mogoče izpolniti tudi v primeru štetja večjih grafkov. Disertacija se posveča tudi problemu generiranja naključnih omrežij s predpisano porazdelitvijo grafkov. Ta problem predstavlja motivacijo za prilagoditev algoritma Orca za uporabo v dinamičnih oz. spreminjajočih omrežjih, kjer lahko nastajajo nove povezave ali pa obstoječe propadajo. Spremembe so lahko posledica postopka za generiranje naključnega omrežja ali pa so del procesa, ki ga omrežje modelira. Generirana omrežja se zelo približajo želeni porazdelitvi grafkov. Poleg števila grafkov pa so si podobna tudi po drugih merah lokalne strukture omrežij. Razviti algoritem je pomembno orodje za analizo omrežij z grafki in predstavlja pomemben korak k analizi večjih in gostejših omrežij. Kot najhitrejša metoda štetja grafkov je tudi osnova nadaljnjega raziskovanja učinkovitih metod štetja vzorcev v omrežjih. Doktorska disertacija temelji na treh objavljenih znanstvenih člankih, ki skupaj s poglavjem, ki vsebuje še neobjavljeno delo, tvorijo jedro disertacije.

Ključne besede

graphlets;orbits;network;graph;subgraph;pattern;counting;computer and information science;doctoral dissertations;

Podatki

Jezik:	Angleški jezik
Leto izida:	2018
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[T. Hočevar]
UDK:	004.7:575.112(043.3)
COBISS:	1537692099
Št. ogledov:	896
Št. prenosov:	494
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Counting small patterns in networks
Sekundarni povzetek:	Networks are an often employed tool that can help us visualize and analyze binary relationships by representing the entities as a set of nodes and the relations between them as edges in the network. One type of relations in the field of bioinformatics that is often modeled by networks are interactions between pairs of proteins. Recent studies have focused on analyzing the local structure of such networks by observing small connected patterns consisting of 4 or 5 nodes, which are also known as graphlets. The nodes of graphlets are further divided into orbits by their "roles" or symmetries. The number of times a node from the network participates in each orbit forms a signature of the node's local network topology. Working under the assumption that the node's local topology is correlated with its function in the network, researchers have successfully used graphlets to predict new protein functions. The bottleneck of graphlet-based approaches is usually in the time required to count them. This restriction is becoming even more pronounced with a growing amount of available data. This dissertation focuses on improving existing graphlet counting techniques that are based on simple exhaustive enumeration. We present the algorithm Orca that counts graphlets and their orbits instead of enumerating them. It exploits relations between orbit counts to construct a system of equations that can be set up efficiently. Orca achieves this by enumerating (k-1)-node graphlets to count k-node graphlets, effectively obtaining a speed-up by a factor proportional to the maximum degree of a node in the network. In practical terms, it counts graphlets in larger protein-protein interaction networks about 50-100 times faster. Orca was designed for counting graphlets with 4 and 5 nodes. However, we adapt the approach to counting edge-orbits in addition to the original node-orbits with the same gains in run time. We also show that this approach can be generalized to graphlets of arbitrary size by identifying the necessary conditions and proving that these conditions can be fulfilled even for larger graphlets. Finally, we consider the problem of generating random graphs with prescribed graph\-let distributions. This motivated the adaptation of Orca for dynamic or changing networks, where edges can be added or removed. These changes can be a consequence of the procedure for generating a random graph or can be inherent in the network and the process it models. The generated graphs closely match the desired graphlet counts and as a consequence approximate other structural measures as well. The developed algorithm is a valuable tool for graphlet-based network analysis and a significant stepping stone towards analyzing larger and denser networks. As the fastest graphlet counting method it also presents a basis for further development of efficient pattern counting methods in graphs. This doctoral dissertation is based on three published papers that together with a chapter containing some unpublished work form the core of the dissertation.
Sekundarne ključne besede:	omrežja;algoritem Orca;grafki;štetje;orbite;grafi;podgrafi;vzorci;računalništvo in informatika;doktorske disertacije;Omrežja;Disertacije;Vzorci;Štetje;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Doktorsko delo/naloga
Študijski program:	1000474
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	IX, 126 str.
ID:	10915327