Readjoiner: a fast and memory efficient string graph-based sequence assembler.

ABSTRACT:

Background

Ongoing improvements in throughput of the next-generation sequencing technologies challenge the current generation of de novo sequence assemblers. Most recent sequence assemblers are based on the construction of a de Bruijn graph. An alternative framework of growing interest is the assembly string graph, not necessitating a division of the reads into k-mers, but requiring fast algorithms for the computation of suffix-prefix matches among all pairs of reads.

Results

Here we present efficient methods for the construction of a string graph from a set of sequencing reads. Our approach employs suffix sorting and scanning methods to compute suffix-prefix matches. Transitive edges are recognized and eliminated early in the process and the graph is efficiently constructed

SUBMITTER: Gonnella G 

PROVIDER: S-EPMC3507659 | biostudies-literature | 2012 May

REPOSITORIES: biostudies-literature