Väitöskirjatutkija Sebastian Schmidt ja tutkijatohtori Jarno Alanko saivat parhaan tutkimusartikkelin palkinnon Workshop on Algorithms in Bioinformatics -konferenssissa (WABI). Voittavan artikkelin otsikkona on “Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time”. Schmidt on apulaisprofessori Alexandru Tomescun vetämän Graph Algorithms -tiimin jäsen.
Uuden sukupolven sekvensointi on tekniikka, jolla sekvensoidaan DNA:ta ja RNA:ta. Sitä käytettiin muun muassa SARS-CoV-2-viruksen genomin selvittämiseen vuonna 2020, mikä loi pohjan nyt käytössä oleville mRNA-rokotteille. Tekninen ratkaisu on yleisesti tutkimuskäytössä, mutta lähitulevaisuudessa se voi olla ratkaisevan tärkeää myös esimerkiksi yksilöllistetyissä syöpähoidoissa. Tällaiset tekniset ratkaisut tuottavat valtavasti dataa, jota on sekä voitava analysoida nopeasti että pakattava tallennusta ja myöhempää käyttöä varten.
Palkittu tutkimus tarjoaa tehokkaan algoritmin, jolla voidaan löytää tietyn merkkijonon (k-mer) vähimmäisesitysmuoto. Tällä on erinäisiä sovelluksia bioinformatiikassa, kuten pakkaaminen tai muiden bioinformatiikan tietorakenteiden tai data-analyysien nopeuttaminen. Ongelman uskottiin aiemmin olevan laskennallisesti vaikea, sillä tätä ennen ei tiedetty, että ongelman voi ratkaista optimaalisesti ja tehokkaasti, kuten Schmidtin ja Alangon tutkimus osoittaa.
Tutkimusryhmä esitteli tutkimuksia myös muissa ALGO-tapaamisen puitteissa järjestetyissä tapahtumissa. Yksi niistä oli ”Width Helps and Hinders Splitting Flows”, jonka olivat kirjoittaneet tohtorikoulutettavat Manuel Cáceres ja Andreas Grigorjew sekä apulaisprofessori Alexandru Tomescu yhdessä Montanan yliopiston, Veronan yliopiston ja Indian Institute of Technology Roorkee -yliopiston tutkijoiden kanssa. Tutkimus käsittelee approksimaatioalgoritmia, jonka avulla virtausverkko voidaan hajottaa painotetuiksi virtausreiteiksi. Se on tietoverkkoja, kuljetusongelmia, bioinformatiikkaa ja useita muita tietojenkäsittelytieteen aloja koskeva laskennallinen perusongelma.
Toinen artikkeli, jonka otsikkona on “Optimizing the Safe Flow Decompositions in DAGs” ja jonka kirjoittivat Graph Algorithms -tiimin alumni Shahbaz Khan (nykyään apulaisprofessorina IIT Roorkeessa Intiassa) ja apulaisprofessori Alexandru Tomescu, käsittelee samaa virtauksen hajotelman ongelmaa. He keskittyivät kuitenkin turvallisiin algoritmiversioihin eli tehokkaisiin algoritmeihin, jotka osoittavat kaikki missä tahansa virtausverkon hajotelmassa esiintyvät reitit. Ratkaisua voidaan soveltaa biologisten sekvenssien entistä tarkempaan koostamiseen. Tutkimus on osa käynnissä olevaa SAFEBIO-tutkimushanketta, jolle Euroopan tutkimusneuvosto on myöntänyt Starting Grant -apurahan. Hankkeessa kehitetään turvallisia algoritmeja alan perusongelmien ratkaisemiseksi, ja niille on sovelluksia bioinformatiikan saralla.
Uuden sukupolven sekvensointidatan analysoinnissa hyödynnetään tämän hankkeen sovelluksia. Tällaiset tekniset ratkaisut eivät kykene lukemaan kokonaista DNA-sekvenssiä alusta loppuun. Sen sijaan ne tuottavat miljoonia lyhyitä DNA-paloja. Palasten koostaminen sekvenssiksi muistuttaa valtavan palapelin kokoamista algoritmien avulla. Valtavan datamäärän takia palapelin voi kuitenkin koota useammalla kuin yhdellä tavalla; miljoonat tai jopa miljardit koosteet ovat yhtä todennäköisiä.
Tässä ERC:n rahoittamassa hankkeessa ehdotetaan epävarmuuden käsittelemiseksi uudenlaista menetelmää, jossa keskitytään tarkastelemaan vain sellaisia osittaisia koosteita, jotka ovat mukana kaikissa miljardeissa mahdollisissa koosteissa. Hanke on tuottanut käytännön työkaluja, joiden avulla biologit voivat saada selvyyttä tähän suunnattomaan epävarmuuteen.
Tietojenkäsittelytieteen laitoksen Algorithmic Bioinformatics -ryhmä koostuu viidestä tiimistä, jotka tarkastelevat bioinformatiikan ongelmia seuraavista näkökulmista: tietorakenteet, pakkaus, merkkijono- ja verkkoalgoritmit, tehokkaat toteutukset sekä käytännöllisistä ja teknisistä haasteista kumpuavat ongelmat. Tärkeimpiä sovelluksia ovat sellaisten käytännön menetelmien kehittäminen, joiden avulla biologiaan ja lääketieteeseen erikoistuneet tutkijat voivat ymmärtää elämää ja evoluutiota tai tutkia sairauksia. Vuonna 2019 perustettu Graph Algorithms -tiimi toimii ERC:n myöntämän Starting Grant -apurahan ja Suomen Akatemian Alexandru Tomesculle (vastaava tutkija) myöntämän akatemiatutkijan rahoituksen turvin.
ALGO on vuosittain järjestettävä usean algoritmikonferenssin yhteen tuova tapaaminen, jossa ovat mukana muun muassa alan keskeinen konferenssi, European Symposium on Algorithms (ESA), ja yksi algoritmisen bioinformatiikan tärkeimmistä konferensseista, Workshop on Algorithms in Bioinformatics (WABI).
Tänä vuonna kaksi Algorithmic Bioinformatics -ryhmän jäsentä toimi ALGO tapahtumassa pääpuhujina (yliopistonlehtori Leena Salmela ja apulaisprofessori Simon Puglisi), kaksi ryhmän tutkimusta julkaistiin ESA-konferenssissa, kaksi WABI-konferenssissa (joista toinen sai parhaan artikkelin palkinnon), sekä yksi ryhmän jäsen (professori Veli Mäkinen) toimi ESA-konferenssin ohjelmatoimikunnassa
Tänä vuonna Algorithmic Bioinformatics -ryhmällä oli yhteys kahteen pääpuhujaan kahteen ESA-konferenssissa esiteltyyn tutkimukseen, kahteen WABI-konferenssissa esiteltyyn tutkimukseen ja yhteen ESA:n ohjelmatoimikunnan jäseneen).