Localized genome assembly from reads to scaffolds: practical traversal of the paired string graph

Rayan Chikhi 1 Dominique Lavenier 1
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Next-generation de novo short reads assemblers typically use the following strategy: (1) assemble unpaired reads using heuristics leading to contigs; (2) order contigs from paired reads information to produce scaffolds. We propose to unify these two steps by introducing localized assembly: direct construction of scaffolds from reads. To this end, the paired string graph structure is introduced, along with a formal framework for building scaffolds as paths of reads. This framework leads to the design of a novel greedy algorithm for memory-efficient, parallel assembly of paired reads. A prototype implementation of the algorithm has been developed and applied to the assembly of simulated and experimental short reads. Our experiments show that our methods yields longer scaffolds than recent assemblers, and is capable of assembling diploid genomes significantly better than other greedy methods.
Type de document :
Communication dans un congrès
Springer. WABI 2011, Sep 2011, Sarrebruck, Germany. 2011, Algorithms in Bioinformatics 11th International Workshop, WABI 2011, Saarbrücken, Germany, September 5-7, 2011. Proceedings. 〈10.1007/978-3-642-23038-7_4〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00637535
Contributeur : Rayan Chikhi <>
Soumis le : mercredi 2 novembre 2011 - 11:53:07
Dernière modification le : jeudi 11 janvier 2018 - 06:20:10
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 10:56:23

Fichier

wabi11_camera.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Rayan Chikhi, Dominique Lavenier. Localized genome assembly from reads to scaffolds: practical traversal of the paired string graph. Springer. WABI 2011, Sep 2011, Sarrebruck, Germany. 2011, Algorithms in Bioinformatics 11th International Workshop, WABI 2011, Saarbrücken, Germany, September 5-7, 2011. Proceedings. 〈10.1007/978-3-642-23038-7_4〉. 〈inria-00637535〉

Partager

Métriques

Consultations de la notice

383

Téléchargements de fichiers

156