Extension of Graphlets to Larger Order and Generic Graph Types

Promovendus/a
Ine Melckenbeeck
Faculteit
Faculteit Ingenieurswetenschappen en Architectuur
Vakgroep
Vakgroep Informatietechnologie
Curriculum
Master of Science in de fysica en de sterrenkunde, Universiteit Gent, 2014
Academische graad
Doctor in de ingenieurswetenschappen: computerwetenschappen
Taal proefschrift
Engels
Vertaling titel
Uitbreiding van graphlets naar grotere orde en generische graaftypen
Promotor(en)
prof. Mario Pickavet, vakgroep Informatietechnologie - dr. Pieter Audenaert, vakgroep Informatietechnologie
Examencommissie
voorzitter prof. Filip De Turck (academisch secretaris) - dr. Pieter Audenaert (Vakgroep Informatietechnologie) - prof. Didier Colle (Vakgroep Informatietechnologie) - prof. Mario Pickavet (Vakgroep Informatietechnologie) - prof. Natasa Przulj (University College London, United Kingdom) - prof. Yvan Saeys (Vakgroep Toegepaste Wiskunde) - dr. ir. Vanessa Vermeirssen (Vakgroep Biomoleculaire Geneeskunde)

Korte beschrijving

Genen en eiwitten voeren hun functies samen uit. Zo vormen ze netwerken. Binnen netwerken ontstaan kleine patroontjes, genaamd graphlets. In bio-informatica worden graphlets gebruikt om belangrijke patronen te vinden en netwerken te vergelijken. Verschillende symmetrische posities voor knopen binnen een graphlet heten orbits. De orbits waarin een knoop voorkomt geven informatie over de functie van die knoop. Vergelijkingen vereenvoudigen het tellen van orbits. Om orbits van graphlets met k knopen te tellen, kan men graphlets met k-1 knopen vinden en vergelijkingen oplossen. Handmatige constructie van die vergelijkingen is onhaalbaar voor grote graphlets; ze moeten automatisch gegenereerd worden. Jesse is ons programma dat graphlets telt met vergelijkingen. Het genereert een groot, lineair afhankelijk stelsel vergelijkingen, ordent de (k-1)-graphlets in een boom, vindt de (k-1)-graphlets en lost de vergelijkingen op, onafhankelijk van de orde van de graphlets. Jesse's looptijd is afhankelijk van de vergelijkingkeuze. Vergelijkingen met dichtere (k-1)-graphlets zijn de snelste in schaarse grafen; vergelijkingen met schaarsere (k-1)-graphlets zijn sneller in dichte grafen. Uiteindelijk werden graphlets uitgebreid naar grafen met verschillende taktypes. Daarom werden alle voorgaande algoritmes aangepast om onafhankelijk te zijn van de taktypes.

Praktisch

Wanneer
Dinsdag 27 augustus 2019, 16:00
Waar
auditorium 1, iGent, eerste verdieping, Technologiepark Zwijnaarde 126, 9052 Zwijnaarde

Meer info

Contact
doctoraat.ea@UGent.be