SSAHA: a fast search method for large DNA databases.

By Zemin Ning, Anthony J. Cox, James C. Mullikin. Genome Research, 2001

1,044 citations recorded by the source corpus.

We describe an algorithm, SSAHA (Sequence Search and Alignment by Hashing Algorithm), for performing fast searches on databases containing multiple gigabases of DNA. Sequences in the database are preprocessed by breaking them into consecutive k-tuples of k contiguous bases and then using a hash table to store the position of each occurrence of each k-tuple. Searching for a query sequence in the database is done by obtaining from the hash table the "hits" for each k-tuple in the query sequence and then performing a sort on the results. We discuss the effect of the tuple length k on the search speed, memory usage, and sensitivity of the algorithm and present the results of computational experiments which show that SSAHA can be three to four orders of magnitude faster than BLAST or FASTA, while requiring less memory than suffix tree methods. The SSAHA algorithm is used for high-throughput single nucleotide polymorphism (SNP) detection and very large scale sequence assembly. Also, it provides Web-based sequence search facilities for Ensembl projects.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/d3fd86b5e929ebd05328e5518ae693bdca153fde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants (2009, methodology): “Despite this confusion, the Sanger version of the FASTQ format has found the broadest acceptance, supported by many assembly and read mapping tools—for example SSAHA2 (18), MAQ (13), Velvet (19), BWA (14) and BowTie (20).”
A hitchhiker's guide to expressed sequence tag (EST) analysis (2006, methodology): “Another option is to use SSAHA (Sequence Search and Alignment by Hashing Algorithm) [55], a fast and efficient DNA database searching tool.”
Fast and accurate long-read alignment with Burrows–Wheeler transform (2010, background): “Most of them are very efficient for short reads but inefficient or not applicable for reads >200 bp because the algorithms are heavily and specifically tuned for short queries with low sequencing error rate.”
Next-generation DNA sequencing (2008, methodology): “Other approaches used to accelerate processing include ‘bit encoding’ to compress sequence data into a computationally more manageable and efficient format 35,36 .”
The Genome Sequence of Caenorhabditis briggsae: A Platform for Comparative Genomics (2003, methodology): “The SSAHA algorithm (Ning et al. 2001), a fast search method for PLoS Biology | http://biology.plosjournals.org Volume 1 | Issue 2 | Page 167 large DNA databases, was used to match previously finished contigs to the corresponding regions of the WGS draft.”
BLAT--the BLAST-like alignment tool. (2002, background): “The program SSAHA indexes the data-base in a manner very similar to that of , and is an extremely The challenge to indexing the database is twofold: the size of the index and the time it takes to generate the index.”
Faster and More Accurate Sequence Alignment with SNAP (2011, background): “BWA, SOAP, Bowtie and SSAHA [7, 10, 6, 13] are but a few recent examples of such tools.”
Pindel: a pattern growth approach to detect break points of large deletions and medium sized insertions from paired-end short reads (2009, background): “…the principles of the pattern growth data structure as presented in PrefixSpan, a sequential pattern mining algorithm (Pei et al., 2004), and introduced various constraints during the data mining process to mine biological meaningful patterns from unaligned protein sequences (Ye et al., 2007).”
Reconstruction of a functional human gene network, with an application for prioritizing positional candidate genes. (2006, methodology): “All features were assigned Ensembl gene identifiers by comparing their sequences to Ensembl transcripts with the use of SSAHA.”
Identification of somatically acquired rearrangements in cancer using genome-wide massively parallel paired-end sequencing (2008, methodology): “Reads in which the two ends failed to align to the genome in the correct orientation and distance apart were further screened with the SSAHA algorith”