LazySampling and LinearSampling: fast stochastic sampling of RNA secondary structure with applications to SARS-CoV-2.

ABSTRACT: Many RNAs fold into multiple structures at equilibrium, and there is a need to sample these structures according to their probabilities in the ensemble. The conventional sampling algorithm suffers from two limitations: (i) the sampling phase is slow due to many repeated calculations; and (ii) the end-to-end runtime scales cubically with the sequence length. These issues make it difficult to be applied to long RNAs, such as the full genomes of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). To address these problems, we devise a new sampling algorithm, LazySampling, which eliminates redundant work via on-demand caching. Based on LazySampling, we further derive LinearSampling, an end-to-end linear time sampling algorithm. Benchmarking on nine diverse RNA families, the sampled s

SUBMITTER: Zhang H 

PROVIDER: S-EPMC9881153 | biostudies-literature | 2023 Jan

REPOSITORIES: biostudies-literature