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/.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00711911
Contributor : Pierre Peterlongo <>
Submitted on : Tuesday, June 26, 2012 - 9:57:01 AM
Last modification on : Thursday, February 7, 2019 - 2:43:27 PM
Long-term archiving on : Thursday, September 27, 2012 - 2:30:56 AM

File

blast_graph_reviewed.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00711911⟩

Share

Metrics

Record views

714

Files downloads

383