Hierarchical genomic feature annotation with variable-length queries

This paper introduces HKS, a data structure built on the Spectral Burrows-Wheeler Transform that enables exact, lossless hierarchical annotation of variable-length k-mers by resolving multi-matches through a user-defined category hierarchy and enhancing specificity with a context-aware smoothing algorithm, achieving high accuracy in genomic feature assignment while maintaining performance comparable to existing tools like Kraken2.

The Gist

Imagine you have a massive library containing every book ever written, but instead of titles, the books are just long strings of letters (A, C, G, T) representing DNA. Now, imagine you have a new, unknown book (a DNA sequence from a person) and you want to know exactly which "section" of the library it came from. Is it from the "Chromosome 1" section? The "Mitochondria" section? Or maybe it's a mix?

This is the problem scientists face when analyzing DNA. They use short snippets of letters called k-mers (like 3-letter or 31-letter words) to find matches. But existing tools have three big headaches:

1. The "One Size Fits All" Problem: You have to pick a specific word length (say, 31 letters) before you start. If you pick too short, the word is too common and matches everywhere. If you pick too long, a single typo in your new book means the tool can't find it at all.
2. The "Confused Librarian" Problem: If a word appears in two different sections (like a word found in both the "History" and "Science" aisles), old tools either guess randomly, throw the word away, or give a vague answer like "It's in the library."
3. The "Fast but Sloppy" Problem: To make things fast, many tools use shortcuts (like looking at just the first letter of a word) that speed things up but lose accuracy.

Enter HKS: The Smart, Flexible Librarian

The paper introduces a new tool called HKS. Think of HKS as a super-smart librarian who doesn't need you to pick a word length in advance.

1. The Magic Index (The Spectral Burrows-Wheeler Transform)

Imagine you have a giant, magical index card system. Usually, to look up a word, you need a specific index for 3-letter words, another for 4-letter words, and so on. That's a nightmare.

HKS builds one single index for a maximum length (let's say 63 letters). Because of a clever mathematical trick (the Spectral Burrows-Wheeler Transform), this one index can instantly answer questions about any word length from 1 up to 63. It's like having a dictionary that can look up "cat," "catch," and "catcher" all at once without needing three different books.

2. The Family Tree (Hierarchical Annotation)

When a word appears in multiple places, HKS doesn't guess. It looks at a Family Tree of the library sections.

• The Scenario: A word appears on Chromosome 13 and Chromosome 21.
• The Old Way: "I don't know, maybe it's Chromosome 13?" (Wrong) or "It's just 'Human DNA'" (Too vague).
• The HKS Way: It looks at the Family Tree. It sees that Chromosome 13 and 21 are both "Acrocentric Chromosomes" (a specific group). So, it labels the word as "Acrocentric." It finds the most specific common ancestor. It's like saying, "This book belongs to the 'Science Fiction' section, not just 'Books' or 'Fiction'."

3. The "Context Clue" Smoothing (Fixing the Gaps)

Sometimes, a DNA sequence has a few typos (mutations) or is brand new (not in the library yet). This creates a "gap" where the tool can't identify the section.

• The Analogy: Imagine you are reading a sentence: "The cat sat on the [BLANK] mat." You don't know the missing word. But if the next word is "fluffy," you can guess it was "soft."
• HKS's Trick: If HKS sees a gap of unknown words surrounded by clear "Chromosome 1" words, it uses the context to fill in the blank. It says, "Since the neighbors are definitely Chromosome 1, this weird gap is probably Chromosome 1 too." This "smoothing" process fixes about 16% more of the DNA, turning vague answers into precise ones.

Why This Matters (The Results)

The authors tested HKS on human DNA.

• Before Smoothing: It could identify about 81% of the DNA snippets correctly.
• After Smoothing: It jumped to 97%.
• The "Errors": The few mistakes it did make weren't because the tool was broken. They were because of real biological quirks, like chromosomes swapping tiny pieces of themselves (recombination). HKS actually helped scientists see these biological events clearly!

The Bottom Line

HKS is like upgrading from a rigid, single-purpose flashlight to a smart, multi-spectrum camera.

• It doesn't force you to choose a setting (word length).
• It understands the relationships between things (the family tree).
• It uses context to fill in the blanks.
• It's just as fast as the old, sloppy tools but gives you perfect, lossless accuracy.

In short, HKS lets scientists read the genome's story with much higher resolution, spotting the tiny plot twists that previous tools missed.

Technical Summary

1. Problem Statement

K-mer-based methods are fundamental to genomic sequence classification (metagenomics, pangenomics, RNA-seq), but existing tools suffer from three critical limitations:

1. Fixed $k$-mer Length: Most tools require the $k$-mer length to be fixed at index construction. Short $k$-mers are non-specific (shared across categories), while long $k$-mers are specific but fail to match if the query diverges even slightly (e.g., due to SNPs). Users must choose a compromise or build multiple indexes.
2. Inconsistent Handling of Multi-matching: When a $k$-mer appears in multiple genomic categories (e.g., repetitive regions), tools handle ambiguity inconsistently—some mask them, others use probabilistic models, or propagate labels up a hierarchy (Lowest Common Ancestor, LCA).
3. Lossy Approximations: To save space and speed, many tools (like Kraken2) use minimizers, Bloom filters, or truncated hashes. These introduce false positives/negatives and complicate the interpretation of exact matches.

There is no existing tool that provides exact, lossless, hierarchical annotation for variable-length $k$-mer queries from a single index.

2. Methodology: The HKS Data Structure

The authors present HKS, a data structure designed to address these limitations. It is built upon the Spectral Burrows–Wheeler Transform (SBWT) and integrates a user-defined category hierarchy.

Core Components

• SBWT & LCS Array: HKS uses the SBWT to encode the $s$-spectrum (all distinct $s$-mers) of the reference sequences. It is augmented with a Longest Common Suffix (LCS) array to enable efficient range queries and left-contraction operations.
• Feature Assignment Framework:
  • Categories: Labels assigned to genomic positions (e.g., specific chromosomes or repeat families).
  • Hierarchy: A tree structure where leaves are categories and internal nodes group related categories (e.g., "Acrocentric" grouping chr13, 14, 15, 21, 22).
  • Features: Disjoint sets of $k$-mers. A $k$-mer occurring in multiple categories is assigned to the most specific common ancestor (LCA) in the hierarchy. This ensures every $k$-mer has exactly one unique label.
• Index Construction:
  • The index is built for a maximum query length $s$.
  • It maps every $s$-mer in the SBWT to a node in the hierarchy (the LCA of all sequences containing that $s$-mer).
  • This creates a "colored variable-order de Bruijn graph" where colors are hierarchical labels.
• Query Algorithm:
  • Supports queries for any $k \le s$ using the same index.
  • Priming: The index is pre-processed (in $O(n)$ time) to map $s$-mer ranks to $k$-mer ranks based on shared suffixes, allowing direct lookup of the LCA for any $k$-mer length.
  • Streaming: Uses $s$-bounded matching statistics to stream through a query sequence, determining the hierarchical label for every position.

Post-Processing: Hierarchy-Aware Smoothing

To address specificity loss caused by multi-matching $k$-mers or novel $k$-mers (absent from the index), the authors introduce a smoothing algorithm:

• It scans the query for windows exhibiting a Specific $\to$ General $\to$ Specific pattern in the hierarchy.
• If a region of non-specific (multi-matching) or unassigned $k$-mers is flanked by specific labels, the algorithm reassigns the interior $k$-mers to the LCA of the flanking labels.
• This recovers specificity without requiring the $k$-mer itself to be unique.

3. Key Contributions

1. Feature Assignment Framework: Formalizes the partitioning of $k$-mers into disjoint sets based on a user-defined hierarchy, generalizing the LCA strategy to any hierarchical structure (not just taxonomy).
2. Variable-Length Exact Index: Realizes a theoretical "colored variable-order de Bruijn graph" using SBWT, enabling exact queries for any $k \le s$ from a single index, eliminating the need for multiple indexes.
3. Hierarchy-Aware Smoothing: A novel post-processing step that leverages flanking sequence context and the hierarchy to resolve ambiguous $k$-mers, significantly improving concordance.

4. Results and Validation

The authors validated HKS by annotating human genome assemblies (CHM13, HG002, NA19185) against a T2T-CHM13v2.0 chromosome index.

• Accuracy & Concordance:
  • Pre-smoothing: Achieved near-perfect accuracy (~99.8%) for assigned $k$-mers but left ~19% of $k$-mers unresolved (assigned to non-specific nodes or "novel").
  • Post-smoothing: Increased overall concordance from ~81% to ~97%. The smoothing algorithm successfully resolved the majority of non-specific $k$-mers into specific chromosome assignments.
  • Residual Errors: Remaining errors (~3%) were attributed to known biological phenomena (acrocentric short-arm recombination, subtelomeric duplications, pseudoautosomal regions) rather than algorithmic failures.
• Performance Benchmarking (vs. Kraken2):
  • Throughput: HKS provides query throughput comparable to Kraken2 across all tested $k$-mer lengths ($k=15$ to $63$).
  • Flexibility: Unlike Kraken2, which requires rebuilding the index for every $k$ or relies on lossy minimizers ($m < k$), HKS uses a single index for all $k \le s$.
  • Exactness: When Kraken2 is configured for exact matching ($m=k$), HKS is faster and produces a smaller index.
  • Index Size: HKS index size (10.4 GiB for $s=63$) is competitive with Kraken2 when Kraken uses high-precision settings, though Kraken can be smaller with aggressive lossy settings ($m \ll k$).

5. Significance

• Lossless Annotation: HKS provides the first tool to perform exact, lossless hierarchical annotation across a range of $k$-mer lengths from a single index, removing the trade-off between specificity and sensitivity inherent in fixed-$k$ or lossy approaches.
• Biological Insight: The positional resolution of HKS allows for the detection of boundaries between features within a single sequence (e.g., translocations, recombination events) rather than assigning a single label to an entire read.
• Generalizability: While demonstrated on chromosomes and repeats, the framework is applicable to any hierarchical genomic annotation, including taxonomic profiling and transcript-level quantification.
• Implementation: The tool is implemented in Rust and is open-source, offering a robust alternative to current state-of-the-art tools like Kraken2 for applications requiring high precision and flexibility.