Scanning transcriptomes for nonlinear, domain-level similarities using hmSEEKR

Technical Summary: Scanning Transcriptomes for Nonlinear, Domain-Level Similarities using hmSEEKR

Problem Statement
Long noncoding RNAs (lncRNAs) are critical regulators of biological processes, yet the vast majority of annotated lncRNAs lack assigned functions. A primary challenge in ascribing function to new lncRNAs is that they often lack significant linear sequence similarity to known functional RNAs, rendering standard alignment tools ineffective. While previous work established that nonlinear k-mer content (via the SEEKR algorithm) could predict protein binding and cellular localization, the original SEEKR framework required users to pre-fragment target transcripts into domains. This is a significant limitation because the boundaries of functional domains in uncharacterized lncRNAs are often unknown; arbitrary fragmentation risks splitting functional domains and missing regional similarities.

Methodology
The authors introduce hmSEEKR, a two-state Hidden Markov Model (HMM) designed to scan transcriptomes for regions of non-linear sequence similarity to a query domain without requiring prior knowledge of domain boundaries.

• Algorithmic Framework: hmSEEKR compares a "Query" (Q) state, representing a domain of interest, against a "Null" (N) state, representing a background set of sequences (e.g., the transcriptome). It utilizes k-mer frequencies calculated by tiling across sequences with a single-nucleotide step size.
• Conditioned Emission: To reconcile the non-independence of k-mers generated by single-nucleotide stepping with the independent emission assumptions of standard HMMs, hmSEEKR employs a "conditioned emission" approach. This calculates the probability of a specific k-mer based on the preceding k-mer in the sequence, effectively reducing the emission matrix to the four possible k-mers that can follow the current position.
• Parameter Optimization: Since suitable training datasets for lncRNA transition probabilities are often unavailable, the authors developed a grid-search function. This empirically derives optimal transition probabilities ($qT$ and $nT$) by maximizing the SEEKR-derived Pearson's $r$ values between the query and hits in a training set. Based on extensive testing, default parameters of $qT=0.99$ and $nT=0.90$ were established for $k=4, 5, 6$.
• Combinatorial Search: A "seqs-to-summary" feature allows for parallel scanning against multiple query domains, aggregating hits to identify transcripts containing sequential, domain-level similarities.

Key Results
The study validates hmSEEKR using the conserved lncRNAs XIST, NEAT1, and MALAT1 as query sources within K562 cell chromatin-associated transcriptomes.

1. Recovery of Inserted Domains: When known domains from XIST, NEAT1, and MALAT1 were randomly inserted into the transcriptome, hmSEEKR successfully recovered 100% of the insertions. The algorithm demonstrated robustness to mutation, with $k=6$ performing best in recovering mutated fragments.
2. Protein Interaction Validation: Hits identified by hmSEEKR within the transcriptome exhibited significantly higher enrichment for the same RNA-binding proteins (RBPs) as their corresponding query domains compared to shuffled controls. This held true for both individual domains and combinatorial interactions (e.g., domains known to bind multiple proteins simultaneously).
3. Transcriptome-Wide Similarity: At stringent thresholds ($p < 0.001$), many domains within XIST, NEAT1, and MALAT1 were found to be unique or rare (matching <200 genes). However, at lower stringency ($p < 0.05$), widespread similarities were detected in both protein-coding and lncRNA genes, frequently located in distal introns.
4. Sequential Domain Discovery:
   • XIST-like Transcripts: Searches for transcripts containing sequential hits to minimal functional XIST domains (Repeats A, F, B1/2, D, E) identified 674 candidates at $p < 0.05$, mostly from protein-coding genes. These candidates showed protein association networks significantly more similar to XIST than the background transcriptome.
   • NEAT1-like Transcripts: Similar searches for minimal NEAT1 domains identified 2,003 candidates at $p < 0.05$. These candidates were significantly enriched for "semi-extractable" properties (a hallmark of NEAT1) and exhibited protein association networks resembling NEAT1.
5. Regulatory Domain Enrichment: When searching sets of known cis-activating and cis-repressive lncRNAs, the authors observed distinct enrichments. Domains associated with transcription-promoting complexes (e.g., MLL, Mediator, P300) were enriched in activating lncRNAs, while HNRNP-binding domains were enriched in repressive lncRNAs.

Significance and Claims
The authors position hmSEEKR as a hypothesis-generating tool that bridges the gap between sequence and function for lncRNAs. Key claims include:

• Minimal Training Requirements: Unlike deep learning models that require large, curated training corpora (which do not yet exist for many lncRNA functions), hmSEEKR can be trained on a single domain from a single lncRNA using standard computing resources.
• Discovery of Non-Linear Similarities: The tool enables the a priori discovery of functional elements based on shared k-mer content, even when linear alignment fails.
• Biological Relevance: The identification of transcripts with sequential domain similarities to XIST and NEAT1, which subsequently share protein interaction networks and biological properties (like semi-extractability), suggests that hmSEEKR can identify RNAs with analogous biological functions.
• Intronic Reservoirs: The findings support the view that intronic elements, particularly in nascent transcripts, may serve as a reservoir of regulatory domains with functions beyond splicing control.

The paper concludes that hmSEEKR offers a sequence-informed approach to discover functional elements within noncoding transcriptomes, providing footholds for future experimental validation of lncRNA mechanisms.