String Searching Methods for Bioinformatics

Julkaisun otsikon käännös: Merkkijonohaun Menetelmät Bioinformatiikassa

Kalle Karhu

    Tutkimustuotos: Doctoral ThesisCollection of Articles

    Abstrakti

    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.
    Julkaisun otsikon käännösMerkkijonohaun Menetelmät Bioinformatiikassa
    AlkuperäiskieliEnglanti
    PätevyysTohtorintutkinto
    Myöntävä instituutio
    • Aalto-yliopisto
    Valvoja/neuvonantaja
    • Tarhio, Jorma, Vastuuprofessori
    • Tarhio, Jorma, Ohjaaja
    Kustantaja
    Painoksen ISBN978-952-60-5298-4
    Sähköinen ISBN978-952-60-5299-1
    TilaJulkaistu - 2013
    OKM-julkaisutyyppiG5 Tohtorinväitöskirja (artikkeli)

    Tutkimusalat

    • sekvenssien rinnastus
    • usean hahmon indeksoitu haku
    • motifien tunnistus

    Sormenjälki

    Sukella tutkimusaiheisiin 'Merkkijonohaun Menetelmät Bioinformatiikassa'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä