FM Tuukka Norri väittelee perjantaina 17.6.2022 klo 13 Helsingin yliopiston Exactum-rakennuksen auditoriossa B123 (Pietari Kalmin katu 5, 1. kerros) aiheesta On Founder Segmentations of Aligned Texts. Vastaväittäjänä toimii professori Knut Reinert (Freie Univerität Berlin, Saksa) ja kustoksena professori Veli Mäkinen (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi. Väitöstilaisuutta voi seurata suorana verkkolähetyksenä osoitteessa https://video.helsinki.fi/unitube/live-stream.html?room=l10.
Tuukka Norrin väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Genome-Scale Algorithmics -tiimissä tehtävää tutkimusta. Väitöskirjatyön ohjaajana on toiminut professori Veli Mäkinen (Helsingin yliopisto).
Linjattujen tekstien kantasegmentoinneista
Linjatut tekstit, kuten biologisten sekvenssien linjaukset tai monilinjaukset, ovat kahden tai useamman tekstin kokonaisuuksia, joista on määritetty toisiaan vastaavat osat. Tyypillisesti nämä osat on etsitty siten, että yhden tekstin muuttamiseen toiseksi tarvittaisiin mahdollisimman vähän muokkausoperaatioita. Näitä voivat olla esimerkiksi tekstin lisääminen, poistaminen ja korvaaminen. Biologisten sekvenssien tapauksessa linjauksilla ja monilinjauksilla on useita eri käyttötarkoituksia.
Tässä väitöskirjassa tarkastelemme eräitä tekstin segmentointiin eli ositukseen liittyviä ongelmia, joissa syötteenä on kokoelma linjattuja tekstejä. Eräässä ongelmassa halutaan muodostaa ositus, jota käyttäen voidaan tuottaa pienempi määrä uusia tekstejä. Näitä kutsutaan kantasekvensseiksi, sillä syötteenä annetut sekvenssit voidaan tietyin ehdoin muodostaa kantasekvensseistä. Ratkaisemme tämän ongelman erikoistapauksen, jossa segmenttien reunojen on sijaittava kaikissa syötteen teksteissä samoissa kohdissa. Esittämässämme ratkaisussa minimoidaan segmenttien maksimimäärä näin muodostuvissa lohkoissa siten, että segmenteillä on annettu minimipituus. Suunnittelemamme algoritmin aikavaativuus on lineaarinen. Lisäksi esitämme algoritmista version, joka käsittelee sekvenssien sijasta varianttidataa, ja käytämme algoritmin tuottamia kantasekvenssejä osana genotyypityssovellusta.
Toisessa ongelmassa tarkoituksenamme on osittaa teksti siten, että tuloksena saatavat tekstisegmentit ovat tietyin ehdoin toisistaan poikkeavia. Seurauksena segmenteistä voidaan muodostaa verkko, josta voidaan etsiä siinä esiintyvien merkkijonojen osia tehokkaasti. Kyseisiä verkkoja kutsutaan kantasegmentteihin perustuviksi verkoiksi, jotka ovat joko kokonaan tai osittain toisteettomia. Esitämme algoritmit, joilla löydetään tarvittava ositus, muodostetaan hakutietorakenne sekä suoritetaan haku. Algoritmimme toimivat lineaarisessa tai lähes lineaarisessa ajassa, mikä tekee niistä käytännön sovellusten kannalta hyödyllisiä.
Väitöskirja pohjautuu viiteen julkaisuun sekä aikaisemmin julkaisemattomaan tutkimukseen. Ensimmäisessä julkaisussa laajennamme sijainnittaisen Burrows-Wheeler-muunnoksen käsittelemään binääriaakkostoa suuremmat vakiokokoiset aakkostot. Muunnosta käytetään osana toisessa julkaisussa esittämäämme segmentointialgoritmia, joka tarvitaan kantasekvenssien muodostamiseen. Kantasekvenssejä hyödynnetään osana hakutietorakennetta lyhytlukuja käyttävässä genotyypityssovelluksessa kolmannessa julkaisussa. Vertaamme sovellusta muihin vastaaviin ja osoitamme, että sovelluksellamme erityisesti yhden nukleotidin polymorfismit havaitaan hyvällä herkkyydellä ja tarkkuudella.
Neljännessä julkaisussa kuvaamme kantasegmentteihin perustuvat verkot. Osoitamme, että jos verkon solmujen tunnisteet ovat toisteettomia, voidaan verkosta muodostaa tehokas hakutietorakenne. Viidennessä julkaisussa laajennamme kantasegmentteihin perustuvien verkkojen teoriaa käsittämään osittain toisteettomat verkot näyttämällä, kuinka indeksoinnin mahdollistava verkko voidaan tuottaa, vaikka syötteessä olisi lisäyksiä ja poistoja.
Lisäksi osoitamme, että osittain toisteettomilla kantasegmentteihin perustuvilla verkoilla on tietynlainen välittömyysominaisuus. Käyttäen ominaisuutta hyödyksi lisäämme verkosta tehtyyn hakutietorakenteeseen tietoa poluista, jotta voimme hakutilanteessa määritellä näistä vaihtoehdoista ne polut, joilla annettu hahmo esiintyy.
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-8215-9.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: tuukka.norri@helsinki.fi.