SsahaSNP

SsahaSNP identifies single nucleotide polymorphisms (SNPs) by using the SSAHA hashing algorithm to rapidly search and align DNA sequences against large genomic databases.

Key Features:

• k-tuple hashing: Preprocesses sequences into consecutive k-tuples and stores the positions of each k-tuple in a hash table to enable rapid retrieval of matches.
• Scalability: Scales to multiple gigabases of DNA for large genomic databases.
• Speed: Operates three to four orders of magnitude faster than BLAST or FASTA for sequence search and alignment.
• Memory efficiency: Requires significantly less memory than suffix-tree approaches.
• Parameter flexibility: Allows adjustment of the tuple length k to trade off search speed, memory usage, and sensitivity.

Scientific Applications:

• SNP detection: High-throughput identification of single nucleotide polymorphisms (SNPs) in genomics research.
• Large-scale assembly: Support for very large-scale sequence assembly and comprehensive genome mapping projects.
• Genomic database integration: Indexing and search integration with genomic databases such as those used in Ensembl projects.

Methodology:

Preprocesses reference sequences into consecutive k-tuples and builds a hash table of k-tuple positions; query sequences are matched via hash-table hits to retrieve potential matches for alignment.