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

Abstract

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).