Simulated Annealing for RNA Design with SIMARD.

Ribonucleic acid (RNA) design is the inverse of RNA folding. RNA folding aims to identify the most likely secondary structure into which a given strand of nucleotides will fold. RNA design algorithms, on the other hand, attempt to design a strand of nucleotides that will fold into a specified secondary structure. Despite the apparent NP-hard nature of RNA design, promising results can be achieved when formulated as a combinatorial optimization problem and approached with simple heuristics. The main focus of this paper is to describe an RNA design algorithm based on simulated annealing. Additionally, noteworthy features and results will be presented herein.

Computational approach to predict species-specific type III secretion system (T3SS) effectors using single and multiple genomes.

BACKGROUND: Many gram-negative bacteria use type III secretion systems (T3SSs) to translocate effector proteins into host cells. T3SS effectors can give some bacteria a competitive edge over others within the same environment and can help bacteria to invade the host cells and allow them to multiply rapidly within the host. Therefore, developing efficient methods to identify effectors scattered in bacterial genomes can lead to a better understanding of host-pathogen interactions and ultimately to important medical and biotechnological applications. RESULTS: We used 21 genomic and proteomic attributes to create a precise and reliable T3SS effector prediction method called Genome Search for Effectors Tool (GenSET). Five machine learning algorithms were trained on effectors selected from different organisms and a trained (voting) algorithm was then applied to identify other effectors present in the genome testing sets from the same (GenSET Phase 1) or different (GenSET Phase 2) organism. Although a select group of attributes that included the codon adaptation index, probability of expression in inclusion bodies, N-terminal disorder, and G + C content (filtered) were better at discriminating between positive and negative sets, algorithm performance was better when all 21 attributes (unfiltered) were used. Performance scores (sensitivity, specificity and area under the curve) from GenSET Phase 1 were better than those reported for six published methods. More importantly, GenSET Phase 1 ranked more known effectors (70.3%) in the top 40 ranked proteins and predicted 10-80% more effectors than three available programs in three of the four organisms tested. GenSET Phase 2 predicted 43.8% effectors in the top 40 ranked proteins when tested on four related or unrelated organisms. The lower prediction rates from GenSET Phase 2 may be due to the presence of different translocation signals in effectors from different T3SS families. CONCLUSIONS: The species-specific GenSET Phase 1 method offers an alternative approach to T3SS effector prediction that can be used with other published programs to improve effector predictions. Additionally, our approach can be applied to predict effectors of other secretion systems as long as these effectors have translocation signals embedded in their sequences.

A permutation based simulated annealing algorithm to predict pseudoknotted RNA secondary structures.

Pseudoknots are RNA tertiary structures which perform essential biological functions. This paper discusses SARNA-Predict-pk, a RNA pseudoknotted secondary structure prediction algorithm based on Simulated Annealing (SA). The research presented here extends previous work of SARNA-Predict and further examines the effect of the new algorithm to include prediction of RNA secondary structure with pseudoknots. An evaluation of the performance of SARNA-Predict-pk in terms of prediction accuracy is made via comparison with several state-of-the-art prediction algorithms using 20 individual known structures from seven RNA classes. We measured the sensitivity and specificity of nine prediction algorithms. Three of these are dynamic programming algorithms: Pseudoknot (pknotsRE), NUPACK, and pknotsRG-mfe. One is using the statistical clustering approach: Sfold and the other five are heuristic algorithms: SARNA-Predict-pk, ILM, STAR, IPknot and HotKnots algorithms. The results presented in this paper demonstrate that SARNA-Predict-pk can out-perform other state-of-the-art algorithms in terms of prediction accuracy. This supports the use of the proposed method on pseudoknotted RNA secondary structure prediction of other known structures.

CIG-P: Circular Interaction Graph for Proteomics.

BACKGROUND: A typical affinity purification coupled to mass spectrometry (AP-MS) experiment includes the purification of a target protein (bait) using an antibody and subsequent mass spectrometry analysis of all proteins co-purifying with the bait (aka prey proteins). Like any other systems biology approach, AP-MS experiments generate a lot of data and visualization has been challenging, especially when integrating AP-MS experiments with orthogonal datasets. RESULTS: We present Circular Interaction Graph for Proteomics (CIG-P), which generates circular diagrams for visually appealing final representation of AP-MS data. Through a Java based GUI, the user inputs experimental and reference data as file in csv format. The resulting circular representation can be manipulated live within the GUI before exporting the diagram as vector graphic in pdf format. The strength of CIG-P is the ability to integrate orthogonal datasets with each other, e.g. affinity purification data of kinase PRPF4B in relation to the functional components of the spliceosome. Further, various AP-MS experiments can be compared to each other. CONCLUSIONS: CIG-P aids to present AP-MS data to a wider audience and we envision that the tool finds other applications too, e.g. kinase - substrate relationships as a function of perturbation. CIG-P is available under: http://sourceforge.net/projects/cig-p/

SARNA-Predict: accuracy improvement of RNA secondary structure prediction using permutation-based simulated annealing.

Ribonucleic acid (RNA), a single-stranded linear molecule, is essential to all biological systems. Different regions of the same RNA strand will fold together via base pair interactions to make intricate secondary and tertiary structures that guide crucial homeostatic processes in living organisms. Since the structure of RNA molecules is the key to their function, algorithms for the prediction of RNA structure are of great value. In this article, we demonstrate the usefulness of SARNA-Predict, an RNA secondary structure prediction algorithm based on Simulated Annealing (SA). A performance evaluation of SARNA-Predict in terms of prediction accuracy is made via comparison with eight state-of-the-art RNA prediction algorithms: mfold, Pseudoknot (pknotsRE), NUPACK, pknotsRG-mfe, Sfold, HotKnots, ILM, and STAR. These algorithms are from three different classes: heuristic, dynamic programming, and statistical sampling techniques. An evaluation for the performance of SARNA-Predict in terms of prediction accuracy was verified with native structures. Experiments on 33 individual known structures from eleven RNA classes (tRNA, viral RNA, antigenomic HDV, telomerase RNA, tmRNA, rRNA, RNaseP, 5S rRNA, Group I intron 23S rRNA, Group I intron 16S rRNA, and 16S rRNA) were performed. The results presented in this paper demonstrate that SARNA-Predict can out-perform other state-of-the-art algorithms in terms of prediction accuracy. Furthermore, there is substantial improvement of prediction accuracy by incorporating a more sophisticated thermodynamic model (efn2).

Meta-analysis of small RNA-sequencing errors reveals ubiquitous post-transcriptional RNA modifications.

Recent advances in DNA-sequencing technology have made it possible to obtain large datasets of small RNA sequences. Here we demonstrate that not all non-perfectly matched small RNA sequences are simple technological sequencing errors, but many hold valuable biological information. Analysis of three small RNA datasets originating from Oryza sativa and Arabidopsis thaliana small RNA-sequencing projects demonstrates that many single nucleotide substitution errors overlap when aligning homologous non-identical small RNA sequences. Investigating the sites and identities of substitution errors reveal that many potentially originate as a result of post-transcriptional modifications or RNA editing. Modifications include N1-methyl modified purine nucleotides in tRNA, potential deamination or base substitutions in micro RNAs, 3' micro RNA uridine extensions and 5' micro RNA deletions. Additionally, further analysis of large sequencing datasets reveal that the combined effects of 5' deletions and 3' uridine extensions can alter the specificity by which micro RNAs associate with different Argonaute proteins. Hence, we demonstrate that not all sequencing errors in small RNA datasets are technical artifacts, but that these actually often reveal valuable biological insights to the sites of post-transcriptional RNA modifications.