Learning Centre

Space-efficient clustering of metagenomic read sets

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Cunial, Fabio
dc.contributor.advisor Belazzougui, Djamal
dc.contributor.author Alanko, Jarno
dc.date.accessioned 2016-01-19T10:52:54Z
dc.date.available 2016-01-19T10:52:54Z
dc.date.issued 2016-01-18
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/19415
dc.description.abstract 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. en
dc.description.abstract 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. fi
dc.format.extent 66
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Space-efficient clustering of metagenomic read sets en
dc.title Tilatehokas metagenomisten DNA-fragmenttien ryhmittely fi
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword Burrows-Wheeler transform en
dc.subject.keyword metagenomics en
dc.subject.keyword clustering en
dc.subject.keyword space-efficient en
dc.identifier.urn URN:NBN:fi:aalto-201601201068
dc.programme.major Tietojenkäsittelytiede fi
dc.programme.mcode IL3010 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Tarhio, Jorma
dc.programme Tietotekniikan koulutusohjelma fi
local.aalto.openaccess yes
dc.rights.accesslevel openAccess
local.aalto.idinssi 53122
dc.type.publication masterThesis
dc.type.okm G2 Pro gradu, diplomityö


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