SGA

SGA constructs de novo genome assemblies from high-coverage short read sequencing data using an overlap-based string graph approach.

Key Features:

• De novo assembly: Constructs large-genome assemblies from high-coverage short read sequencing data.
• String graph representation: Represents sequence relationships with string graphs rather than decomposing reads into k-mers as in de Bruijn graph methods.
• Overlap-based assembly: Builds the assembly graph from overlaps between sequencing reads.
• Time- and space-efficient algorithms: Uses algorithms optimized for time and memory to construct string graphs on large datasets.
• Transitive reduction: Implements a novel linear expected time algorithm for transitive reduction of the string graph.
• Scalability: Designed to scale to complex mammalian genomes and large whole-genome sequencing datasets.
• Relation to unitigs and BOA: Leverages unitig concepts from Celera Genomics and contributes ideas integral to the Berkeley Open Assembler (BOA).

Scientific Applications:

• Large-genome assembly: Assembly of large genomes from high-coverage short read sequencing data.
• Whole-genome sequencing projects: Handling of large datasets typical in whole-genome sequencing projects.
• Complex mammalian genomes: Assembly of complex mammalian genomes requiring scalable overlap-based methods.

Methodology:

Constructs a string graph from overlaps between sequencing reads (avoiding k-mer decomposition used in de Bruijn graph methods) and applies time- and space-efficient algorithms including a linear expected time transitive reduction.