haku: @supervisor Tarhio, Jorma / yhteensä: 69
viite: 3 / 69
| Tekijä: | Alanko, Jarno |
| Työn nimi: | Space-efficient clustering of metagenomic read sets |
| Tilatehokas metagenomisten DNA-fragmenttien ryhmittely | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2015 |
| Sivut: | 66 Kieli: eng |
| Koulu/Laitos/Osasto: | Perustieteiden korkeakoulu |
| Oppiaine: | Tietojenkäsittelytiede (IL3010) |
| Valvoja: | Tarhio, Jorma |
| Ohjaaja: | Cunial, Fabio ; Belazzougui, Djamal |
| Elektroninen julkaisu: | http://urn.fi/URN:NBN:fi:aalto-201601201068 |
| Sijainti: | P1 Ark Aalto 3448 | Arkisto |
| Avainsanat: | Burrows-Wheeler transform metagenomics clustering space-efficient Burrows-Wheeler muunnos metagenomiikka ryhmittely tilatehokas |
| Tiivistelmä (fin): | Kaikkien ympäristössä esiintyvien genomien joukkoa kutsutaan kyseisen ympäristön \emph{metagenomiksi}. Viimeisen 15 vuoden aikana kehitetyt korkean läpisyötön sekvenssoriteknologiat ovat mahdollistaneet ensimmäistä kertaa historiassa kokonaisen ympäristön metagenomin kartoittamisen. Tämä kehityssuunta on johtanut uusiin mielenkiintoisiin algoritmisiin ongelmiin. Tämä työ käsittelee ympäristöistä näytteistettyjen DNA-fragmenttejen ryhmittelyä lajien, tai yleisemmin taksonomisten yksiköiden mukaan. Työssä tunnistetaan ja formalisoidaan kaksi merkkijono-ongelmaa, jotka ilmentyvät metagenomisten DNA-fragmentteja ryhmittelyssä. Ongelmiin esitetään tilatehokkaat ratkaisut käyttäen hiljattain kehitettyä kaksisuuntaista Burrows-Wheeler indeksiä. Algoritmit toteutettiin pitäen silmällä rinnakkaista laskentaa. Työssä osoitetaan, että uusi toteutus antaa hyviä tuloksia yksinkertaisille simuloiduille näytteille, ja että työkalu on kymmenen kertaa nopeampi ja tilatehokkaampi, kuin kaksi hiljattain julkaistua metagenomisten näytteiden ryhmittelyyn tarkoitettua työkalua. |
| Tiivistelmä (eng): | The collection of all genomes in an environment is called the metagenome of the environment. In the past 15 years, high-throughput sequencing has made it feasible to sequence entire environments at once for the first time in history, which has resulted in a variety of interesting new algorithmic problems. This thesis focuses on the basic problem of clustering the reads from an environment according to which species, or more generally, taxonomic unit they originate from. In this work, we identify and formalize two fundamental string processing tasks useful in clustering metagenomic read sets. We solve the two problems with space efficiency in mind using the recently developed bidirectional Burrows-Wheeler index. The algorithms were implemented in a way which makes parallel processing possible. Our tool is experimentally shown to give good results for simple simulated datasets, and to use less than 10 times less space and time compared to two recently published metagenome clustering tools. |
| ED: | 2016-02-21 |
INSSI tietueen numero: 53122
+ lisää koriin
INSSI