FM Niko Välimäki väittelee tiistaina 21.8.2012 kello 12 (Helsingin yliopiston päärakennus, Unioninkatu 34, Auditorio XIV (vanha puoli), 3. kerros) aiheesta "Applications of Compressed Data Structures on Sequences and Structured Data". Tutkimus kuuluu tietojenkäsittelytieteen alaan ja erityisesti tietorakenteisiin.

Tiivistettyjen tietorakenteiden sovelluksia tekstimuotoiselle ja rakenteelliselle tiedolle

Tiivistettyjen tietorakenteiden viimeaikainen kehitys on luonut mielenkiintoisia mahdollisuuksia tieteidenväliseen tutkimukseen ja sovelluksiin. Tiivistetty tietorakenne tarjoaa ensisijaisesti valinnan tilan ja laskenta-ajan välisestä suhteesta; siinä missä perinteinen tietorakenne vaatii ylimääräistä tilaa alkuperäisen syötteen lisäksi, tiivistetty tietorakenne korvaa syötteen ja vaatii tilan, joka on verrannollinen tiivistetyn syötteen kokoon. Käytössä olevan muistin määrä on usein rajoitettu, jolloin saattaa olla mielekästä käyttää enemmän laskenta-aikaa, jos se mahdollistaa suurempien syötteiden käsittelyn. Tiivistetyt tietorakenteet eivät kuitenkaan ole vielä saavuttaneet laajempaa suosiota muiden tieteenalojen keskuudessa. Tässä työssä tutkitaan kuinka tiivistettyjä tietorakenteita voidaan soveltaa bioinformatiikan, data-analyysin ja tiedonhaun tarpeisiin.

Tämä väitöskirja esittelee uusia sovelluskohteita tiivistetyille tietorakenteille ja sisältää kokeellisen arvion ehdotettujen menetelmien käytännöllisyydestä. Ehdotetut sovelluskohteet ovat (i) merkkijonojen louhinta annetuilla frekvenssirajoitteilla, (ii) merkkijonojen alku- ja loppuosien likimääräisten päällekkäisyyksien laskeminen, (iii) polkupohjainen verkkokerneli esimerkiksi entsyymin katalysoiman reaktion ennustamiseen, sekä (iv) XML-muotoisen datan indeksointi siten, että kyselyt sekä puurakenteen että tekstisisällön suhteen pystytään ratkaisemaan tehokkaasti. Ongelma (i) on tiedonlouhintaa, jossa tavoitteena on löytää osajonot, jotka erottavat kaksi merkkijonojoukkoa toisistaan. Ongelma (ii) on ensimmäisiä vaiheita, kun DNA-sekvensoinnista saatuja fragmentteja kootaan yhteen. Ongelman (iii) motivaatio on koneoppimisessa, jossa kerneli on eräs tapa mallintaa monimutkaisia syötteitä. Ongelman (iv) tausta on tiedonhaussa.

Väitöskirjassa ehdotetut menetelmät saavuttavat sekä teoreettisia että käytännön etuja verrattuna aiempiin kirjallisuudessa esitettyihin menetelmiin. Saavutetut tulokset on julkaistu eri osa-alojen foorumeilla, mukaan lukien bioinformatiikan, tiedonlouhinnan ja tietojärjestelmien konferensseja ja lehtiä.

Väitöskirjan saatavuus

Väitöskirjan elektroninen versio on saatavilla e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-952-10-8017-3.

Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: (09) 191 51151 tai niko.valimaki@cs.helsinki.fi.