BlastGraph: intensive approximate pattern matching in string graphs and de-Bruijn graphs

Guillaume Holley 1 Pierre Peterlongo 1
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE, Inria Rennes – Bretagne Atlantique
Abstract : Abstract. Many de novo assembly tools have been created these last few years to assemble short reads generated by high throughput sequencing platforms. The core of almost all these assemblers is a string graph data structure that links reads together. This motivates our work: BlastGraph, a new algorithm performing intensive approximate string matching between a set of query sequences and a string graph. Our approach is similar to blast-like algorithms and additionally presents specificity due to the matching on the graph data structure. Our results show that BlastGraph performances permit its usage on large graphs in reasonable time. We propose a Cytoscape plug-in for visualizing results as well as a command line program. These programs are available at http://alcovna.genouest.org/blastree/.
Type de document :
Communication dans un congrès
PSC 2012, Aug 2012, Prague, Czech Republic. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00711911
Contributeur : Pierre Peterlongo <>
Soumis le : mardi 26 juin 2012 - 09:57:01
Dernière modification le : mercredi 16 mai 2018 - 11:23:35
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 02:30:56

Fichier

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

Identifiants

  • HAL Id : hal-00711911, version 1

Citation

Guillaume Holley, Pierre Peterlongo. BlastGraph: intensive approximate pattern matching in string graphs and de-Bruijn graphs. PSC 2012, Aug 2012, Prague, Czech Republic. 2012. 〈hal-00711911〉

Partager

Métriques

Consultations de la notice

597

Téléchargements de fichiers

309