StringGraph

StringGraph constructs string graphs for de novo genome assembly from short reads using a hash-based method that combines a modified Karp-Rabin fingerprint with Bloom filters to manage overlaps and sequence fingerprints.

Key Features:

• Hash-based string graph construction: Constructs string graphs using a hash-based approach as an alternative to de Bruijn graphs, suffix arrays, the Burrows-Wheeler transform, or the FM index.
• Incremental Karp-Rabin fingerprinting: Uses a modification of the Karp-Rabin fingerprint applied incrementally to compute sequence fingerprints.
• Bloom filter integration: Employs Bloom filters as a probabilistic data structure to store sequence fingerprints and reduce memory requirements.
• Probabilistic error behavior: Acknowledges that probabilistic hashing and Bloom filters can introduce false-positive and false-negative edges in the graph.
• Error detection and correction: Implements mechanisms to detect and correct false-positive and false-negative edges introduced by the probabilistic methods.
• Designed for short-read sequencing challenges: Targets assembly problems arising from modern sequencing technologies that produce large volumes of short reads, including long and repetitive sequences.
• Algorithmic simplicity: Implements simpler data structures and algorithmic concepts for string graph construction.
• Performance baseline: Preliminary implementations show favorable performance compared to the initial string graph construction method of Simpson and Durbin (2010) though not exceeding subsequent improvements.

Scientific Applications:

• De novo genome assembly: Applied to reconstruct genomes from short-read sequencing data without a reference genome.
• String graph-based assembler improvement: Used to explore alternative string graph construction approaches that may enhance efficiency and accuracy of string graph-based assemblers.
• Assembly of repetitive regions: Targets the assembly of long and repetitive sequences that complicate short-read assembly.
• Genomic research and bioinformatics: Applicable in genomic research workflows that require string graph construction and evaluation of probabilistic assembly methods.

Methodology:

Constructs a string graph using a hash-based method that applies an incremental modification of the Karp-Rabin fingerprint combined with Bloom filters and includes procedures to detect and correct false-positive and false-negative edges.