Space-Efficient Algorithms for Strings and Prefix-Sortable Graphs

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten sv
dc.contributor University of Helsinki, Faculty of Science, Tietojenkäsittelytiede en
dc.contributor Tietojenkäsittelytieteen tohtoriohjelma fi
dc.contributor Doktorandprogrammet i datavetenskap sv
dc.contributor Doctoral Programme in Computer Science en
dc.contributor.author Alanko, Jarno
dc.date.accessioned 2020-05-13T05:04:21Z
dc.date.available 2020-05-24
dc.date.available 2020-05-13T05:04:21Z
dc.date.issued 2020-06-03
dc.identifier.uri URN:ISBN:978-951-51-6168-0
dc.identifier.uri http://hdl.handle.net/10138/314808
dc.description.abstract Space-efficient data structures are an active field of research that has found many applications in combinatorial pattern matching and bioinformatics. The idea is to build data structures that occupy space close to an information-theoretic lower bound, or even less, but still support efficient query operations. In the past few decades, compact index structures have been designed for a variety of different types of data, including bit vectors, strings, trees and graphs, to name a few prominent applications. In this thesis, we design and apply compact data structures for problems related to bioinformatics, and advance the theory of Wheeler graphs, which are a class of graphs that admit a compact indexing data structure. The work is based on four published papers. In the first two papers, we propose compact solutions for two problems on strings. In Paper I, we design and implement an algorithm that computes the classical greedy approximation for the shortest common superstring problem. In Paper II, we design and implement data structures for storing a variable-order Markov model in a compact and queryable form. The last two papers of the thesis expand the theory of Wheeler graphs. In Paper III, we extend the theory into finite state automata, leading to a number of interesting algorithms for recognizing, sorting, determinizing and minimizing automata that are Wheeler graphs. We also show how to turn any acyclic automaton into the minimum equivalent Wheeler graph automaton. In Paper IV, we propose a method to compress a Wheeler graph while retaining the indexing functionality, by generalizing a recently introduced method of tunneling from the Burrows-Wheeler transform to Wheeler graphs. en
dc.description.abstract Tilatiiviit tietorakenteet ovat aktiivinen tutkimusalue, jolle on löytynyt paljon käytännön sovelluksia kombinatoristen hahmojen hakemisessa ja bioinformatiikassa. Ajatuksena on pyrkiä rakentamaan tietorakenteita, joiden käyttämä tila on lähellä informaatioteoreettista alarajaa, tai jopa sen alle, mutta kyselyt ovat silti nopeita. Viime vuosikymmenten tutkimuksen tuloksena on löytynyt suuri määrä tilatiiviitä ratkaisuja monenlaiselle rakenteille, kuten bittivektoreille, merkkijonoille, puille ja verkoille. Tässä väitöskirjassa on suunniteltu ja toteutettu kompakteja tietorakenteita bioinformatiikan ongelmiin. Tämän lisäksi työssä on laajennettu niin kutsuttujen Wheeler-verkkojen teoriaa. Tutkimustyö on julkaistu neljässä erillisessä artikkelissa. Ensimmäisessä kahdessa artikkelissa on suunniteltu uusia tietorakenteita ja algoritmeja kahteen merkkijono-ongelmaan. Artikkelissa I esitetään algoritmi, joka pyrkii ratkaisemaan klassisen lyhyimmän yhteisen ylimerkkijonon ongelman pienessä tilassa. Artikkelissa II suunnitellaan ja toteutetaan käyttövalmis ja tiivis tietorakenne vaihtuva-asteisille Markov-malleille. Wheeler-verkot ovat suunnattujen verkkojen osajoukko, jossa kaaret on nimikoitu kirjaimin, ja jolle on tunnetusti mahdollista rakentaa tilatiivis ja tehokas indeksirakenne. Kahdessa jälkimmäisessä artikkelissa on kehitetty Wheeler-verkkojen teoriaa. Artikkelissa III teoriaa on laajennettu äärellisiin automaatteihin, ja kehitetty tämän avulla uusia algoritmeja Wheeler-verkon ehdot täyttävien automaattien tunnistamiseen, järjestämiseen, determinisointiin ja minimointiin. Lisäksi artikkelissa näytetään kuinka muunnetaan mikä tahansa syklitön äärellinen automaatti vastaavaksi Wheeler-verkon ehdot täyttäväksi pienimmäksi mahdolliseksi automaatiksi. Artikkelissa IV on kehitetty teoreettinen menetelmä Wheeler-verkon pakkaamiselle siten, että sen indeksointiominaisuudet säilyvät. Tämä yleistää hiljattain kehitettyä tunnelointimenetelmää Burrows-Wheeler-muunnoksen pakkaamiseen. fi
dc.format.mimetype application/pdf
dc.language.iso en
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-951-51-6167-3
dc.relation.isformatof Unigrafia: 2020, A-2020-3. 1238-8645
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject tietojenkäsittelytiede
dc.title Space-Efficient Algorithms for Strings and Prefix-Sortable Graphs en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Doktorsavhandling (sammanläggning) sv
dc.ths Mäkinen, Veli
dc.opn Thankachan, Sharma
dc.type.dcmitype Text

Files in this item

Total number of downloads: Loading...

Files Size Format View
Space-Ef.pdf 569.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record