Straumareiknirit fyrir heilraðgreiningu erfðamengja - verkefni lokið
Fréttatilkynning verkefnisstjóra
Í þessu verkefni voru reiknirit þróuð við smíði þjappaðra de Bruijn neta beint út frá raðgreiningargögnum á DNA. Við sýndum fram á að mögulegt er að smíða beint þjappaða útgáfu af netinu án þess að búa fyrst til óþjappað net.
Aðferðir okkar nota jafn mikið minni og keyra jafnhratt og bestu aðferðir hingað til en hafa þann kost að vera kvikar og það er auðveldara að aðlaga þær að ólíkum verkefnum, s.s. samröðun erfðamengja, samröðun umritunarmengja og breytileikaköllun. Við þróuðum einnig reiknirit til að smíða lituð de Bruijn net sem hafa verið nýtt í sam-erfðamengjafræði og tegundagreiningu. Aðferðin okkar gat smíðað net úr 117,913 Salmonella stofnum, sem er 7.3 sinnum stærra en áður hefur tekist að búa til. Stærð netsins opnar fyrir nýjar uppgötvanir í sam-erfðafræði þar sem rannsakendur geta nú greint stærri söfn en áður var hægt. Reikniritunum og útfærslu þeirra í hugbúnaði er lýst í Holley, G., Melsted, P. Bifrost – Highly parallel construction and indexing of colored and compacted de Bruijn graphs. bioRxiv 695338. Hugbúnaðurinn er aðgengilegur á https://github.com/pmelsted/bifrost/
English:
In this project we developed new algorithms for constructing compacted de Bruijn graphs directly from raw sequencing data of DNA. We showed that it is possible to construct a compressed version of the graph without constructing the full graph first. Our methods are on par with state of the art methods for de Bruijn graph construction in terms of running time and memory usage, with the added benefit of being dynamic and easily adapted to various applications such as: whole genome assembly, transcriptome assembly, and variant calling. We also developed algorithms for constructing a colored variant of the de Bruijn graph which has found numerous uses in pan-genomics and phylogenetic analysis. The method was able to construct a de Bruijn graph of 117,913 Salmonella strains, processing a 7.3 times larger dataset than previously attempted. The size of the graph enables new discoveries in pan-genome analysis as researchers are now able to query larger datasets than before. The algorithms and software are described in Holley, G., Melsted, P. Bifrost – Highly parallel construction and indexing of colored and compacted de Bruijn graphs. bioRxiv 695338. The software is freely available on https://github.com/pmelsted/bifrost/
Heiti verkefnis: Straumareiknirit
fyrir heilraðgreiningu erfðamengja / Streaming algorithms for
whole genome assembly
Verkefnisstjóri: Páll Melsted, Háskóla Íslands
Tegund styrks: Verkefnisstyrkur
Styrktímabil: 2015-2017
Fjárhæð styrks: 27,375
millj. kr. alls
Tilvísunarnúmer Rannís: 152399
