| Přispěvatelé: |
University of Helsinki, Faculty of Science, Tietojenkäsittelytiede, Doctoral Programme in Computer Science, Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen tohtoriohjelma, Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, Doktorandprogrammet i datavetenskap, Thankachan, Sharma, Mäkinen, Veli |
| Popis: |
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. 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. |
