Mihin algoritmeja tarvitaan?

Algoritmi on tietojenkäsittelytieteen keskeinen käsite. Algoritmeja tarvitaan, jotta tietokoneita osattaisiin ohjelmoida. Kukin algoritmi määrittelee äärellisistä ja täsmällisistä laskenta-askelista muodostuvan kokonaisuuden, joka tuottaa annetuista syöttötiedoista halutun tuloksen. Tietokoneohjelmat ovat abstraktien algoritmien konkreettisia toteutuksia, joita tietokone pystyy suorittamaan erilaisten tehtävien ratkaisemiseksi.

Algoritmien tutkimuksella on kaksi päätavoitetta. Toisaalta kehitetään yhä parempia algoritmeja yhä uusille laskentaongelmille. Tämä työ on usein hyvin sovellushakuista ja käytännöllistä. Toisaalta pyritään ymmärtämään algoritmien yleisiä rajoituksia ja laskentaongelmien sisäistä vaikeutta eli ns. laskennallista vaativuutta.

Tämä vastakkaisista suunnista etenevä tutkimusohjelma luo täsmällisen perustan arvioida algoritmitutkimuksen edistystä. Ongelman sisäisen vaikeuden analysointi antaa arvion siitä kuinka paljon laskentavoimaa ongelman ratkaiseminen vähintään vaatii. Ongelmalle esitetty ratkaisualgoritmi antaa puolestaan erään rajan sille, kuinka suuri laskentavoima riittää ongelmamme ratkaisemiseksi. Kun nämä kaksi arviota kohtaavat, tiedetään että käsillä on tietyssä mielessä paras mahdollinen ongelman ratkaisu.

Algoritmitutkimuksen keskeinen asema tietojenkäsittelytieteessä näkyy siitäkin, että Kansainvälisen matemaattisen unionin myöntämä Nevanlinna-palkinto on tähän mennessä aina jaettu tutkijalle, jonka työ liittyy syvällisellä tavalla algoritmiteoriaan. Arvostettu Nevanlinna-palkinto annetaan merkittävästä tietojenkäsittelytieteen matemaattisiin aspekteihin liittyvästä tutkimustyöstä.

Tarkastelen lyhyesti paria ajankohtaista algoritmitutkimuksen aluetta. Kumpikin on kiinnostava sekä algoritmiteorian että sovellusten kannalta. Toinen liittyy alkulukutestaukseen ja tietosuojaan, ja toinen bioinformatiikkaan, josta on tullut uuden molekyylibiologian kehittyessä voimakkaasti laajeneva monitieteinen tutkimusala. Bioinformatiikan menetelmät ovat laajasti edustettuina myös huippuyksikkömme tutkimusohjelmassa.

Alkulukutestaus helppoa

Eräs algoritmitutkimuksen tuore huomattava tulos on lausuttavissa lyhyesti: alkulukutestaus kuuluu joukkoon P. Tieto tästä saavutuksesta levisi vuoden 2002 kesällä, ja jopa New York Times kertoi siitä elokuussa. Mistä on kyse, kun tällainen teoreettisluonteinen tulos pystyi poikkeuksellisesti ylittämään uutiskynnykset?

Intian teknologisen instituutin tutkijat Manindra Agarwal, Neeraj Kayal ja Nitin Saxena onnistuivat löytämään algoritmin, joka testaa onko mielivaltainen annettu kokonaisluku alkuluku ts. sellainen luku, että jos se yritetään jakaa jollakin sitä pienemmällä kokonaisluvulla, jako ei mene tasan (paitsi jos jakajana on 1). Tämä keksijöidensä nimien perusteella AKS-algoritmiksi nimetty algoritmi on lisäksi sellainen - ja tämä on tuloksen uusi tärkeä ominaisuus - että sen toiminta-aika kasvaa syötteenä saadun luvun pituuden kasvaessa varsin kohtuullisesti, nimittäin kuten eräs pituuden potenssi.

Ollaksemme täsmällisiä, AKS-algoritmi vaatii laskenta-ajan joka on verrannollinen pituuden potenssiin 12, mikä tosin on algoritmin käytännön soveltamisen kannalta kiusallisen korkea asteluku. Teknisemmin ilmaistuna sanotaan, että tällaisen algoritmin aikavaatimus on polynominen syötteen pituuden suhteen. Edellä mainittu joukko P koostuu laskentaongelmista, joilla on tällainen polynomisessa ajassa toimiva ratkaisualgoritmi. Intialaisten tulos lopetti pitkään jatkuneen epätietoisuuden alkulukutestauksen vaikeudesta: se on kuin onkin joukon P jäsen.

Miksi sitten joukon P jäsenyys on arvokasta? Eikö riitä että ongelmalla on ylipäänsä jokin ratkaisualgoritmi, jolloin algoritmi voidaan ohjelmoida tietokoneelle ja sitten pannaan kone vain töihin? Asia ei ole näin yksinkertainen. Jos halutaan, että tietokone saa tulokset valmiiksi säällisessä ajassa, algoritmin pitää olla riittävän nopea.

Alkulukutestaus tarjoaa tästä asiasta valaisevan esimerkin. Välittömästi nimittäin huomataan, että alkulukutestaus onkin aivan helppo ratkaista: annetun luvun n alkulukuominaisuuden testaamiseksi kokeillaan vuoronperään kaikilla lukua n pienemmillä kokonaisluvuilla luvusta 2 alkaen, jakavatko ne tasan luvun n. Tasan jakaminen selviää tunnetulla menetelmällä, ja jos tasan menevä jako löytyy, n ei ole alkuluku, mutta muuten on.

Tämä algoritmi on kuitenkin hitautensa takia täysin käyttökelvoton. Jos luvussa n on vaikkapa 300 numeroa (näin pitkiä kokonaislukuja käytetään nykyaikaisissa tiedonsuojausmenetelmissä), on helppo arvioida että algoritmimme tarvitsema jakolaskujen määrä on suuruudeltaan niin supertähtitieteellinen ettei mikään nykyisten tietokoneiden kyvyillä varustettu laskentalaite (tai rakennettavissa oleva rinnakkaisten laskentalaitteiden kokoelma) pysty saamaan tulosta valmiiksi siedettävässä ajassa, ei vaikka koneiden nopeus tunnetun Mooren lain mukaisesti kasvaisi rajustikin. Tarvitaaan parempi algoritmi.

Luokkaa P voidaan myös luonnehtia niin, että se on 'käytännössä' algoritmeilla ratkeavien ongelmien luokka. Kokemusperäisesti on nimittäin havaittu että polynomisessa ajassa toimiva algoritmi on yleensä käyttökelpoisen nopea. Jos toisaalta aikavaatimus kasvaa nopeammin kuin mikään polynomi, ei algoritmi voi olla yleisesti käyttökelpoinen. Polynomisissa algoritmeissa on myös teoreettista viehätystä: niiden edellytyksenä yleensä on, että ongelman sisäisestä kombinatorisesta rakenteesta on paljastunut vahvaa säännönmukaisuutta, joka avulla ratkaisu löytyy 'suoraan' ilman että on tarpeen turvautua edellä mainittuun hitaaseen yrityksen ja erehdyksen menetelmään.

Alkulukutestauksen saaminen luokkaan P onkin huomattava saavutus, onhan alkulukuominaisuus klassinen matemaattinen käsite jonka tutkimuksella on vuosituhantinen perinne. Kiinalaisilla oli jo noin 10. vuosisadalla ennen ajanlaskumme alkua (virheelliseksi osoittautunut) ehdotus alkulukutestausalgoritmiksi ja (oikein toimiva) ns. Eratosteneen seula on noin vuodelta 240 ennen ajanlaskun alkua.

Lisäksi tunnetaan useita uudempia alkulukutestejä, joiden tehokkuus on jonkun lisäoletuksen (kuten laajennetun Riemannin hypoteesin) varassa tai jotka eivät ole deterministisiä vaan käyttävät apuna lantinheittoa. Tällaiset testit ovat jo laajassa käytössä eikä ole selvää, että uusi deterministinen AKS-algoritmi on käytännössä näitä parempi. Deterministinen algoritmi on kuitenkin ratkaissut ongelman sisäistä vaikeutta koskevan pitkäaikaisen avoimen kysymyksen. Mahdollisesti algoritmia pystytään vielä parantamaan paljonkin, nyt kun pää on saatu auki.

Tekijöihin jako vaikeaa

Alkulukutestaus on klassista lukuteoriaa ja sellaisenaan kiehtova ongelma, jonka ratkaisulla voi olla odottamattomiakin seurauksia. Vielä kiinnostavampi on sen lähisukuinen ongelma, nimittäin annetun luvun jakaminen tekijöihinsä. Nyt tehtävänä on selvittää, mitkä ovat annetun kokonaisluvun tekijät ts. luvut, joiden tulo annettu luku on.

Toistaiseksi ei tunneta nopeaa tekijöihinjakoalgoritmia. Toisaalta käänteinen tehtävä, luvun määrittäminen kun sen tekijät on annettu, on ilmeisen nopeasti laskettavissa. Tekijöihin jako onkin lupaava ehdokas niin sanotuksi yksisuuntaiseksi funktioksi. Tällaisen funktion laskeminen on nopeaa toiseen suuntaan mutta hidasta toiseen.

Yksisuuntaisia funktioita tarvitaan nykyaikaisissa julkisen avaimen salakirjoitukseen perustuvissa tiedonsuojausmenetelmissä. Näiden menetelmien turvallisuus on yksisuuntaisuusoletuksen varassa. Paljon käytetty Rivest-Shamir-Adleman salakirjoitusmenetelmä käyttää tekijöihin jakoa yksisuuntaisena funktiona. Sen turvallisuus perustuu siis oletukseen, että tekijöihinjako on hidasta. Nopean tekijöihinjakoalgoritmin löytyminen murtaisi samalla tämän salakirjoitusmenetelmän.

Tätä kirjoitettaessa ei ole tiedossa mitään siihen viittaavaa, että uuden AKS-alkulukutestin seurauksena myös tekijöihin jakaminen ratkeasi nopeammin. Uusi testi ei näytä antavan viitteitä testattavan luvun tekijöiden arvoista; se ainoastaan sanoo onko tekijoitä olemassa. Tilanne saattaa muuttua, jos ns. kvanttitietokone onnistutaan joskus rakentamaan. Tällainen kone tarjoaisi uudentyyppisiä laskentaoperaatioita, joilla on mahdollista suorittaa tiettyjä tehtäviä oleellisesti nopeammin kuin nykyisillä tietokoneilla. Nevanlinna-palkittu Peter Schorr osoitti jo lähes 10 vuotta sitten, että kvanttitietokoneella mahdollisia operaatioita käyttäen voidaan tekijöihin jakaminen suorittaa nopeasti. Kvanttitietokoneen tultua jouduttaisiinkin salakirjoitusmenetelmät miettimään uudestaan.

Merkkijonoalgoritmit ja bioinformatiikka

Toinen algoritmitutkimuksen ajankohtainen ongelmien lähde ja sovellusalue on molekyylibiologia. Lähtökohtana on DNA-molekyylin sisältämän perinnöllisen informaation koodaustapa. DNA-molekyylin oleellinen sisältö voidaan kuvata neljää erilaista merkkiä sisältävänä sekvenssinä eli yksinkertaisena merkkijonona. Kun tietokoneet käyttävät kaksiarvoisia bittejä, on luonto omaksunut neliarvoiset 'kvatit' DNA:n sisältämän perinnöllisen informaation koodaamiseen.

Useiden organismien DNA:n merkkijonot on jo selvitetty (eli sekvensoitu) ja useita on valmistumisvaiheessa. Näin kertyy valtavasti mielenkiintoista merkkijonomuotoista dataa. Tämän datan käsittely ja analyysi on tehtävä, jossa tietojenkäsittelytieteen piirissä pitkään jatkuneella merkkijonomenetelmien ja muiden kombinatoristen algoritmien tutkimuksella on paljon annettavaa, koska kyseessä on luonteeltaan diskreeteistä symboleista (eikä enemmän tai vähemmän epätarkoista luvuista) koostuva data.

Uuden molekyylibiologisen datan analyysitarpeet ovat synnyttäneet uuden tutkimusalan, bioinformatiikan. Sillä tarkoitetaan biologisen informaation ja biologisten systeemien rakenteen analyysiä ja mallittamista tietojenkäsittelytieteen, tilastotieteen ja matematiikan tarjoamien välineiden avulla. Bioinformatiikasta on tullut bioteknisen tutkimuksen ja teollisuuden eräs keskeinen tekijä, jonka osaajista on maailmanlaajuinen pula.

DNA-palapeli

DNA-jonojen kokoaminen lyhyemmistä palasista on eräs välttämätön laskentatehtävä, joka pitää ratkaista kaikissa genomien sekvensointihankkeissa. Ongelma syntyy siitä, että DNA:n rakennetta osataan lukea laboratoriossa sekvensointilaitteita käyttäen vain suhteellisen lyhyissä palasissa. Näiden palasten pituus on tyypillisesti 150 - 800 merkkiä. Paloista pitäisi koota koko genomia esittävä oikeassa järjestyksessä oleva yhtenäinen merkkijono, jonka pituus on kenties miljoonia tai miljardeja merkkejä.

Palojen oikea sijainti ja kulkusuunta lopullisessa jonossa ei ole etukäteen tarkalleen tiedossa vaan ne voivat olla enemmän tai vähemmän 'haulikolla ammuttuja'. Lisäksi paloissa voi olla pieni määrä eri syistä johtuvia virheitä (puuttuvia, muuttuneita tai lisättyjä merkkejä).

DNA-jonon palasista muodostuu tällä tavoin varsin ainutlaationen, valtaisa palapeli. Esimerkiksi ihmisen genomin kokoamista varten näitä paloja on tuotettu lähes 30 miljoonaa ja palapelin lopputuloksena pitäisi muodostua noin 3 miljardia merkkiä pitkä jono. Palapelin ratkaiseminen on hieno algoritmitutkimuksen ongelma, joka on algoritmiteoreettisesti haastava ja jolla on relevanttia käyttöä.

Ratkaisu lähtee liikkeelle siitä, että joidenkin palasten tiedetään olevan osittain päällekkäin alkuperäisessä jonossa. Sekvensointi on tätä varten tarkoituksellisesti tehty niin, että palaset peittävät saman alueen moneen kertaan. Silloin palasten alkuperäisestä järjestyksestä saadaan vihiä etsimällä pareja, joilla on samanlainen alku- ja loppuosa ja jotka näinollen voisivat olla alkuperäisessä jonossa osittain päällekkäin.

Näin muodostuu palaparien keskinäistä järjestystä koskevia paikallisia ehdotuksia. Näiden perusteella voidaan seuraavaksi muodostaa ehdotuksia yhä laajempien palajoukkojen keskinäiseksi asetelmaksi. Tehtävää vaikeuttaa se, että usein on tarjolla useita erilaisia lupaavia asetelmavaihtoehtoja. Tämä voi johtua siitä, että paloja on sekvensoitu liian vähän tai paloissa on virheitä. Suurin vaikeus on kuitenkin se, että DNA-jonot voivat sisältää useaan kertaan toistuvia pitkiä jaksoja, mikä voi sotkea palapelin sallimalla useita ratkaisuja.

Kuvattu palapeli johtaa useisiin algoritmisiin osatehtäviin. Tarvitaan esimerkiksi merkkijonomenetelmiä palaparien likimääräisten päällekkäisyyksien hakemiseen ja erilaisia verkkoteorian algoritmeja palapelin kokonaisratkaisun muodostamiseen. Jos ratkaisu muotoillaan kombinatoriseksi optimointiprobleemaksi, se osoittautuu tunnetun kauppamatkustajan ongelman sukulaiseksi ja on luonteeltaan ns. NP-kova ongelma. Tämän ongelmaluokan tarkka ratkaiseminen on kaikilla tunnetuilla menetelmillä toivottaman hidasta, joten erilaiset likimääräisratkaisut ovat tarpeen. Jonojen toisteisuus vaatii vielä erikseen räätälöityjä menetelmiä, jotta lopputulos olisi biologisesti mahdollisimman tarkka.

Kaikki palapelin vaiheet osataan toteuttaa tehokkailla algoritmeilla, mikä datan suuresta koosta johtuen onkin välttämätöntä. Silti isot genomihankkeet tarvitsevat varsin järeän tietokonepatterin merkkijonojensa hallintaa ja analyysiä varten. Käsityökin on edelleen välttämätöntä ratkaisun viimeistelyvaiheessa.

DNA-jonojen tulkinta

DNA-jonojen kokoaminen on tietenkin vasta lähtölaukaus jonojen sisällön analysoinnille. Koottukin jono on vasta dataa joka odottaa tulkitsijaansa. Esimerkiksi varsinaisten geenien paikallistaminen DNA-jonosta laboratoriossa on työläs tehtävä, jota voidaan auttaa laatimalla tietokone-ennusteita geenien paikoista. Tämä on luonteeltaan merkkijonojen luokitteluongelma, joka on onnistuttu ratkaisemaan kohtuullisen hyvin. Uudet arviot eri organismien geenien määristä perustuvat tällaisiin ennusteisiin.

On myös havaittu että samankaltaisten jonojen biologinen merkitys on usein sama. Näin syntyy tarve verrata merkkijonoja ja löytää samankaltaisia jonoja tai jonojen alueita (ns. homologioita) tai jonoissa esiintyviä yhteisiä merkkihahmoja. Tähän tarkoitukseen on kehitetty laaja joukko merkkijonojen etäisyysmittoja ja niihin perustuvia algoritmeja ja tietokoneohjelmia, joilla verrataan jonoja toisiinsa ja etsitään annetun jonon sukulaisjonot erilaisista DNA-jonojen tietokannoista.

Tällaiset merkkijonojen vertailu- ja hakuohjelmat ovat laajassa päivittäisessä käytössä lähes kaikessa molekyylibiologisessa tutkimuksessa, ja biologeista on tullut Suomen supertietokoneiden suurin käyttäjäryhmä. Jälleen algoritmien tehokkuus on tärkeää, koska laajamittaisten sekvensointihankkeiden ansiosta tietokantojen koko kasvaa räjähdysmäisesti.

Kunkin organismin DNA voidaan ymmärtää eräänlaiseksi ohjelmaksi, jonka ohjaamana organismi kasvaa ja elää. On valtava haaste selvittää, miten tämä ohjelma toimii. Työ etenee tietenkin vähittäin. Koko genomin toiminnasta järjestelmällistä tietoa antavien mittausmenetelmien kehittäminen ja systemaattisten mittausten suorittaminen 'systeemibiologian' hengessä on tässä avainasemassa. Eräs tällainen uusi mittausmenetelmä on ns. DNA-siru. Sillä voidaan samanaikaisesti mitata organismin kaikkien - mahdollisesti kymmenien tuhansien - geenien aktiivisuutta eri olosuhteissa.

Näin saadaan tietoa DNA-ohjelman toiminnan sisäisistä tiloista, minkä perusteella pyritään muodostamaan esimerkiksi geenien välisiä säätelysuhteita kuvaavia verkostorakenteita tai jopa kokonaisen solun toimintaa kuvaavia tietokonemalleja. Tällaisten säätelyverkkojen ja mallien laskeminen mittausdatan perusteella on jälleen algoritmin kehittäjälle huomattavan kova haaste. Sen ratkaisemiseksi on intensiivinen tutkimus käynnissä eri puolilla maailmaa.

Kirjallisuutta

M. Agrawal, N. Kayal ja N. Saxena (2002): PRIMES is in P. Indian Institute of Technology, Kanpur, India, August 6 2002, (www.cse.iitk.ac.in/users/manindra/index.html).

A. Brazma, I. Jonassen, J. Vilo ja E. Ukkonen (1998): Predicting gene regulatory elements in silico on a genomic scale. Genome Research 8, 1202-1215.

D. Gusfield (1997): Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.

E. W. Myers et al. (2000): A whole-genome assembly of Drosophila. Science 287, 2196-2204.

Ylös