Laurea Magistrale Nicola Rizzo puollustaa väitöskirjaansa "Indexable Sequence Graphs: Exploiting Uniqueness in the Pangenome Era" perjantaina 27.6.2025 klo 12 Helsingin yliopiston Chemicum-rakennuksen salissa A110 (A. I. Virtasen aukio 1, 1. krs). Vastaväittäjänä toimii professori Marinella Sciortino (Università degli Studi di Palermo, Italia) ja kustoksena professori Veli Mäkinen (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Nicola Rizzon väitöskirjatyö on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Genome-scale Algorithms -tiimissä tehtävää tutkimusta. Väitöskirjatyön ohjaajana on toiminut professori Veli Mäkinen (Helsingin yliopisto).
Indeksoitavat kantaverkot: ainutkertaisuuden hyödyntäminen pangenomiikan aikakaudella
Sekvenssien ja verkkojen linjaus (samankaltaisempien osien löytäminen) on aktiivinen tutkimusalue bioinformatiikassa, joka on saanut motivaationsa pangenomiikan referenssigenomien yleistymisestä ja niihin liittyvien ongelmien laskennallisesta vaikeudesta. Verkkopohjaiset pangenomit ovatkin suosittu työkalu genomikokoelmien esittämiseen, koska verkon polut voivat helposti ja kompaktisti sisällyttää monimuotoisuutta. Tiettyä uutta sekvenssiä eniten muistuttavan polun löytäminen on perustavanlaatuinen tehtävä. Sekvenssien linjaaminen vie neliöllisen ajan sekä tässä että klassisessa sekvenssien välisessä asetelmassa, mikäli tunnetut hienojakoiset kompleksisuushypoteesit pitävät paikkansa. Tarkka hahmonsovitus kahden sekvenssin välillä (täsmälleen samojen osien etsintä) taasen voidaan ratkaista lineaarisessa ajassa, mutta kun korvaamme yhden sekvenssin verkolla, tarkkakin hahmonsovitus vaatii neliöllisen ajan. Tämä laskennallinen vaativuus rajoittaa myös sekvenssien ja verkkojen linjauksessa laajalti käytössä olevia heuristisia menetelmiä, kuten ankkuroi-ja-jatka ja ankkuroi-ketjuta-ja-jatka, koska molemmissa ensimmäinen vaihe perustuu tarkkaan hahmonsovitukseen.
Indeksoitavat elastiset kantaverkot toimivat viitekehyksenä verkkojen konstruoimiseksi joukosta linjattuja sekvenssejä. Lähestymistavassa verkko, joka on indeksoitavissa polynomiajassa lineaarisen ajan tarkan hahmonsovituksen osalta, hyödyntää syötteen ainutlaatuisuutta niin, että jokainen solmun tunniste edustaa ainutlaatuista sijaintia. Tapausta, jossa sekvenssien linjauksessa ei sallita aukkoja, on tutkittu laajasti. Tämä väitöskirja, joka perustuu kolmeen julkaistuun artikkeliin ja hyväksyttyyn konferenssijulkaisuun, laajentaa elastisten kantaverkkojen viitekehystä kehittämällä lineaariaikaisia konstruointialgoritmeja, uuden hahmonsovitusindeksin ja joukon käytännön työkaluja indeksoitaville elastisille kantaverkoille, jotka on rakennettu linjatuista sekvensseistä, joissa on aukkoja.
Ensimmäisessä artikkelissa täydennämme olemassa olevaa elastisten kantaverkkojen teoreettista viitekehystä kehittämällä lineaariaikaisia konstruointialgoritmeja, jotka optimoivat eri mittareita, ja parantamalla hahmonsovitusindeksin aikaa ja tilaa. Toisessa artikkelissa laajennamme maksimaalisia tarkkoja osumia – tärkeää käsitettä, jolla on yhteydet klassisiin linjausmetriikkoihin – sekvenssien ja verkkojen väliseen linjaukseen. Tämä laajennos johtaa tehokkaaseen algoritmiin tarkoille osumille, jotka kattavat enintään vakiomäärän solmuja, ja yleisen ratkaisun indeksoitaville elastisille kantaverkoille. Kolmannessa artikkelissa kehitämme tehokkaan sekvenssi-verkko-ketjutusalgoritmin, joka maksimoi keskinäisen peiton. Tämä metriikka on yhteydessä sekvenssien linjauksen klassiseen pisimmän yhteisen alijonon käsitteeseen. Algoritmin aikavaativuus on parametrisoitu verkon leveydellä (minimimäärällä polkuja, jotka peittävät kaikki solmut). Neljännessä artikkelissa kehitämme erittäin tarkan ja käytännöllisen prosessin ankkuriketjun pidentämiseen perustuvaa linjausta varten indeksoitavien elastisten kantaverkkojen avulla: konstruktiossa huomioimme käytännön näkökohtia puuttuvien genomin osien, pitkien aukkojen, suurten genomikokoelmien ja lineaarisen referenssin variaatioiden käsittelemiseksi; toteutamme tehokkaan ankkurointimenetelmän, joka perustuu tarkkaan hahmonsovitukseen; laajennamme ketjutusratkaisuja sekvenssi-verkko-tapaukseen, jossa verkko on elastisen kantaverkko variantti; ja integroimme alalla laajalti käytetyn työkalun viimeiseen laajennusvaiheeseen.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio tulee olemaan saatavilla Helsingin yliopiston avoimessa julkaisuarkistossa Heldassa osoitteessa http://urn.fi/URN:ISBN:978-952-84-1345-5.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: nicola.rizzo@helsinki.fi