Myös epäonnistumiset vievät tietojenkäsittelytieteen tutkimusta eteenpäin

Perimän pieniä poikkeuksia on työlästä etsiä, vaikka tietojenkäsittelytiede on etsinyt ratkaisuja genomiseen tiedonhakuun vuosikymmeniä. Veli Mäkinen tietää, että myös mahdottomuustulos auttaa tiedeyhteisöä.

Miltä tuntuu, kun tutkimuksen tulos ei ole sitä mitä toivottiin? Hyvältä, sanoo tietojenkäsittelytieteen professori Veli Mäkinen.

Lähes kymmenen vuoden ajan Mäkinen tutkimusryhmineen on etsinyt aiempaa tehokkaampaa tapaa etsiä muutoksia ihmisen DNA:sta. Nämä muutokset muodostavat yksilön perimän ja voivat myös vaikuttaa sairauksien syntyyn.

Tutkimus valmistui hiljattain, ja tulos oli eräänlainen umpikuja: tehokasta hakualgoritmia on mahdotonta löytää, ellei samalla ratkaista toista tietojenkäsittelytieteen vaikeaa ydinongelmaa. Tutkimus julkaistaan ICALP-konferenssissa heinäkuussa 2019. Tutkimusta on tehty yhteistyössä Pisan yliopiston professori Roberto Grossin, tohtorikoulutettava Massimo Equin ja tutkija Alexandru Tomescun kanssa.

Miten tässä näin kävi?

Tähtäimessä täsmähoidot

DNA:n tiettyjen jaksojen etsiminen on perustyökalu esimerkiksi lääkekehityksessä ja perinnöllisten sairauksien tunnistamisessa. DNA-tiedon avulla tutkijat kehittävät esimerkiksi yhä yksilöllisempiä, ihmisen perimän huomioivia syöpähoitoja.

Perinteinen tapa etsiä DNA:sta tiettyjä kohtia on hakea niitä ihmisen sekvensoidusta DNA:sta, siis yhdestä pitkästä, tietokoneelle syötetystä merkkijonosta. Siitä hakualgoritmit etsivät haluttuja pätkiä samaan tapaan kuin Google-haku haravoi internetin tekstiavaruutta. Tätä on osattu tehdä jo 1970-luvulta.

Vuosikymmeniä on tiedetty sekin, että kun merkkijonojen pituus kasvaa, haku vaikeutuu, ja tietokoneiden laskentatehon rajat tulevat nopeasti vastaan.

Genomi, josta hakuja tehdään, ei myöskään ole täysin tarkka kuva kenenkään perimästä. Se on tiedeyhteisön sopima, riittävän hyvänä pidetty keskiarvo.

– Oikeasti tämä keskiarvogenomi voi olla kaukana kunkin yksilön todellisesta perimästä. Se hukkaa paljon lääkekehitykselle tärkeää tietoa perimän vaihteluista, Mäkinen sanoo.

Tämän vuoksi perimän muutokset kiinnostavat tutkijoita, ja tämän vuoksi yritetään kehittää tarkempia hakumenetelmiä.

Variaatioverkosta uusi kokeilu

Jotta perimän vaihtelut löytyisivät paremmin, kymmenisen vuotta sitten perinteisen hakutavan rinnalle ilmestyi uusia tapoja hakea vaihteluja. Yksi niistä on laittaa hakualgoritmi etsimään DNA-tietoa niin kutsutusta variaatioverkosta.

Variaatioverkko on tiedon esittämisen tapa, joka tiivistää dataa tehokkaasti ja sopii siksi hyvin genomitiedon esittämiseen. 

Variaatioverkon toimintaperiaate näkyy tässä kuvassa:

variaatioverkko

Eri ihmisten genomit ovat erittäin samanlaisia keskenään. Miljoonien ihmisten genomeja ei ole järkeä esittää erillisinä merkkijonoina, vaan keskittyä etsimään eroja niiden väliltä. Jotta datan määrä ei räjähtäisi käsiin, kaikille yhteiset nukleotidijaksot kannattaa esittää yhtenä jonona, jollainen näkyy tässä kuvassa. Kun vastaan tulee eroja yksilöiden välillä, variaatioverkko haarautuu eri teille, ja hakualgoritmi voi löytää muutokset. Kun perimät ovat taas samanlaisia keskenään, kirjaimet palaavat takaisin kompaktiin jonoon. Kuvassa esiintyvä hakujono ”äänestää” kahta variaatiota.

Tulos: ei onnistu

Mäkisen tutkimusryhmä yritti kehittää hakualgoritmin, joka hakisi tiettyjä DNA-pätkiä tällaisesta variaatioverkosta yhtä tehokkaasti kuin perinteiset, yhdestä genomista hakevat algoritmit.

Kävi ilmi, että ei onnistu. Ilmeinen hakualgoritmi, joka hyppää jokaiseen kohtaan verkossa ja vertaa merkkejä, osoittautui parhaaksi, mitä voidaan keksiä.  Kun merkkijonojen pituus kasvaa, tällaisen haun pyörittäminen alkaa viedä niin paljon laskentatehoa, että nykylaitteilla laskutoimitukset kestäisivät satoja päiviä.

– Tarkka haku variaatoverkosta olikin yhtä vaikeaa kuin perinteinen, virheitä salliva haku yhdestä keskiarvogenomista. Meidän tuloksemme sanoo, että juuri mitään tätä parempaa hakutapaa ei ole toivoa löytää, Mäkinen kertoo.

Jos Mäkisen ryhmä olisi onnistunut parantamaan haun tulosta, se olisi ollut tietojenkäsittelytieteen alalla iso juttu. Se olisi ollut merkittävä edistysaskel alan klassikon, niin kutsutun P=NP?-ongelman, ympärillä.

Lisää valoa kollegoille

Mäkinen ei silti ole pettynyt tulokseen. Päinvastoin, nyt ollaan perustutkimuksen ytimessä.

– Perustutkimus etenee pienin askelin. Tietojenkäsittelytieteen tutkimuksessa jokin asia osoitetaan usein ensin vaikeaksi, ja sitten aletaan rajata ongelmakenttää, kuten mekin teimme. Ajan kuluessa toiset tutkijat voivat saada uusia tuloksia ja kiristää taas ruuvia ongelman ympärillä, Mäkinen sanoo.

Mäkisen mukaan nyt tutkijat maailmalla tietävät genomisen tiedonhaun reunaehdot taas vähän tarkemmin, eivätkä haparoi yhtä pimeässä kuin aiemmin. Seuraavaksi tutkijoiden kannattaisi yrittää keksiä variaatioverkoista sellaisia ominaisuuksia, jotka eivät jäisi kiinni tunnettuihin mahdottomuuksiin.

Myös Mäkisen ryhmä yhteistyökumppaneineen jatkaa tutkimusta.

– Olisihan se kivaa, jos ei tarvitsisi käydä läpi näitä välivaiheita, mutta käytännössä tutkimustyö etenee pikkuhiljaa. Kun voimme todistaa, että jokin on tai ei ole mahdollista, tulokset alkavat kertyä toistensa päälle ja aina mennään eteenpäin. Jossain on sitten se lopullinen ratkaisu.

Lue lisää:

Tutustu alkuperäiseen tutkimukseen
Genome-Scale Algorithmics -tutkimusryhmä

csm_makinen_veli

Veli Mäkinen

Tietojenkäsittelytieteen professori