RNA Secondary Structures with Limited Base Pair Span: Exact Backtracking and an Application.

ABSTRACT: The accuracy of RNA secondary structure prediction decreases with the span of a base pair, i.e., the number of nucleotides that it encloses. The dynamic programming algorithms for RNA folding can be easily specialized in order to consider only base pairs with a limited span L, reducing the memory requirements to O(nL), and further to O(n) by interleaving backtracking. However, the latter is an approximation that precludes the retrieval of the globally optimal structure. So far, the ViennaRNA package therefore does not provide a tool for computing optimal, span-restricted minimum energy structure. Here, we report on an efficient backtracking algorithm that reconstructs the globally optimal structure from the locally optimal fragments that are produced by the interleaved backtracking impleme

SUBMITTER: Lorenz R 

PROVIDER: S-EPMC7823788 | biostudies-literature | 2020 Dec

REPOSITORIES: biostudies-literature