Unknown

Dataset Information

0

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 including irreducible edges only. CONCLUSIONS: Our suffix-prefix match determination and string graph construction algorithms have been implemented in the software package Readjoiner. Comparison with existing string graph-based assemblers shows that Readjoiner is faster and more space efficient. Readjoiner is available at http://www.zbh.uni-hamburg.de/readjoiner.

SUBMITTER: Gonnella G 

PROVIDER: S-EPMC3507659 | biostudies-literature | 2012

REPOSITORIES: biostudies-literature

altmetric image

Publications

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

Gonnella Giorgio G   Kurtz Stefan S  

BMC bioinformatics 20120506


<h4>Background</h4>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.<h4>Results</h4>Here  ...[more]

Similar Datasets

| S-EPMC3521391 | biostudies-literature
| S-EPMC3626529 | biostudies-literature
| S-EPMC4496933 | biostudies-literature
| S-EPMC7313139 | biostudies-literature
| S-EPMC4816029 | biostudies-literature
| S-EPMC8147420 | biostudies-literature
| S-EPMC6074839 | biostudies-literature
| S-EPMC6480747 | biostudies-literature
| S-EPMC3366991 | biostudies-literature
| S-EPMC6812468 | biostudies-literature