SSAHA swMATH ID: 17308 Software Authors: Ning Z, Cox AJ, Mullikin JC Description: SSAHA: a fast search method for large DNA databases. We describe an algorithm, SSAHA (SequenceSearch and Alignment by HashingAlgorithm), for performing fast searches on databases containing multiple gigabases of DNA. Sequences in the database are preprocessed by breaking them into consecutive k-tuples ofk 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 SSAHAalgorithm 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. Homepage: http://www.sanger.ac.uk/science/tools/ssaha Related Software: Soap; BLAT; BLAST; PSI-BLAST; KEGG; SHRiMP; DIALIGN; PatternHunter; BLASTZ; MUMMER; AVID; SAGA; Flamingo; Galaxy; ROAST; featureCounts; Rsubread; recount; PROPER; GenomeGraphs Cited in: 3 Publications all top 5 Cited by 9 Authors 1 Athitsos, Vassilis 1 Cho, Hwan-Gue 1 Choi, Jeong-Hyeon 1 Das, Gautam Kumar 1 Davis, Sean L. 1 Kotsifakos, Alexios 1 Mathé, Ewy 1 Papapetrou, Panagiotis 1 Stefan, Alexandra Cited in 3 Serials 1 Data Mining and Knowledge Discovery 1 Computational Biology and Chemistry 1 Methods in Molecular Biology Cited in 3 Fields 3 Biology and other natural sciences (92-XX) 1 Statistics (62-XX) 1 Computer science (68-XX) Citations by Year