SSAHA2

SSAHA2 performs fast pairwise sequence alignment and maps high-throughput sequencing reads onto genomic reference sequences for rapid large-scale genomic analyses.

Key Features:

• Hash-based preprocessing: Database sequences are decomposed into consecutive k-tuples of contiguous bases and stored in a hash table mapping each occurrence's position.
• Rapid retrieval of hits: The hash table enables quick retrieval of potential matches for query sequences to accelerate alignment searches.
• Tuple length parameterization: Choice of tuple length (k) influences search speed, memory usage, and sensitivity.
• High speed: Reported performance achieves speeds three to four orders of magnitude faster than BLAST or FASTA for comparable searches.
• Memory efficiency: Achieves rapid searches without the high memory demands typically associated with suffix tree methods, enabling use on multi-gigabase DNA databases.
• Applicability to variant and assembly analyses: Suited for high-throughput single nucleotide polymorphism (SNP) detection and very large-scale sequence assembly.

Scientific Applications:

• High-throughput sequencing read mapping: Mapping of HTS reads onto genomic reference sequences for downstream analyses.
• SNP detection: Rapid alignment enables high-throughput single nucleotide polymorphism discovery workflows.
• Large-scale sequence assembly: Application to very large-scale assembly tasks requiring fast pairwise alignments.
• Integration into genomic projects: Use in large genomic resources and projects, including those conducted by the Ensembl consortium.

Methodology:

SSAHA2 breaks database sequences into contiguous k-tuples, stores k-tuples in a hash table mapping positions, retrieves potential matches for queries via the hash to find hits, and relies on the chosen tuple length (k) to balance speed, memory, and sensitivity.