M.Sc. Manuel Cáceres puollustaa väitöskirjaansa "Parameterized and Safe & Complete Graph Algorithms for Bioinformatics" tiistaina 3.10.2023 klo 13 Helsingin yliopiston Physicum-rakennuksen auditoriossa E204 (Gustaf Hällströmin katu 2, 2. krs). Vastaväittäjänä toimii professori Christian Komusiewicz (Friedrich-Schiller-Universität Jena, Saksa) ja kustoksena apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Manuel Cáceresin 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).
Parametrisoidut sekä turvalliset ja täydelliset verkkoalgoritmit bioinformatiikassa
Koska verkot ovat monikäyttöisiä, ne ovat bioinformatiikassa suosittu tapa mallintaa dataa (esimerkiksi pangenomiikassa) ja laskentaongelmia (esimerkiksi usean sekvenssin kokoamisessa). Yhtäältä datan määrän kasvu rajoittaa pangenomiikan laskentaongelmien ratkaisumenetelmien ajoaikaa. Toisaalta taas teoreettisia työkaluja, jotka parantavat monen sekvenssin kokoamisen laatua, on vähän verrattuna niiden menestyksekkääseen soveltamiseen klassisessa genomin kokoamisongelmassa.
Tässä vaitöskirjassa kehitämme nopeampia ja hienostuneempia ratkaisuja verkko-ongelmiin bioinformatiikassa. Saavutamme tuloksemme parametrisoitujen algoritmien sekä turvallisten ja täydellisten algoritmien avulla.
Kahdessa ensimmäisessä artikkelissa esitämme ensimmäisen parametrisoidun lineaariaikaisen ratkaisun maksimiantiketju- ja minimipolkupeiteongelmiin. Algoritmit käyttävät parametrina verkon leveyttä, joka havaintojen mukaan on pangenomiikassa pieni. Näin ollen, kun tämä parametri katsotaan vakioksi, ratkaisujemme ajoaika on optimaalinen.
Kahdessa viimeisessä artikkelissa käytämme turvallisten ja täydellisten algoritmien kehystä ratkaistaksemme laskentaongelmia, joiden ratkaisu on joukko polkuja. Erityisesti esitämme tehokkaan turvallisen ja täydellisen algoritmin polkupeiteongelmaan ja virtauksen hajottamiseen. Tämän algoritmin toteutuksemme näyttää, että algoritmimme parantaa ratkaisun laatua.
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-9433-6.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: manuel.caceresreyes@helsinki.fi.