Prague Stringology Conference 2012
Guillaume Holley and Pierre Peterlongo
BlastGraph: Intensive Approximate Pattern Matching in Sequence Graphs and de-Bruijn Graphs
| 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 sequence graph data structure that links reads together. This motivates our work: BLAST GRAPH, a new algorithm performing intensive approximate string matching between a set of query sequences and a sequence 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 BLAST GRAPH 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 |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |