RAPSearch2: a fast and memory-efficient protein similarity search tool for next-generation sequencing data

By Yongan Zhao, Haixu Tang, Yuzhen Ye. 2011

411 citations recorded by the source corpus.

Summary: With the wide application of next-generation sequencing (NGS) techniques, fast tools for protein similarity search that scale well to large query datasets and large databases are highly desirable. In a previous work, we developed RAPSearch, an algorithm that achieved a ~20–90-fold speedup relative to BLAST while still achieving similar levels of sensitivity for short protein fragments derived from NGS data. RAPSearch, however, requires a substantial memory footprint to identify alignment seeds, due to its use of a suffix array data structure. Here we present RAPSearch2, a new memory-efficient implementation of the RAPSearch algorithm that uses a collision-free hash table to index a similarity search database. The utilization of an optimized data structure further speeds up the similarity search—another 2–3 times. We also implemented multi-threading in RAPSearch2, and the multi-thread modes achieve significant acceleration (e.g. 3.5X for 4-thread mode). RAPSearch2 requires up to 2G memory when running in single thread mode, or up to 3.5G memory when running in 4-thread mode. Availability and implementation: Implemented in C++, the source code is freely available for download at the RAPSearch2 website: http://omics.informatics.indiana.edu/mg/RAPSearch2/. Contact: yye@indiana.edu Supplementary information: Available at the RAPSearch2 website.

Subfields: Genetics, Molecular Biology

How researchers see this paper

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

In Genetics

In Molecular Biology

Citations in the corpus

Clustering huge protein sequence sets in linear time (2017, background): “At 50% identity, Linclust clusters the 123 million sequences 10 times faster than Linclust/MMseqs2 and, by extrapolation, 2300 times faster than UCLUST, 720 times faster than MMseqs, 4600 times faster than CD-HIT, 1600 times faster than DIAMOND [12], 69 000 times faster than MASH [13], and 26 000 ti”
MMseqs2: sensitive protein sequence searching for the analysis of massive data sets (2017, methodology): “The similar k -mers are generated with a linear-time branch-and-bound algorithm[3] that has been further accelerated in MMseqs2 using AVX2 vector instructions.”
Species-level functional profiling of metagenomes and metatranscriptomes (2018, positive): “We analyzed the synthetic metagenome in COGNIZER using the “-p 4” option, which defines a workflow in which RAPSearch2 17 profiles the metagenome against a reduced (non-redundant) COG sequence collection.”
A cloud-compatible bioinformatics pipeline for ultrarapid pathogen identification from next-generation sequencing of clinical samples (2014, methodology): “2011) and RAPSearch (Fig. 1D; Zhao et al. 2012), which have computational times that are orders of magnitude faster than other available algorithms.”
Structure and function of the global ocean microbiome (2015, methodology): “For modifications, we used RAPsearch2 (65) rather than BLAST to efficiently process the large data volume and a database of nonredundant protein sequences from UniProt (version: UniRef_2013_07) and eukaryotic transcriptome data not represented in UniRef.”
PHASTER: a better, faster version of the PHAST phage search tool (2016, background): “Tests with one such alternative, RAPSearch2 (15), led to a ∼ 7% loss in sensitivity (data not shown).”