DI Jarno N. Alanko väittelee keskiviikkona 3.6.2020 klo 16 Helsingin yliopiston Porthania-rakennuksen auditoriossa PII (Yliopistonkatu 3, 1. kerros) aiheesta Space-Efficient Algorithms for Strings and Prefix-Sortable Graphs. Vastaväittäjänä toimii apulaisprofessori Sharma Thankachan (University of Central Florida, Yhdysvallat) ja kustoksena professori Veli Mäkinen (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi. Väitöstilaisuutta voi seurata suorana verkkolähetyksenä osoitteessa https://helsinki.zoom.us/j/68865960125?pwd=bElCenBGVm5BU3hvN01ocEhENngxZz09.
Jarno N. Alangon väitöskirjatyö on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Genome-Scale Algorithmics -ryhmässä tehtävää tutkimusta. Väitöskirjatyön ohjaajana on toiminut professori Veli Mäkinen (Helsingin yliopisto).
Tilatiiviitä algoritmeja merkkijonoille ja etuliite-järjestettäville verkoille
Tilatiiviit tietorakenteet ovat aktiivinen tutkimusalue, jolle on löytynyt paljon käytännön sovelluksia kombinatoristen hahmojen hakemisessa ja bioinformatiikassa. Ajatuksena on pyrkiä rakentamaan tietorakenteita, joiden käyttämä tila on lähellä informaatioteoreettista alarajaa tai jopa sen alle, mutta kyselyt ovat silti nopeita. Viime vuosikymmenten tutkimuksen tuloksena on löytynyt suuri määrä tilatiiviitä ratkaisuja monenlaisille rakenteille, kuten bittivektoreille, merkkijonoille, puille ja verkoille.
Tässä väitöskirjassa on suunniteltu ja toteutettu kompakteja tietorakenteita bioinformatiikan ongelmiin. Tämän lisäksi työssä on laajennettu niin kutsuttujen Wheeler-verkkojen teoriaa. Tutkimustyö on julkaistu neljässä erillisessä artikkelissa.
Ensimmäisessä kahdessa artikkelissa on suunniteltu uusia tietorakenteita ja algoritmeja kahteen merkkijono-ongelmaan. Artikkelissa I esitetään algoritmi, joka pyrkii ratkaisemaan klassisen lyhyimmän yhteisen ylimerkkijonon ongelman pienessä tilassa. Artikkelissa II suunnitellaan ja toteutetaan käyttövalmis ja tiivis tietorakenne vaihtuva-asteisille Markov-malleille.
Wheeler-verkot ovat suunnattujen verkkojen osajoukko, jossa kaaret on nimikoitu kirjaimin ja jolle on tunnetusti mahdollista rakentaa tilatiivis ja tehokas indeksirakenne. Kahdessa jälkimmäisessä artikkelissa on kehitetty Wheeler-verkkojen teoriaa. Artikkelissa III teoriaa on laajennettu äärellisiin automaatteihin ja kehitetty tämän avulla uusia algoritmeja Wheeler-verkon ehdot täyttävien automaattien tunnistamiseen, järjestämiseen, determinisointiin ja minimointiin. Lisäksi artikkelissa näytetään, kuinka muunnetaan mikä tahansa syklitön äärellinen automaatti vastaavaksi Wheeler-verkon ehdot täyttäväksi pienimmäksi mahdolliseksi automaatiksi.
Artikkelissa IV on kehitetty teoreettinen menetelmä Wheeler-verkon pakkaamiselle siten, että sen indeksointiominaisuudet säilyvät. Tämä yleistää hiljattain kehitettyä tunnelointimenetelmää Burrows-Wheeler-muunnoksen pakkaamiseen.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-6168-0.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: jarno.alanko@helsinki.fi.