Scalable, Real-Time, and Information-Rich Sequence Search Over SRA

Compact, exact, and incrementally updatable indexes for searching petabyte-scale sequencing data.

The Sequence Read Archive (SRA) holds petabytes of raw sequencing data, but searching it for a given sequence has long been impractical at scale. This project builds compact, exact, and information-rich indexes that make large-scale sequence search fast and space-efficient.

We introduced Squeakr (Pandey et al., 2017) for fast and compact $k$-mer counting, and the Mantis system (Pandey et al., 2018; Almodaresi et al., 2019) for exact, large-scale sequence search. These build on succinct colored de Bruijn graph representations such as deBGR (Pandey et al., 2017) and Rainbowfish (Almodaresi et al., 2017). We made the search index incrementally updatable (Almodaresi et al., 2022), extended the approach to genomic variant search with VariantStore (Pandey et al., 2021), and most recently scaled colored compacted de Bruijn graph construction to massive datasets with Cuttlefish 3 (Khan et al., 2026).

References

2026

  1. RECOMB 2026
    Faster and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3
    Jamshed Khan, Laxman Dhulipala, Prashant Pandey, and 1 more author
    In International Conference on Research in Computational Molecular Biology 2026, 2026
    PDF Code

2022

  1. BIOINFORMATICS 2022
    An Incrementally Updatable and Scalable System for Large-Scale Sequence Search using the Bentley-Saxe Transformation
    Fatemeh Almodaresi, Jamshed Khan, Sergey Madaminov, and 4 more authors
    Bioinformatics, 2022
    PDF Code

2021

  1. Genome Biology 2021
    VariantStore: an index for large-scale genomic variant search
    Prashant Pandey, Yinjie Gao, and Carl Kingsford
    Genome biology, 2021
    PDF Video Code

2019

  1. RECOMB 2019, JCB 2020
    An Efficient, Scalable and Exact Representation of High-Dimensional Color Information Enabled via de Bruijn Graph Search Problem
    Fatemeh Almodaresi, Prashant Pandey, Michael Ferdman, and 2 more authors
    In Research in Computational Molecular Biology - 23rd Annual International Conference, RECOMB 2019, Washington, DC, USA, May 5-8, 2019, Proceedings, 2019
    DOI PDF Code

2018

  1. RECOMB 2018, Cell Systems 2018
    Mantis: A Fast, Small, and Exact Large-Scale Sequence-Search Index
    Prashant Pandey, Fatemeh Almodaresi, Michael A. Bender, and 3 more authors
    In Research in Computational Molecular Biology - 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings, 2018
    PDF Code

2017

  1. BIOINFORMATICS 2017
    Squeakr: An Exact and Approximate K-Mer Counting System
    Prashant Pandey, Michael A. Bender, Rob Johnson, and 1 more author
    Bioinform., 2017
    DOI PDF Code
  2. ISMB 2017, BIOINFORMATICS 2017
    deBGR: An Efficient and Near-Exact Representation of the Weighted de Bruijn Graph
    Prashant Pandey, Michael A. Bender, Rob Johnson, and 1 more author
    Bioinform., 2017
    DOI PDF Video Code
  3. WABI 2017
    Rainbowfish: A Succinct Colored de Bruijn Graph Representation
    Fatemeh Almodaresi, Prashant Pandey, and Rob Patro
    In 17th International Workshop on Algorithms in Bioinformatics, WABI 2017, August 21-23, 2017, Boston, MA, USA, 2017
    DOI PDF Code