M.Sc. Sebastian Schmidt puollustaa väitöskirjaansa "Unitigs Are Not Enough: the Advantages of Superunitig-Based Algorithms in Bioinformatics" torstaina 31.8.2023 klo 13 Helsingin yliopiston Exactum-rakennuksen auditoriossa CK112 (Pietari Kalmin katu 5, pohjakerros). Vastaväittäjänä toimii tutkimusjohtaja Pierre Peterlongo (INRIA/Irisa – Campus de Beaulieu, Ranska) ja kustoksena apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Sebastian Schmidtin väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Graph Algorithms -tiimissä tehtävää tutkimusta. Väitöskirjan ohjaajana on toiminut apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto).
Unitigit eivät riitä: superunitig-pohjaisten algoritmien edut bioinformatiikassa
Unitigit ovat keskeinen rakenne monilla bioinformatiikan osa-alueilla, mukaan lukien genomin kokoaminen ja k-meerien (k:n mittaisten merkkijonojen) joukkojen tiivis esittäminen. Käyttämällä superunitigejä (eli unitigien supermerkkijonoja) unitigien sijaan parantaa tuloksia molemmilla osa-alueilla. Genomin kokoamisessa unitigit ovat triviaalin turvallisia siinä mielessä, että ne esiintyvät genomissa varmasti olettaen, että sekvensoinnissa ei ole virheitä. Superunitigit voivat myös olla turvallisia samassa mielessä, ja lisäksi ne johtavat käytännössä täydellisempään genomin kokoamiseen. Tähän mennessä bakteerigenomeille ja bakteerigenomijoukoille on muodostettu maksimaaliset turvalliset superunitigit. Myös niiden tehokasta listausta on tutkittu, mutta turvallisen genomin kokoamisen teoria on edelleen hajanaista, koska aiheesta olemassa olevissa julkaisuissa on pyritty vain kohti erityisiä tavoitteita eikä niissä ole yritetty kuvata olemassa olevaa teoriaa yleisessä muodossa.
Tässä väitöskirjassa esitellään leikkauspolun käsite. Leikkauspolut ovat verkkoteorian näkökulmasta turvallisen kävelyn ydin. Tutkimalla niiden loppurakennetta saadaan yksinkertainen KYLLÄ-sertifikaatti sille, että kävely on turvallinen siinä, missä aikaisemmat luonnehdinnat ovat toimineet vain EI-sertifikaateille. Loppurakenteella on myös hyödyllisiä ominaisuuksia, jotka johtavat poistojen ansiosta tehokkaampiin algoritmeihin metagenomin kokoamisessa. Bakteerigenomien tutkimisen lisäksi väitöskirjassa esitetään lineaarisille genomeille superunitig-algoritmeja, jotka toimivat myös virheitä sisältävien genomiverkkojen tapauksessa.
K-meerien joukkojen tiiviitä esitystapojen osalta väitöskirjassa osoitetaan, että optimaalinen superunitig-esitys ilman k-meerien toistoa voidaan laskea lineaarisessa ajassa. Aiemmin ajateltiin, että tämä ongelma saattaisi olla NP-vaikea, koska se on samankaltainen kuin Hamiltonin polku -ongelma solmukeskeisissä de Bruijn -verkoissa. Tässä väitöskirjassa kuitenkin osoitetaan, että ongelma on ratkaistavissa mallintamalla ongelma kaarikeskeisten de Bruijn -verkkojen avulla, jolloin Eulerin sykli antaa optimaalisen Eulertigeiksi nimetyn ratkaisun lineaarisessa ajassa.
Väitöskirjassa esitetään myös optimaalinen algoritmi superunitigeille tapauksessa, jossa k-meerien toisto on sallittua. Kutsumme näin saatuja merkkijonoja nimellä matchtigs. Esitetty algoritmi palauttaa ongelman tunnetun kiinalaisen postimiehen ongelman muunnokseen, joka taas voidaan palauttaa minimikustannuksen kokonaislukuvirtausongelman kautta minimikustannuksen täydellisen parituksen ongelmaan. Väitöskirjassa toteutetaan sekä Eulertig- että matchtig-algoritmit kiinnittäen huomiota ohjelmoinnin yksityiskohtiin siten, että algoritmit skaalautuvat joihinkin nykyään bioinformatiikan alan suurimpiin saatavilla oleviin aineistoihin. Käytännössä matchtigit voivat vähentää unitigien esittämiseen kuluvaa tilaa jopa 59 % verrattuna toistottomiin unitigeihin ilman merkittävää lisäkustannusta laskennassa. Tämän lisäksi superunitig-pohjainen esitystapa voi nopeuttaa k-meereihin pohjautuvia kyselyitä jopa 4,25-kertaisesti verrattuna unitigeihin.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio tulee olemaan saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-9380-3.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: sebastian.schmidt@helsinki.fi.