String Searching Methods for Bioinformatics

Abstract

The cost of obtaining biologically relevant data via sequencing has been declining rapidly, far surpassing the decline in computing costs. This is highlighting a need for more efficient, and thus cheaper, ways to analyze all of this data. Analyzing such data commonly requires searching through the text representing it in one way or another. The focus of this thesis is on improving the efficiency of the computational approaches that one may wish to use when searching through such texts.More precisely, it addresses three subproblems related to text searches in bioinformatics. First, we consider the approximate, indexed alignment of long sequences. We present an approach using an index that combines q-sampling and block addressing for the initial approximate location of promising alignments, which are then studied more carefully using a multi-pattern, q-gram algorithm. Based on our experimental results, this approach is able to answer alignment queries notably faster than previous approaches, using only a fraction of the memory required by them. We additionally show that the quality of alignments and even the exon mappings produced by this approach are not worse than those produced using previous approaches. Second, we consider indexed multi-pattern matching. For this subproblem, a set of multiple patterns is preprocessed, speeding up our search of this set from an index structure. This thesis presents the first experimental results on this type of an indexed, multi-pattern matching setting together with new theoretical insights. Practical approaches to this setting are presented, and our experimental results suggest that the presented approaches to preprocessing notably improve later searches from the corresponding index structures. Namely, compressed suffix arrays and bidirectional FM-indexes are considered in our study. Finally, we consider protein motif discovery. We present a new graph-theoretical approach based on de Bruijn graphs. Moreover, we show how to further improve the query times of this approach using similarity indexing. Our experiments suggest that the presented approaches produce motif predictions of equal quality notably faster than previous methods.

Biologiselta kannalta merkityksellisen datan tuottamisen kustannukset laskevat ennätyksellistä tahtia sekvensointiteknologian kehityksen myötä. Näiden kustannusten laskun nopeus ohittaa jopa laskentakustannusten laskun nopeuden. Tästä aiheutuu kasvava kysyntä, joka kohdistuu uusiin, tehokkaampiin laskennallisiin menetelmiin, joilla pystyttäisiin vastaamaan kasvavien datamäärien asettamiin haasteisiin. Tyypillisesti tällaisen datan analysointiin kuuluvat tekstihaut, muodossa tai toisessa. Tämä väitöskirja pureutuu sellaisten laskennallisten menetelmien tehokkuuden parantamiseen, joita tarvitaan, kun tällaisia tekstihakuja halutaan suorittaa. Tarkemmin, keskitymme kolmeen bioinformatiikan tekstihakujen osaongelmaan. Ensimmäisenä tarkastelemme pitkien sekvenssien indeksoitua, likimääräistä hakua. Esitämme menetelmän, joka käyttää indeksirakenteita, jossa kaksi konseptia: q-sampling ja block addressing yhdistetään. Indeksirakenteen avulla löydetyt lupaavat alueet tarkistetaan usealle q-grammille suunnitellulla algoritmilla. Kokeelliset tuloksemme osoittavat, että tämä menetelmä vaatii vain murto-osan aikaisempien menetelmien vaatimasta muistista, mutta se on kuitenkin merkittävästi aikaisempia menetelmiä nopeampi. Toiseksi, tarkastelemme usean hahmon indeksoitua hakua. Tässä osaongelmassa usean hahmon joukko esikäsitellään, tarkoituksena nopeuttaa tämän joukon myöhempää indeksoitua hakua. Tässä väitöskirjassa esitämme ensimmäiset tähän osaongelmaan liittyvät kokeelliset tulokset. Esitämme myös uusia teoreettisia huomioita tähän asetelmaan liittyen. Kokeelliset tuloksemme antavat viitteitä siitä, että esitetyt esikäsittelymenetelmät nopeuttavat hahmojoukkojen indeksoitua hakua huomattavasti. Keskitymme kahteen indeksirakenteeseen: tiivistettyyn loppuosataulukkoon ja kaksisuuntaiseen FM-indeksiin. Viimeisenä osaongelmana keskitymme motifien etsimiseen proteiinisekvensseistä. Esittelemme graafiteoriaan pohjautuvan lähestymistavan, jossa käytämme de Bruijn -graafeja. Näytämme myös, kuinka tätä lähestymistapaa voidaan edelleen nopeuttaa samankaltaisuus-indeksointia apuna käyttäen. Kokeelliset tuloksemme osoittavat, että kehitetyt menetelmät ovat tarkkuudeltaan samaa tasoa, mutta merkittävästi nopeampia kuin aikaisemmat menetelmät.