M.Sc. Massimo Equi väittelee keskiviikkona 22.6.2022 klo 13 Helsingin yliopiston Chemicum-rakennuksen auditoriossa A129 (A. I. Virtasen aukio 1, 1. kerros) aiheesta Lower and Upper Bounds for String Matching in Labelled Graphs. Vastaväittäjänä toimii apulaisprofessori Nicola Prezza (Università Ca' Foscari Venezia, Italia) ja kustoksena professori Veli Mäkinen (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi. Väitöstilaisuutta voi seurata suorana verkkolähetyksenä osoitteessa https://video.helsinki.fi/unitube/live-stream.html?room=l42.
Massimo Equin väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Genome-Scale Algorithmics -tiimissä tehtävää tutkimusta. Väitöskirjatyön ohjaajina ovat toimineet professori Veli Mäkinen ja apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto).
Ala- ja ylärajoja merkkijonon etsinnälle verkosta
Merkkijonon etsintä verkosta (engl. String Matching in Labelled Graphs, SMLG) on yleistys klassiselle ongelmalle etsiä merkkijonohahmon osumaa tekstistä. SMLG-ongelmassa syötteenä ovat merkkijonohahmo ja verkko, jonka solmuilla on merkkijonotunnisteet. Tavoitteena on löytää polku, jonka solmujen tunnisteet muodostavat tekstin, joka sisältää annetun merkkijonohahmon. Ongelmaa on tutkittu vuodesta 1992 alun alkaen mallintamaan linkkien etsintää hypertekstistä. Viime aikoina ongelma on tullut uudestaan esille bioinformatiikan saralla. Sekä vanhat että uudet ratkaisut eivät ole onnistuneet oleellisesti murtamaan neliöllistä aikavaativuutta ongelman ratkaisussa.
Tässä työssä SMLG ongelmaa tarkastellaan eri näkökulmista perustuen neljään julkaisuun. Ensin todistetaan ehdollinen alaraja ongelman vaativuudelle. Sitten esitetään tehokkaita ratkaisuja erilaisille verkkojen aliluokille.
Ensimmäisessä julkaisussa paljastamme syyn SMLG-ongelman vaikeudelle johtamalla ehdollisen alarajan perustuen kohtisuorien vektorien hypoteesiin (engl. Orthogonal Vectors Hypothesis) ja vahvaan eksponentiaalisen aikavaativuuden hypoteesiin (engl. Strong Exponential Time Hypothesis). Tähän tulokseen käytämme hienorakenteisen vaativuusteorian (engl. fine-grained complexity) tekniikoita, kuten lineaariaikaista reduktiota kohtisuorien vektoreiden ongelmasta kohdeongelmaan, tässä tapauksessa eri variaatioille SMLG-ongelmasta.
Toisessa julkaisussa vahvistamme edellistä tulosta osoittamalla, että polynomiaikainen verkon indeksointi ei riitä tukemaan alle neliöaikaista merkkijonohahmon etsintää. Kehitämme yleisen kehikon tämän kaltaisten indeksointialarajojen johtamiseen tavallisista alarajoista, ja todistamme SMLG-ongelman alarajan sovellutuksena tästä tekniikasta.
Kolmannessa julkaisussa ohitamme alarajat identifioimalla verkkojen aliluokan, kantasegmentteihin perustuvat verkot (engl. founder block graphs), joilla indeksointi onnistuu alle neliöllisessä ajassa, jonka jälkeen merkkijonohahmon etsintää voidaan suorittaa lineaarisessa ajassa. Kantasegmentteihin perustuvilla verkoilla voidaan esittää merkkijonokokoelmien monilinjaukset, mikäli linjauksessa ei tarvita poistoja ja lisäyksiä.
Neljännessä julkaisussa parannamme merkittävästi aiempia tuloksiamme indeksoitavista verkoista. Laajennamme kantasegmentteihin perustuvat verkot elastisuuden käsitteellä, jolloin ne voivat esittää mielivaltaisia monilinjauksia, joissa linjauksessa sallitaan poistot ja lisäykset. Tämän lisäksi johdamme algoritmeja näiden elastisten kantasegmentteihin perustuvien verkkojen muodostamiseen, indeksointiin sekä merkkijonohahmojen etsintään.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-8217-3.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: massimo.equi@helsinki.fi.