Doctoraat in de ingenieurswetenschappen: computerwetenschappen

Uitbreiding van graphlets naar grotere orde en generische graaftypen


Doctorandus Publieke verdediging
Naam: Ine Melckenbeeck   Datum: Dinsdag 27/08/2019 om 16:00 
Adres: ()
, null null
  Lokatie: auditorium 1, iGent, eerste verdieping, Technologiepark Zwijnaarde 126, 9052 Zwijnaarde
Contact FEA: info.ea@ugent.be   Taal: Nederlands

Curriculum
Master of science in de Fysica en Sterrenkunde, UGent, 2014

Promotor
Mario Pickavet
Pieter Audenaert

Examencommissie
prof. Filip De Turck
Mario Pickavet (EA05)
Pieter Audenaert (EA05)
Yvan Saeys
Natasa Przulj
Vanessa Vermeirssen
Didier Colle, Universiteit Gent, Faculteit Ingenieurswetenschappen en Architectuur, EA05 - Vakgroep Informatietechnologie, Technologiepark Zwijnaarde 126, 9052 Zwijnaarde
E: didier.colle@ugent.be

Onderzoeksthema

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.


Taal proefschrift
Engels

Documenten