Lower and Upper Bounds for String Matching in Labelled Graphs

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-951-51-8217-3
Title: Lower and Upper Bounds for String Matching in Labelled Graphs
Alternative title: Ala- ja ylärajoja merkkijonon etsinnälle verkosta
Author: Equi, Massimo
Contributor organization: University of Helsinki, Faculty of Science
Doctoral Programme in Computer Science
Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta
Tietojenkäsittelytieteen tohtoriohjelma
Helsingfors universitet, matematisk-naturvetenskapliga fakulteten
Doktorandprogrammet i datavetenskap
Publisher: Helsingin yliopisto
Date: 2022-06-22
Language: eng
URI: http://urn.fi/URN:ISBN:978-951-51-8217-3
http://hdl.handle.net/10138/344069
Thesis level: Doctoral dissertation (article-based)
Abstract: String Matching in Labelled Graphs (SMLG) is a generalisation of the classic problem of finding a match for a string into a text. In SMLG, we are given a pattern string and a graph with node labels, and we want to find a path whose node labels match the pattern string. This problem has been studied since 1992, and it was initially intended to model the problem of finding a link in a hypertext. Recently, the problem received attention due to its applications in bioinformatics, but all of the solutions, old and new, failed to run in truly sub-quadratic time. In this work, based on four published papers, we study SMLG from different angles, first proving conditional lower bounds, and then proposing efficient algorithms for special classes of graphs. In the first paper, we unveil the reason behind the hardness of SMLG, showing a quadratic conditional lower bound based on the Orthogonal Vectors Hypothesis and the Strong Exponential Time Hypothesis. The techniques that we employ come from the fine-grained complexity, and involve finding linear-time reductions from the Orthogonal Vectors problem to different variations of SMLG. In the second paper, we strengthen our findings by showing that an indexing data structure built in polynomial time is not enough to provide subquadratic time queries for SMLG. We devise a general framework for obtaining indexing lower bounds out of regular lower bounds, and we prove the indexing lower bound for SMLG as an application of this technique. In the third paper, we surpass the limitations of our lower bounds by identifying a class of graphs, called founder block graphs, which support linear time queries after subquadratic indexing. This class of graph effectively represents collections of strings called multiple sequence alignments, if gap characters are not present. In the fourth paper, we significantly improve our previous results on efficiently indexable graphs. We propose elastic founder graphs, a superset of founder block graphs, that are able to represent multiple sequence alignments with gaps. Moreover, we propose algorithms for constructing elastic founder graph, indexing them, and perform queries in linear time.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.
Subject: computer Science
Rights: Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.


Files in this item

Total number of downloads: Loading...

Files Size Format View
equi_massimo_dissertation_2022.pdf 638.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record