M.Sc. Daniel Valenzuela väittelee perjantaina 9.6.2017 klo 12 Helsingin yliopiston Exactum-rakennuksen auditoriossa CK112 (Gustaf Hällströmin katu 2b) aiheesta "Algorithms and Data Structures for Sequence Analysis in the Pan-Genomic Era". Vastaväittäjänä toimii Directeur de recherche Gregory Kucherov (Le Centre national de la recherche scientifique, Ranska), ja kustoksena professori Veli Mäkinen (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Algoritmeja ja tietorakenteita sekvenssianalyysiin pangenomiikan aikakaudella
Motivaatio tähän väitöskirjaan tulee kahdesta tärkeästä bioinformatiikan prosessista: geenimutaatioiden etsinnästä (variation calling) ja haplotyyppauksesta (haplotyping). Työssä edistetään sekvenssianalyysin algoritmiikkaa ja kehitetään työkaluja mittausdatan analysointiin.
Geenimutaatioiden etsinnässä pyritään identifioimaan ne muutokset perimässä, jotka erottavat yksilön lajin referenssigenomista. Tähän tarkoitukseen käytetään perimää koodaavasta DNA-eristeestä luettuja lyhyitä sekvenssejä eli lukujaksoja (read sequences). Nämä lukujaksot linjataan referenssigenomiin, jolloin eroavuudet paljastavat yksilön geenimutaatiot. Hyvin samaan tapaan voidaan suorittaa haplotyyppausta: Suvullisesti lisääntyvien eli diploidisten organismien perimä on järjestynyt kahteen joukkoon kromosomeja, joissa vastinpareilla on sama funktio. Yksi kromosomijoukko peritään äidiltä ja toinen peritään isältä. Yksittäistä kromosomijoukkoa kutsutaan haplotyypiksi. Haplotyypin vaiheistus -ongelmassa (haplotype phasing problem) pyritään selvittämään löydetyille geenimutaatioille niiden oikea haplotyyppi.
Ensimmäinen väitöskirjassa tarkasteltu ongelma on suurten genomikokoelmien tehokas indeksointi. Lempel-Ziv tiivistysalgoritmit ovat hyödyllisiä tähän tarkoitukseen. Väitöskirja keskittyy kahteen Lempel-Ziv algoritmien haaraan: RLZ- ja LZ77-algoritmeihin. Ensimmäistä näistä analysoidaan, ja kumpaankin näistä esitetään muutoksia, jolloin lopputuloksena on skaalautuva indeksi suurille ja toisteisille kokoelmille.
Kehitettyä indeksiä käytetään uuden geenimutaatioiden etsintään tarkoitetun työkalun komponenttina. Tämä indeksi kykenee hyödyntämään tuhansia referenssigenomeita yhden sijaan. Työkalua testataan mutaatiorikkailla alueilla suomalaisen alipopulaation genomeista. Uusi lähestymistapa tuottaa systemaattisesti parempia tuloksia kuin aiempi yhteen referenssigenomiin perustuva lähestymistapa.
Toinen osa väitöskirjatyöstä keskittyy haplotyyppaukseen. Aluksi sekvenssien linjauksesta esitetään yleistys diploidisille genomeille. Tämän jälkeen esitettyä mallia kehitetään ratkaisuksi haplotyypin vaiheistus -ongelmaan perhe-kolmikko-tapauksessa, jossa geenimutaatiot on selvitetty sekä yksilölle että hänen vanhemmilleen. Lopuksi lukujaksoihin perustuvan haplotyyppien vaiheistus -ongelman tapauksessa palataan perusalgoritmiikkaan, ja johdetaan aikajanojen skedulointiongelmaan perustuva ratkaisu lukujaksojen suodatukseen; väitöskirjatyössä esitetään ongelmaan tarkka polynomiaikainen ratkaisu sekä lähes lineaariaikainen 2-approksimaatioalgoritmi.
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-3231-4.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: daniel.valenzuela@helsinki.fi.