Compressed inverted indexes for scalable sequence similarity

This paper introduces Onika, a Rust-based system that utilizes compressed inverted indexes and early-pruning schemes to enable scalable, output-sensitive all-vs-all sequence similarity comparisons with orders-of-magnitude speedups over existing forward-index tools while maintaining rigorous accuracy guarantees.

The Gist

Imagine you are a librarian in a library that has grown so massive it now contains billions of books (representing DNA sequences from bacteria, viruses, and humans). Your job is to find books that are similar to each other—maybe to find different strains of the same bacteria or to spot errors in genetic data.

In the past, to find similar books, you had to take every single book off the shelf, open it, and compare its first few sentences with every other book in the library. This is like the old way computers did it: slow, exhausting, and impossible when the library gets too big.

This paper introduces a new, super-fast system called Onika that solves this problem using three clever tricks. Here is how it works, explained simply:

1. The "Fingerprint" Shortcut (Sketching)

Instead of reading the whole book, imagine you take a tiny fingerprint of each one.

• Old Way: You compare the whole book (thousands of pages).
• New Way: You only compare a small, unique set of 512 numbers (the fingerprint) that represents the book.
• The Problem: Even with fingerprints, if you have a billion books, you still have to compare every fingerprint against every other fingerprint. That's a trillion comparisons! It's like trying to match every person in a stadium with every other person by shaking hands.

2. The "Phone Book" Trick (Inverted Index)

This is the paper's biggest breakthrough. Instead of listing books and then their fingerprints (Forward Index), Onika builds a giant phone book (Inverted Index).

• The Old Way (Forward Index):

  • Book A: Fingerprint 123, 456, 789
  • Book B: Fingerprint 123, 999, 101
  • To find matches: You have to scan Book A, then Book B, then Book C... comparing them one by one.

• The Onika Way (Inverted Index):

  • Fingerprint 123: Appears in Book A, Book B, Book Z...
  • Fingerprint 456: Appears in Book A, Book K...
  • To find matches: You look up "123" in the phone book. Boom! The book instantly tells you, "Hey, Book A and Book B both have this fingerprint. They are similar!" You don't need to check the other billions of books that don't have that fingerprint.

The Analogy:
Imagine you are looking for people who share a specific birthday.

• Old Way: You walk up to every person in the stadium and ask, "What is your birthday?" Then you compare lists.
• Onika Way: You have a list sorted by birthday. You just look at the "January 1st" list. Everyone on that list is a match. You ignore everyone born on other days instantly.

The authors proved mathematically that this "phone book" takes up exactly the same amount of memory as the old way, but it is much faster because it skips the boring stuff.

3. The "Early Exit" Strategy (Pruning)

Sometimes, you don't need to check every fingerprint to know two books are different.

• The Scenario: You are comparing Book A and Book B. You check the first 10 fingerprints, and they only match once. You know they are very different.
• The Old Way: The computer keeps checking all 512 fingerprints just to be sure.
• The Onika Way: It has a smart rule. "If they haven't matched enough by now, stop checking! They are definitely not similar enough to care about."
• The Result: It stops the comparison early, saving massive amounts of time and energy. It's like a bouncer at a club who sees you don't have a ticket and stops you at the door instead of letting you in to check your ID later.

4. Organizing the Shelves (Reordering)

Finally, Onika is smart about how it stores the data.

• If you have 1,000 copies of the same book (redundant data), Onika realizes they are similar.
• It rearranges the library so that similar books are sitting right next to each other on the shelf.
• This makes the "phone book" lists much shorter and easier to compress (like packing a suitcase tightly). This saves even more space and makes the computer run faster.

The Bottom Line

The authors built a tool called Onika (written in a programming language called Rust) that uses these tricks.

• Speed: It is thousands of times faster than current tools when comparing huge collections of DNA.
• Memory: It doesn't need more computer memory than the old tools; it just uses it smarter.
• Accuracy: It doesn't miss any important matches; it just ignores the ones that are obviously unimportant.

In short: They turned a slow, brute-force search into a smart, organized, and lightning-fast system, allowing scientists to analyze the entire "library of life" without waiting years for the results.

Technical Summary

1. Problem Statement

Modern computational biology faces a scalability crisis due to the exponential growth of nucleotide sequence archives (e.g., SRA, assembled genomes). Traditional alignment-based methods (like BLAST) are computationally prohibitive for this scale. While alignment-free methods using MinHash sketching (e.g., Mash, Dashing2, Bindash2) have become the standard for estimating sequence similarity (Jaccard index), they face two critical bottlenecks:

• Forward Index Limitations: Current tools use "forward indexes" where every sequence is represented by an explicit fingerprint vector. Comparing two collections of size $Q$ and $R$ requires $O(Q \cdot R \cdot S)$ operations (where $S$ is sketch size), leading to quadratic time complexity for all-vs-all comparisons.
• Memory and Redundancy: Storing explicit vectors for millions of sequences consumes significant memory. Furthermore, existing inverted index attempts (like the authors' previous tool, NIQKI) suffered from exponential memory overhead and inefficient memory representation, making them impractical for large-scale deployment.

The core challenge is to design an indexing architecture that maintains the accuracy of sketching while achieving output-sensitive time complexity (proportional only to the number of matches found) and linear space complexity comparable to forward indexes.

2. Methodology

The authors propose a framework based on compressed inverted indexes over sketch fingerprints, implemented in a Rust system called Onika.

A. Theoretical Foundation: Inverted vs. Forward Indexes

• Forward Index: Maps documents to their sketches ($D \times S$ matrix). Comparison requires iterating through all pairs.
• Inverted Index: Maps each possible fingerprint value to a list of documents containing it.
  • Space Complexity: The authors prove (Theorem 1) that with $\delta$-encoding (storing differences between sorted document IDs) and assuming uniform fingerprint distribution, the expected size of an inverted index is $O(DSW)$ bits. This matches the space complexity of a forward index, debunking the myth that inverted indexes inherently require more memory.
• Comparison Algorithms:
  • Algorithm 1 (Forward): $O(QRS + \Sigma M)$.
  • Algorithm 2 (Hybrid): $O(QS + \Sigma M)$.
  • Algorithm 3 (Inverted-Inverted): $O(\Sigma M)$. This is the optimal approach. It iterates only over matching fingerprint positions between two inverted indexes. The running time is proportional to $\Sigma M$ (the total number of matching sketch positions), making it output-sensitive.

B. Implementation Strategy (Onika)

• Two-Pass Construction: To avoid memory fragmentation and high peak usage, Onika uses a two-pass strategy:
  1. Pass 1: Computes sketches for all datasets and stores them in a transposed layout (partitions $\times$ datasets).
  2. Pass 2: Scans partition by partition, building posting lists, applying $\delta$-encoding, and compressing to disk before moving to the next partition.
• Similarity-Aware Reordering: To improve compression, Onika optionally reorders dataset identifiers before index construction. It greedily places similar sequences next to each other, increasing locality in posting lists and enhancing $\delta$-encoding efficiency.

C. Pruning Schemes

To handle the requirement of finding only pairs above a similarity threshold $t$, the authors introduce two pruning mechanisms:

1. Exact Pruning: If the current matches $k$ plus the remaining partitions $(S-n)$ cannot reach the threshold $tS$, the pair is discarded immediately.
2. Probabilistic Pruning: Uses a statistical bound (based on the binomial distribution and Agievich's upper bound for binomial coefficients) to estimate the probability that a pair will eventually meet the threshold. If the probability is below a user-defined risk $s$, the pair is discarded. This allows for early termination with explicit control over the false-rejection rate.

3. Key Contributions

1. Theoretical Proof of Optimality: Proved that inverted indexes can achieve the same asymptotic space complexity as forward indexes ($O(DSW)$) while offering strictly superior time complexity for all-vs-all comparisons ($O(\Sigma M)$ vs. $O(QRS)$).
2. Onika System: An open-source Rust implementation featuring:
   • Compressed inverted posting lists.
   • A memory-efficient two-pass construction algorithm.
   • A high-throughput inverted-inverted comparator.
   • Optional dataset reordering to shrink index size.
3. Pruning Framework: Development of exact and probabilistic early-pruning schemes that reduce computational load and memory footprint without compromising the retrieval of high-similarity pairs.

4. Results

Experiments were conducted on bacterial genome repositories (RefSeq) and long-read HiFi datasets, comparing Onika against Dashing2 and Bindash2.

• Scalability & Speed:
  • On the RefSeq bacterial genomes (high redundancy), Onika was 3x faster than Bindash2 and 5x faster than Dashing2 on the largest collections.
  • On random synthetic sequences (low redundancy, best-case scenario), Onika was >1,000x (3 orders of magnitude) faster than state-of-the-art tools.
• Index Size:
  • Onika's compressed sketch sizes are comparable to Bindash2.
  • The optional reordering step reduced sketch sizes by >35% in redundant collections.
• Memory Usage:
  • Onika uses less memory than Dashing2. While Bindash2 uses less memory due to chunking (which slows it down), Onika maintains a balance of low memory and high speed.
• Robustness:
  • Onika's performance is largely insensitive to read ordering, whereas Dashing2's performance degrades significantly when reads are reordered (e.g., by Oreo).
• Pruning Efficiency:
  • Probabilistic pruning drastically reduced runtime while keeping the fraction of missed hits (false negatives) negligible and strictly below the chosen probability threshold.

5. Significance

This paper fundamentally shifts the paradigm for large-scale sequence similarity search. By demonstrating that inverted indexes are not only viable but optimal for sketch-based comparison, the authors solve the scalability bottleneck that has limited the application of MinHash to massive datasets.

• Impact: Enables efficient all-vs-all comparisons of billions of sequences, which was previously intractable.
• Application: Critical for pangenomics, metagenomic screening, and large-scale phylogenetics where identifying similar sequences in massive, diverse databases is required.
• Future Work: The framework opens doors for GPU acceleration, specialized top-K retrieval algorithms, and redundancy-aware mutualized computations.

In summary, Onika represents a breakthrough in bioinformatics infrastructure, providing a tool that is theoretically optimal in both time and space, and empirically superior in speed and scalability compared to current industry standards.