String Searching Methods for Bioinformatics

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Tarhio, Jorma, Professor, Aalto University, Finland
dc.contributor.author Karhu, Kalle
dc.date.accessioned 2013-09-18T09:00:14Z
dc.date.available 2013-09-18T09:00:14Z
dc.date.issued 2013
dc.identifier.isbn 978-952-60-5299-1 (electronic)
dc.identifier.isbn 978-952-60-5298-4 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/10961
dc.description.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. en
dc.description.abstract 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. fi
dc.format.extent 132
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 130/2013
dc.relation.haspart [Publication 1]: Kalle Karhu, Juho Mäkinen, Jussi Rautio, Hugh Salamon and Jorma Tarhio. GAST, a genomic alignment search tool. In BIOINFORMATICS 2011 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, 82–90, 2011.
dc.relation.haspart [Publication 2]: Kalle Karhu. Improving exact search of multiple patterns from a compressed suffix array. In Proceedings of the Prague Stringology Conference, 226–231, 2011.
dc.relation.haspart [Publication 3]: Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen and Niko Välimäki. Multi-Pattern Matching with Bidirectional Indexes. Accepted for publication in Journal of Discrete Algorithms, 2013.
dc.relation.haspart [Publication 4]: Elena Czeizler, Tommi Hirvola and Kalle Karhu. A graph-theoretical approach for motif discovery in protein sequences. Submitted to BMC Bioinformatics, 2013.
dc.subject.other Computer science en
dc.title String Searching Methods for Bioinformatics en
dc.title Merkkijonohaun Menetelmät Bioinformatiikassa fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science and Engineering en
dc.subject.keyword sequence alignment en
dc.subject.keyword indexed multi-pattern matching en
dc.subject.keyword motif discovery en
dc.subject.keyword sekvenssien rinnastus fi
dc.subject.keyword usean hahmon indeksoitu haku fi
dc.subject.keyword motifien tunnistus fi
dc.identifier.urn URN:ISBN:978-952-60-5299-1
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Tarhio, Jorma, Professor, Aalto University, Finland
dc.opn Ukkonen, Esko, Professor, University of Helsinki, Finland
dc.date.dateaccepted 2013-06-20
dc.contributor.lab String Algorithms Group en
dc.contributor.lab Merkkijonoalgoritmit fi
dc.rev Lecroq, Thierry, Professor, University of Rouen, France
dc.rev Sagot, Marie-France, Dr, Université Claude Bernard, France
dc.date.defence 2013-09-20


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account