DGraph: Algorithms for Shortgun Reads Assembly Using De Bruijn Graph

Abstract : Massively parallel DNA sequencing platforms have become widely available, reducing the cost of DNA sequencing by over two orders of magnitude, and democratizing the field by putting the sequencing capacity of a major genome center in the hands of individual investigators. New challenges include the development of robust protocols for generating sequencing libraries, building effective new approaches to resequence and data-analysis. In this paper we demonstrate a new sequencing algorithm, named DGraph, which has two modules, one module is responsible to construct De Bruijn graph by cutting reads into k-mers, and the other’s duty is to simplify this graph and collect all long contigs. The authors didn’t adapt the sequence graph reductions operations proposed by RAMANA M.IDURY or Finding Eulerian Superpaths proved by Pavel A.Pevzner or bubble remove steps suggested by Danial Zerbino, As the first operations was computing expensive, and the second one was impractical, and the last one did not benefit either the quality of contigs or the efficiency of the assembler. Our assembler was focused only on efficient and effective error removal and path reduction operations. Applying DGraph to the simulation data of fruit fly Drosophila melanogaster chromosome X, DGraph (3min) is about six times faster than velvet 0.3 (19 mins), and its coverage (92.5%) is also better than velvet (78.2%) when k = 21. Compare to velvet, the results shows that the algorithm of DGraph is a faster program with high quality results.
Type de document :
Communication dans un congrès
James J. Park; Albert Zomaya; Sang-Soo Yeo; Sartaj Sahni. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. Springer, Lecture Notes in Computer Science, LNCS-7513, pp.14-21, 2012, Network and Parallel Computing. 〈10.1007/978-3-642-35606-3_2〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01551353
Contributeur : Hal Ifip <>
Soumis le : vendredi 30 juin 2017 - 10:36:03
Dernière modification le : vendredi 1 décembre 2017 - 01:09:57
Document(s) archivé(s) le : lundi 22 janvier 2018 - 20:11:44

Fichier

978-3-642-35606-3_2_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jintao Meng, Jianrui Yuan, Jiefeng Cheng, Yanjie Wei, Shengzhong Feng. DGraph: Algorithms for Shortgun Reads Assembly Using De Bruijn Graph. James J. Park; Albert Zomaya; Sang-Soo Yeo; Sartaj Sahni. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. Springer, Lecture Notes in Computer Science, LNCS-7513, pp.14-21, 2012, Network and Parallel Computing. 〈10.1007/978-3-642-35606-3_2〉. 〈hal-01551353〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

23