Small World Asynchronous Parallel Model for Genome Assembly

Abstract : Large de bruijn graph based algorithm is widely used in genome assembly and metagenetic assembly. The scale of this kind of graphs - in some cases billions of vertices and edges - poses challenges to genome assembly problem. In this paper, a one-step bi-directed graph is used to abstract the problem of genome assembly. After that small world asynchronous parallel model (SWAP) is proposed to handle the edge merging operation predefined in the graph. SWAP aims at making use of the locality of computing and communication to explore parallelism for graph algorithm. Based on the above graph abstraction and SWAP model, an assembler is developed, and experiment results shows that a factor of 20 times speedup is achieved when the number of processors scales from 10 to 640 when testing on processing C.elegans data.
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.145-155, 2012, Network and Parallel Computing. 〈10.1007/978-3-642-35606-3_17〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01551319
Contributeur : Hal Ifip <>
Soumis le : vendredi 30 juin 2017 - 10:35:37
Dernière modification le : vendredi 1 décembre 2017 - 01:10:01
Document(s) archivé(s) le : lundi 22 janvier 2018 - 21:16:34

Fichier

978-3-642-35606-3_17_Chapter.p...
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. Small World Asynchronous Parallel Model for Genome Assembly. 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.145-155, 2012, Network and Parallel Computing. 〈10.1007/978-3-642-35606-3_17〉. 〈hal-01551319〉

Partager

Métriques

Consultations de la notice

35

Téléchargements de fichiers

19