SSAHA

SSAHA indexes and aligns DNA sequences by hashing consecutive k-tuples to enable rapid matching and alignment within large genomic databases.

Key Features:

• Hash-Based Preprocessing: Divides database DNA sequences into consecutive k-tuples and indexes them in a hash table.
• Efficient Search Mechanism: Retrieves hash-table hits for each k-tuple in a query and sorts results to identify potential matches.
• Tuple-Length Optimization: The choice of tuple length (k) affects search speed, memory usage, and sensitivity.
• Performance Relative to BLAST/FASTA: Computational comparisons report SSAHA can be three to four orders of magnitude faster than BLAST or FASTA.
• Memory Efficiency Compared to Suffix Trees: Requires less memory than suffix tree–based approaches while maintaining rapid search capabilities.

Scientific Applications:

• High-Throughput SNP Detection: Enables rapid detection of single nucleotide polymorphisms (SNPs) across large datasets.
• Large-Scale Sequence Assembly: Supports assembly workflows by rapidly matching short fragments into longer contiguous sequences.
• Sequence Search Against Genome Databases (Ensembl): Applied for sequence search and matching within genome databases such as Ensembl.

Methodology:

Preprocess database sequences into consecutive k-tuples stored in a hash table; for a query, retrieve hits for each k-tuple and sort them to identify candidate alignments; selection of k controls the trade-off between speed, memory, and sensitivity.