Dataset Information

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search.

ABSTRACT:

Motivation

Predicting the secondary structure of an ribonucleic acid (RNA) sequence is useful in many applications. Existing algorithms [based on dynamic programming] suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications.

Results

We present a novel alternative O(n3)-time dynamic programming algorithm for RNA folding that is amenable to heuristics that make it run in O(n) time and O(n) space, while producing a high-quality approximation to the optimal solution. Inspired by incremental parsing for context-free grammars in computational linguistics, our alternative dynamic programming algorithm scans the sequence in a left-to-right (5'-to-3') direction rather than in a bottom-up fashion, which allows us to employ the effective beam pruning heuristic. Our work, though inexact, is the first RNA folding algorithm to achieve linear runtime (and linear space) without imposing constraints on the output structure. Surprisingly, our approximate search results in even higher overall accuracy on a diverse database of sequences with known structures. More interestingly, it leads to significantly more accurate predictions on the longest sequence families in that database (16S and 23S Ribosomal RNAs), as well as improved accuracies for long-range base pairs (500+ nucleotides apart), both of which are well known to be challenging for the current models.

Availability and implementation

Our source code is available at https://github.com/LinearFold/LinearFold, and our webserver is at http://linearfold.org (sequence limit: 100 000nt).

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Huang L

PROVIDER: S-EPMC6681470 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search.

Huang Liang L Zhang He H Deng Dezhong D Zhao Kai K Liu Kaibo K Hendrix David A DA Mathews David H DH

Bioinformatics (Oxford, England) 20190701 14

<h4>Motivation</h4>Predicting the secondary structure of an ribonucleic acid (RNA) sequence is useful in many applications. Existing algorithms [based on dynamic programming] suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications.<h4>Results</h4>We present a novel alternative O(n3)-time dynamic programming algorithm for RNA folding that is amenable to heuristics that make it run in O(n) time and O(n) spac ...[more]

PMID: 31510672

Similar Datasets

Project description:Ecological decision problems, such as those encountered in agriculture, often require managing conflicts between short-term costs and long-term benefits. Dynamic programming is an ideal method for optimally solving such problems but agricultural problems are often subject to additional complexities that produce state spaces intractable to exact solutions. In contrast, look-ahead policies, a class of approximate dynamic programming (ADP) algorithm, may attempt to solve problems of arbitrary magnitude. However, these algorithms focus on a temporally truncated caricature of the full decision problem over a defined planning horizon and as such are not guaranteed to suggest optimal actions. Thus, look-ahead policies may offer promising means of addressing detail-rich ecological decision problems but may not be capable of fully utilizing the information available to them, especially in scenarios where the best short- and long-term solutions may differ. We constructed and applied look-ahead policies to the management of a hypothetical, stage-structured, continually reproducing, agricultural insect pest. The management objective was to minimize the combined costs of management actions and crop damage over a 16-week growing season. The manager could elect to utilize insecticidal sprays or one of six release ratios of male-selecting transgenic insects where the release ratio determines the number of transgenic insects to be released for each wild-type male insect in the population. Complicating matters was the expression of insecticide resistance at non-trivial frequencies in the pest population. We assessed the extent to which look-ahead policies were able to recognize the potential threat of insecticide resistance and successfully integrate insecticides and transgenic releases to capitalize upon their respective benefits. Look-ahead policies were competent at anticipating and responding to ecological and economic information. Policies with longer planning horizons made fewer, better-timed insecticidal sprays and made more frequent transgenic releases, which consequently facilitated lower resistance allele frequencies. However, look-ahead policies were ultimately inefficient resistance managers, and directly responded to resistance only when it was dominant and prevalent. Effective long-term agricultural management requires the capacity to anticipate and respond to the evolution of resistance. Look-ahead policies can accommodate all the information pertinent to making the best long-term decision but may lack the perspective to actually do so.

Project description:BackgroundIt is well known that the search for homologous RNAs is more effective if both sequence and structure information is incorporated into the search. However, current tools for searching with RNA sequence-structure patterns cannot fully handle mutations occurring on both these levels or are simply not fast enough for searching large sequence databases because of the high computational costs of the underlying sequence-structure alignment problem.ResultsWe present new fast index-based and online algorithms for approximate matching of RNA sequence-structure patterns supporting a full set of edit operations on single bases and base pairs. Our methods efficiently compute semi-global alignments of structural RNA patterns and substrings of the target sequence whose costs satisfy a user-defined sequence-structure edit distance threshold. For this purpose, we introduce a new computing scheme to optimally reuse the entries of the required dynamic programming matrices for all substrings and combine it with a technique for avoiding the alignment computation of non-matching substrings. Our new index-based methods exploit suffix arrays preprocessed from the target database and achieve running times that are sublinear in the size of the searched sequences. To support the description of RNA molecules that fold into complex secondary structures with multiple ordered sequence-structure patterns, we use fast algorithms for the local or global chaining of approximate sequence-structure pattern matches. The chaining step removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our improved online algorithm is faster than the best previous method by up to factor 45. Our best new index-based algorithm achieves a speedup of factor 560.ConclusionsThe presented methods achieve considerable speedups compared to the best previous method. This, together with the expected sublinear running time of the presented index-based algorithms, allows for the first time approximate matching of RNA sequence-structure patterns in large sequence databases. Beyond the algorithmic contributions, we provide with RaligNAtor a robust and well documented open-source software package implementing the algorithms presented in this manuscript. The RaligNAtor software is available at http://www.zbh.uni-hamburg.de/ralignator.

Dataset Information

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search.

Motivation

Results

Availability and implementation

Supplementary information

Publications

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets