pipette
ESEspañol

LinearRaccess: linear-time approximation of RNA accessibility without base-pair span limits

T. Otagaki, K. Sato

PreprintClaims a big stepCode available

In the authors' words

Motivation: RNA accessibility is the probability that every nucleotide in a contiguous interval is simultaneously unpaired; it is widely used to predict binding sites for RNA-binding proteins and other RNA-RNA interactions, often in the form of the opening energy, an equivalent measure on a logarithmic scale. Existing tools restrict the maximum base-pair span, discarding long-range base pairs that matter biologically. Others sample structures, introducing statistical variance, or compute accessibility exactly without a span limit, at cubic time cost. No existing method computes the accessibility of windows longer than one nucleotide deterministically in linear time while preserving long-range base pairs. We present LinearRaccess, which computes accessibility directly in linear time via beam-pruned inside-outside dynamic programming with a difference-array aggregation step, without restricting base-pair span. Results: For a sequence of length N and a fixed beam width b, LinearRaccess runs in O(N) time and O(Nb) memory. Against exact accessibility on 12,872 bpRNA-1m(90) sequences of 100-1,000 nt, its median opening-energy error is below 0.001 kcal/mol (0.14 kcal/mol for 700-1,000 nt), and it distinguishes windows of very small accessibility, including 35-nt windows, below the resolution of sampling-based estimates. LinearRaccess analyzes the full 29,903-nt SARS-CoV-2 genome in 419 seconds. Conclusion: LinearRaccess is the first method to compute the accessibility of windows longer than one nucleotide deterministically (without sampling) in linear time without restricting base-pair span. Availability: https://github.com/TakumiOtagaki/LinearRaccess, archived at Zenodo (https://doi.org/10.5281/zenodo.23598502).

Main resultThe abstract does not state a limitation.

In plain words AI summary

RNA accessibility measures how likely a stretch of RNA is to be unpaired, which helps predict where proteins or other RNAs can bind. Previous methods either ignored long-range pairings, used random sampling, or were too slow. LinearRaccess calculates accessibility in linear time without these limits, using a pruned dynamic programming approach. It achieves median errors below 0.001 kcal/mol on short sequences and 0.14 kcal/mol on longer ones, and can detect very small accessibility windows that sampling misses. It analyzed the full SARS-CoV-2 genome in under seven minutes.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.

Appeared: Saturday, November 7. bioRxiv. Preprint, not yet peer-reviewed.

DOI: 10.64898/2026.11.04.764167