Infrared: a declarative tree decomposition-powered framework for bioinformatics

MOTIVATION

Many bioinformatics problems can be approached as optimization or controlled sampling tasks, and solved exactly and efficiently using Dynamic Programming (DP). However, such exact methods are typically tailored towards specific settings, complex to develop, and hard to implement and adapt to problem variations.

METHODS

We introduce the Infrared framework to overcome such hindrances for a large class of problems. Its underlying paradigm is tailored toward problems that can be declaratively formalized as sparse feature networks, a generalization of constraint networks. Classic Boolean constraints specify a search space, consisting of putative solutions whose evaluation is performed through a combination of features. Problems are then solved using generic cluster tree elimination algorithms over a tree decomposition of the feature network. Their overall complexities are linear on the number of variables, and only exponential in the treewidth of the feature network. For sparse feature networks, associated with low to moderate treewidths, these algorithms allow to find optimal solutions, or generate controlled samples, with practical empirical efficiency.

RESULTS

Implementing these methods, the Infrared software allows Python programmers to rapidly develop exact optimization and sampling applications based on a tree decomposition-based efficient processing. Instead of directly coding specialized algorithms, problems are declaratively modeled as sets of variables over finite domains, whose dependencies are captured by constraints and functions. Such models are then automatically solved by generic DP algorithms. To illustrate the applicability of Infrared in bioinformatics and guide new users, we model and discuss variants of bioinformatics applications. We provide reimplementations and extensions of methods for RNA design, RNA sequence-structure alignment, parsimony-driven inference of ancestral traits in phylogenetic trees/networks, and design of coding sequences. Moreover, we demonstrate multidimensional Boltzmann sampling. These applications of the framework-together with our novel results-underline the practical relevance of Infrared. Remarkably, the achieved complexities are typically equivalent to the ones of specialized algorithms and implementations.

AVAILABILITY

Infrared is available at https://amibio.gitlabpages.inria.fr/Infrared with extensive documentation, including various usage examples and API reference; it can be installed using Conda or from source.

Automated design of dynamic programming schemes for RNA folding with pseudoknots

Although RNA secondary structure prediction is a textbook application of dynamic programming (DP) and routine task in RNA structure analysis, it remains challenging whenever pseudoknots come into play. Since the prediction of pseudoknotted structures by minimizing (realistically modelled) energy is NP-hard, specialized algorithms have been proposed for restricted conformation classes that capture the most frequently observed configurations. To achieve good performance, these methods rely on specific and carefully hand-crafted DP schemes. In contrast, we generalize and fully automatize the design of DP pseudoknot prediction algorithms. For this purpose, we formalize the problem of designing DP algorithms for an (infinite) class of conformations, modeled by (a finite number of) fatgraphs, and automatically build DP schemes minimizing their algorithmic complexity. We propose an algorithm for the problem, based on the tree-decomposition of a well-chosen representative structure, which we simplify and reinterpret as a DP scheme. The algorithm is fixed-parameter tractable for the treewidth tw of the fatgraph, and its output represents a [Formula: see text] algorithm (and even possibly [Formula: see text] in simple energy models) for predicting the MFE folding of an RNA of length n. We demonstrate, for the most common pseudoknot classes, that our automatically generated algorithms achieve the same complexities as reported in the literature for hand-crafted schemes. Our framework supports general energy models, partition function computations, recursive substructures and partial folding, and could pave the way for algebraic dynamic programming beyond the context-free case.

G·U base pairing motifs in long non-coding RNAs

Long non-coding RNAs (lncRNAs) are recently-discovered transcripts involved in gene expression regulation and associated with diseases. Despite the unprecedented molecular complexity of these transcripts, recent studies of the secondary and tertiary structure of lncRNAs are starting to reveal the principles of lncRNA structural organization, with important functional implications. It therefore starts to be possible to analyze lncRNA structures systematically. Here, using a set of prototypical and medically-relevant lncRNAs of known secondary structure, we specifically catalogue the distribution and structural environment of one of the first-identified and most frequently occurring non-canonical Watson-Crick interactions, the G·U base pair. We compare the properties of G·U base pairs in our set of lncRNAs to those of the G·U base pairs in other well-characterized transcripts, like rRNAs, tRNAs, ribozymes, and riboswitches. Furthermore, we discuss how G·U base pairs in these targets participate in establishing interactions with proteins or miRNAs, and how they enable lncRNA tertiary folding by forming intramolecular or metal-ion interactions. Finally, by identifying highly-G·U-enriched regions of yet unknown function in our target lncRNAs, we provide a new rationale for future experimental investigation of these motifs, which will help obtain a more comprehensive understanding of lncRNA functions and molecular mechanisms in the future.

Research on RNA secondary structure predicting via bidirectional recurrent neural network

BACKGROUND

RNA secondary structure prediction is an important research content in the field of biological information. Predicting RNA secondary structure with pseudoknots has been proved to be an NP-hard problem. Traditional machine learning methods can not effectively apply protein sequence information with different sequence lengths to the prediction process due to the constraint of the self model when predicting the RNA secondary structure. In addition, there is a large difference between the number of paired bases and the number of unpaired bases in the RNA sequences, which means the problem of positive and negative sample imbalance is easy to make the model fall into a local optimum. To solve the above problems, this paper proposes a variable-length dynamic bidirectional Gated Recurrent Unit(VLDB GRU) model. The model can accept sequences with different lengths through the introduction of flag vector. The model can also make full use of the base information before and after the predicted base and can avoid losing part of the information due to truncation. Introducing a weight vector to predict the RNA training set by dynamically adjusting each base loss function solves the problem of balanced sample imbalance.

RESULTS

The algorithm proposed in this paper is compared with the existing algorithms on five representative subsets of the data set RNA STRAND. The experimental results show that the accuracy and Matthews correlation coefficient of the method are improved by 4.7% and 11.4%, respectively.

CONCLUSIONS

The flag vector introduced allows the model to effectively use the information before and after the protein sequence; the introduced weight vector solves the problem of unbalanced sample balance. Compared with other algorithms, the LVDB GRU algorithm proposed in this paper has the best detection results.

Predicting RNA secondary structure via adaptive deep recurrent neural networks with energy-based filter

Background

RNA secondary structure prediction is an important issue in structural bioinformatics, and RNA pseudoknotted secondary structure prediction represents an NP-hard problem. Recently, many different machine-learning methods, Markov models, and neural networks have been employed for this problem, with encouraging results regarding their predictive accuracy; however, their performances are usually limited by the requirements of the learning model and over-fitting, which requires use of a fixed number of training features. Because most natural biological sequences have variable lengths, the sequences have to be truncated before the features are employed by the learning model, which not only leads to the loss of information but also destroys biological-sequence integrity.

Results

To address this problem, we propose an adaptive sequence length based on deep-learning model and integrate an energy-based filter to remove the over-fitting base pairs.

Conclusions

Comparative experiments conducted on an authoritative dataset RNA STRAND (RNA secondary STRucture and statistical Analysis Database) revealed a 12% higher accuracy relative to three currently used methods.

A quantitative characterization of interaction between prion protein with nucleic acids

Binding of recombinant prion protein with small highly structured RNAs, prokaryotic and eukaryotic prion protein mRNA pseudoknots, tRNA and polyA has been studied by the change in fluorescence anisotropy of the intrinsic tryptophan groups of the protein. The affinities of these RNAs to the prion protein and the number of sites where the protein binds to the nucleic acids do not vary appreciably although the RNAs have very different compositions and structures. The binding parameters do not depend upon pH of the solution and show a poor co-operativity. The reactants form larger nucleoprotein complexes at pH 5 compared to that at neutral pH. The electrostatic force between the protein and nucleic acids dominates the binding interaction at neutral pH. In contrast, nucleic acid interaction with the incipient nonpolar groups exposed from the structured region of the prion protein dominates the reaction at pH 5. Prion protein of a particular species forms larger complexes with prion protein mRNA pseudoknots of the same species. The structure of the pseudoknots and not their base sequences probably dominates their interaction with prion protein. Possibilities of the conversion of the prion protein to its infectious form in the cytoplasm by nucleic acids have been discussed.

In Silico Prediction of RNA Secondary Structure

The secondary structure of an RNA molecule represents the base-pairing interactions within the molecule and fundamentally determines its overall structure. In this chapter, we overview the main approaches and existing tools for predicting RNA secondary structures, as well as methods for identifying noncoding RNAs from genomic sequences or RNA sequencing data. We then focus on the identification of a well-known class of small noncoding RNAs, namely microRNAs, which play very important roles in many biological processes through regulating post-transcriptionally the expression of genes and which dysregulation has been shown to be involved in several human diseases.

Secondary Structure Predictions for Long RNA Sequences Based on Inversion Excursions and MapReduce

Secondary structures of ribonucleic acid (RNA) molecules play important roles in many biological processes including gene expression and regulation. Experimental observations and computing limitations suggest that we can approach the secondary structure prediction problem for long RNA sequences by segmenting them into shorter chunks, predicting the secondary structures of each chunk individually using existing prediction programs, and then assembling the results to give the structure of the original sequence. The selection of cutting points is a crucial component of the segmenting step. Noting that stem-loops and pseudoknots always contain an inversion, i.e., a stretch of nucleotides followed closely by its inverse complementary sequence, we developed two cutting methods for segmenting long RNA sequences based on inversion excursions: the centered and optimized method. Each step of searching for inversions, chunking, and predictions can be performed in parallel. In this paper we use a MapReduce framework, i.e., Hadoop, to extensively explore meaningful inversion stem lengths and gap sizes for the segmentation and identify correlations between chunking methods and prediction accuracy. We show that for a set of long RNA sequences in the RFAM database, whose secondary structures are known to contain pseudoknots, our approach predicts secondary structures more accurately than methods that do not segment the sequence, when the latter predictions are possible computationally. We also show that, as sequences exceed certain lengths, some programs cannot computationally predict pseudoknots while our chunking methods can. Overall, our predicted structures still retain the accuracy level of the original prediction programs when compared with known experimental secondary structure.

Computational prediction of RNA secondary structure

The purpose of this section is to detail methods for the computational prediction of RNA secondary structure. This protocol is intended to provide an easy entry into the field of RNA structure prediction for those wishing to utilize it in their research and to suggest 'best practices' for going from sequence to secondary structure depending on the available data.