Motivation: Understanding how nucleic acids interact is essential for understanding their function. Controlling these interactions, for example, can allow us to detect diseases and create new therapeutics. During quantitative reverse-transcription polymerase chain reaction (qRT-PCR) testing, having nucleic acids interact as designed is essential for ensuring accurate test results. Accurate testing is an important consideration during the detection of COVID-19, the disease caused by the severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). Results: I introduced the program DinoKnot (Duplex Interaction of Nucleic acids with pseudoKnots) that follows the hierarchical folding hypothesis to predict the secondary structure of two interacting nucleic acid strands (DNA/RNA) of similar or different type. DinoKnot is the first program that utilizes stable stems in both strands as a guide to find the structure of their interaction. Using DinoKnot, I predicted the interaction structure between the SARS-CoV-2 genome and nine reverse primers from qRT-PCR primer-probe sets. I compared these results to an existing tool RNAcofold and highlighted an example to showcase DinoKnot’s ability to predict pseudoknotted structures. I investigated how mutations to the SARS-CoV-2 genome may affect the primer interaction and predicted three mutations that may prevent primer binding, reducing the ability for SARS-CoV-2 detection. Interaction structure results pre- dicted by DinoKnot that showed disruption of primer binding were consistent with a clinical example showing detection issues due to mutations. DinoKnot has the potential to screen new SARS-CoV-2 variants for possible detection issues and support existing applications involving DNA/RNA interactions, such as microRNA (miRNA) target site prediction, by adding structural considerations to the interaction to elicit functional information. / Graduate

Background: RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, spaceefficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models. Results: Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by n2, but are typically much smaller. The time complexity of RNA folding is reduced from O(n3) to O(n2 + nZ); the space complexity, from O(n2) to O(n + T + Z). Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases). Conclusions: The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA–RNA-interaction prediction are expected to profit even stronger than \"standard\" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.unileipzig. de/~will/Software/SparseMFEFold.

A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral. No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora / The theory of formal languages is widely used to solve problems of different natures as it can deal with artificial and natural languages. The grammars, formalisms able to synthesize languages, can also be used in pattern recognition problems due to the ability to model the language components hierarchies, decomposing patterns in substructures. Based on this idea, the framework GrammarLab was designed to facilitate the work involved in implementing, generating and testing different grammar based sequence classifiers, providing regular and context free grammar in the prior version. However, some problems need a formalism that can be found only in higher classes of grammars in the Chomsky hierarchy. The problem of using a higher class of grammar is the high computational time complexity for parsing. While the problem of recognizing sequences using regular and context free grammars is solved at polynomial time, the same problem in general case is NP-Complete for context sensitive grammars and undecidable for unrestricted grammars. Nevertheless, the use of adaptive methods allows a grammar to alter the set of production rules during sentences generation, including context sensitivity even to grammars that were designed to be context free, without increasing the polynomial parsing complexity. This work was focused in improving the GrammarLab framework by including the ability to deal with adaptive methods and in the creation of an adaptive version of Earleys algorithm. To test the solution in real world problems, it was conducted a preliminary study of the use of the framework in characterizing RNA functional families with conserved secondary structure, including pseudoknots. The pseudoknot pattern, represented by crossing dependences among RNA sequence nucleotides, is an example of context dependence, so it is a good test case for the use of a model that consider adaptability in the constitution. The obtained results with two families of RNAs with pseudoknots show that the approach is promising

A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral. No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora / The theory of formal languages is widely used to solve problems of different natures as it can deal with artificial and natural languages. The grammars, formalisms able to synthesize languages, can also be used in pattern recognition problems due to the ability to model the language components hierarchies, decomposing patterns in substructures. Based on this idea, the framework GrammarLab was designed to facilitate the work involved in implementing, generating and testing different grammar based sequence classifiers, providing regular and context free grammar in the prior version. However, some problems need a formalism that can be found only in higher classes of grammars in the Chomsky hierarchy. The problem of using a higher class of grammar is the high computational time complexity for parsing. While the problem of recognizing sequences using regular and context free grammars is solved at polynomial time, the same problem in general case is NP-Complete for context sensitive grammars and undecidable for unrestricted grammars. Nevertheless, the use of adaptive methods allows a grammar to alter the set of production rules during sentences generation, including context sensitivity even to grammars that were designed to be context free, without increasing the polynomial parsing complexity. This work was focused in improving the GrammarLab framework by including the ability to deal with adaptive methods and in the creation of an adaptive version of Earleys algorithm. To test the solution in real world problems, it was conducted a preliminary study of the use of the framework in characterizing RNA functional families with conserved secondary structure, including pseudoknots. The pseudoknot pattern, represented by crossing dependences among RNA sequence nucleotides, is an example of context dependence, so it is a good test case for the use of a model that consider adaptability in the constitution. The obtained results with two families of RNAs with pseudoknots show that the approach is promising

Double-stranded RNA fungal virus Helminthosporium victoriae virus 190S (genus Victorivirus, family Totiviridae) contains two large open reading frames (ORFs) that overlap in the tetranucleotide AUGA. Translation of the downstream ORF, which encodes the RNA-dependent RNA polymerase (RdRp), was previously proposed to depend on ribosomal reinitiation following termination of the upstream ORF, which encodes the capsid protein. In this study, I provided evidence to confirm that coupled termination-reinitiation (stop-restart) is indeed used. A dual-fluorescence method was established to define the RNA sequence determinants for RdRp translation. Stop-restart depends on a 32-nt stretch of RNA sequence immediately upstream of the AUGA motif, including a predicted pseudoknot structure. The presence of similar sequence motifs and predicted RNA structures in other victoriviruses suggest that they all share a related stop–restart strategy for RdRp translation. The close proximity of the secondary structure to the AUGA motif appears to be especially important for promoting translation of the downstream ORF. Normal strong preferences for AUG start codons and canonical sequence context for translation initiation of the downstream ORF appear somewhat relaxed. With dual-fluorescence system, reinitiation efficiency of the downstream ORF was determined to be ~3.9%. Pseudoknot swapping between the one in HvV190S and those predicted from other victoriviruses showed that reinitiation from the downstream ORF of HvV190S is quite tolerant to varying primary sequences of the various pseudoknots. Mutational analysis by introducing different combinations of nucleotide mutations into pseudoknot stems reproducibly confirmed the determinant role of pseudoknot on reinitiation using two different experimental systems. Together, these results provide the first example of coupled termination-reinitiation regulated by a simple pseudoknot stucture. These data expanded the understanding of coupled termination-reinitiation mechanism employed by RNA viruses and refined a new model for genus victorivirus, the largest genus in the family Totiviridae. The dual fluorescence system used in this study represented the first application of an efficient in vivo assay for recording low-frequency events in filamentous fungi.

De nombreuses recherches ont constaté l'importance des molécules d'ARN, car ils jouent un rôle vital dans beaucoup de procédures moléculaires. Et il est accepté généralement que les structures des molécules d'ARN sont la clé de la découverte de leurs fonctions.Au cours de l'enquête de structures d'ARN, les chercheurs dépendent des méthodes bioinformatiques de plus en plus. Beaucoup de méthodes in silico de prédiction des structures secondaires d'ARN ont émergé dans cette grosse vague, y compris certains qui sont capables de prédire pseudonoeuds, un type particulier de structures secondaires d'ARN.Le but de ce travail est d'essayer de comparer les méthodes de l'état de l'art pour prédiction de pseudonoeud, et offrir aux collègues des idées sur le choix d’une méthode pratique pour la seule séquence donnée. En fait, beaucoup d'efforts ont été fait dans la prédiction des structures secondaires d'ARN parmi lesquelles le pseudonoeud les dernières décennies, contribuant à de nombreux programmes dans ce domaine. Certaines enjeux sont soulevées conséquemment. Comment est-elle la performance de chaque méthode, en particulier sur une classe de séquences d'ARN particulière? Quels sont leurs pour et contre? Que pout-on profiter des méthodes contemporaines si on veut développer de nouvelles? Cette thèse a la confiance dans l'enquête sur les réponses.Cette thèse porte sur très nombreuses comparaisons de la performance de prédire pseudonoeuds d'ARN par les méthodes disponibles. Une partie principale se concentre sur la prédiction de signaux de déphasage par deux méthodes principalement. La deuxième partie principale se concentre sur la prédiction de pseudonoeuds qui participent à des activités moléculaires beaucoup plus générale.Dans le détail, la deuxième partie du travail comprend 414 pseudonoeuds de Pseudobase et de la Protein Data Bank, ainsi que 15 méthodes dont 3 méthodes exactes et 12 heuristiques. Plus précisément, trois grandes catégories de mesures complexes sont introduites, qui divisent encore les 414 pseudonoeuds en une série de sous-classes respectivement.Les comparaisons se passent par comparer les prédictions de chaque méthode basée sur l'ensemble des 414 pseudonœuds, et les sous-ensembles qui sont classés par les deux mesures complexes et la longueur, le type de l'ARN et de l'organisme des pseudonœuds.Le résultat montre que les pseudo-noeuds portent une complexité relativement faible dans toutes les mesures. Et la performance des méthodes modernes varie de sous-classe à l’autre, mais diminue constamment lors que la complexité de pseudonoeuds augmente. Plus généralement, les méthodes heuristiques sont supérieurs globalement à celles exacts. Et les résultats de l'évaluation sensibles sont dépendants fortement de la qualité de structure de référence et le système d'évaluation. Enfin, cette partie du travail est fourni comme une référence en ligne pour la communauté bioinformatique. / Lots of researches convey the importance of the RNA molecules, as they play vital roles in many molecular procedures. And it is commonly believed that the structures of the RNA molecules hold the key to the discovery of their functions.During the investigation of RNA structures, the researchers are dependent on the bioinformatical methods increasingly. Many in silico methods of predicting RNA secondary structures have emerged in this big wave, including some ones which are capable of predicting pseudoknots, a particular type of RNA secondary structures.The purpose of this dissertation is to try to compare the state-of-the-art methods predicting pseudoknots, and offer the colleagues some insights into how to choose a practical method for the given single sequence. In fact, lots of efforts have been done into the prediction of RNA secondary structures including pseudoknots during the last decades, contributing to many programs in this field. Some challenging questions are raised consequently. How about the performance of each method, especially on a particular class of RNA sequences? What are their advantages and disadvantages? What can we benefit from the contemporary methods if we want to develop new ones? This dissertation holds the confidence in the investigation of the answers.This dissertation carries out quite many comparisons of the performance of predicting RNA pseudoknots by the available methods. One main part focuses on the prediction of frameshifting signals by two methods principally. The second main part focuses on the prediction of pseudoknots which participate in much more general molecular activities.In detail, the second part of work includes 414 pseudoknots, from both the Pseudobase and the Protein Data Bank, and 15 methods including 3 exact methods and 12 heuristic ones. Specifically, three main categories of complexity measurements are introduced, which further divide the 414 pseudoknots into a series of subclasses respectively. The comparisons are carried out by comparing the predictions of each method based on the entire 414 pseudoknots, and the subsets which are classified by both the complexity measurements and the length, RNA type and organism of the pseudoknots.The result shows that the pseudoknots in nature hold a relatively low complexity in all measurements. And the performance of contemporary methods varies from subclass to subclass, but decreases consistently as the complexity of pseudoknots increases. More generally, the heuristic methods globally outperform the exact ones. And the susceptible assessment results are dependent strongly on the quality of the reference structures and the evaluation system. Last but not least, this part of work is provided as an on-line benchmark for the bioinformatics community.

The repertoire of cellular functions mediated by Ribonucleic acid (RNA) molecules have expanded considerably during the last two decades. The role played by RNA in controlling and regulating gene expression in viruses, prokaryotes and eukaryotes has been a matter of continuous investigations. This interest has arisen primarily due to the discoveries of cisacting RNA structures like riboswitches, ribosensors and frameshift elements, which are found in either the 5’-, 3’-untranslated regions of mRNA or in the open reading frames. These structures control gene expression at the level of translation by either sequestering the Shine-Dalgarno (SD) sequence to regulate translation initiation or modulating ribosomal positions during an active translation process. Very often, these structures comprise of an RNA pseudoknot and it has been observed that these pseudoknots exist in a dynamic equilibrium with other intermediate structures. This equilibrium could be shifted by several factors including presence of ions, metabolites, temperature and external force. RNA pseudoknots represent the most versatile and ubiquitous class of RNA structures in the cell, whose unique folding topology could be exploited in a number of ways by the cellular machinery. In this thesis, a thorough study of programmed -1 ribosomal frameshifting (-1 PRF) process, which is a well known gene regulation event employed by many RNA viruses, was carried out. -1 PRF is a translation recoding process, necessary for viruses to main-tain a stoichiometric ratio of structural: enzymatic proteins. This ratio varies among different viral species. At the heart of this process, lies an RNA pseudoknot accompanied by a seven nucleotide long sequence motif, which pauses an actively translating ribosome on mRNA and causes it to shift its reading frame. The frameshift inducing efficiency of pseudoknot depends on multiple factors, for example the time scale of ribosomal pause and RNA unfolding, subsequent refolding of structure to native/intermediate states and/or environment conditions. With the aim of illustrating the fundamentals of the process, multiple factors involved in -1 PRF were studied. Chapters 2-4 represent distinct aspects of -1 PRF process, while Chapter 5 discusses a different work concerned with nucleocytoplasmic transport of tRNA carried out by nuclear export receptor Exporting. Chapter 1 gives an overview of the different regulatory activities with which RNA structures and sequences are found to be associated and the evolution of these stud-ies. It discusses the different types of structural motifs found to constitute tertiary RNA structure and secondary structure prediction and determination techniques. A brief description of ab initio RNA structure modeling and other relevant tools and methodologies used in this work has been presented. Details of techniques used in each study have been provided in relevant chapters. Chapter 2 describes how local factors like ionic conditions, hydration patterns, presence of protonated residues and single residue mutations affect the structural dynamics of an RNA pseudoknot involved in -1 PRF from a plant luteovirus. Single residue mutations in the loop regions or certain base-pair inversions in the stem regions of pseudoknot increase the frameshift inducing ability of the pseudoknot structure, while some others decrease this efficiency. However, it was not clear how the changes made to the wild-type (WT) RNA pseudoknot from Beet Western Yellow Mosaic virus were affecting the global structure in terms of its dynamics and other parameters. To study this, multiple all-atom molecular dynamics simulations (MD) were performed on WT and mutant structures created in silico. The effect of presence and absence of magnesium ions on the structural geometry was also studied. The analysis was done to identify the increase/decrease in the number of hydrogen bonds formed by Watson-Crick base-pairs in stem region or non Watson-Crick pairs between stem and loop. Ionic and water densities were analyzed and the role of potential ribosome-pseudoknot interaction was elaborated. With the aim of mimicking ribosome induced unfolding of an RNA pseudoknot, steered molecular dynamics pulling experiments were performed. This work was done primarily to understand the unfolding pathway of Hairpin(H)-type pseudoknots in general and the intermediate structures formed. Chapter 3 describes the thermodynamics and mechanics associated with the mechanical pulling of -1 PRF inducing RNA pseudoknot and its mutants described in previous chapter. Analysis of the trajectories reveal relative unfolding patterns in terms of disruption of various hydrogen bonds. This study allowed us to pinpoint the kind of intermediate structures being formed during pulling and whether these intermediate structures correspond to any known secondary structures, such as simple stem-loops. This information could be used for gaining insights into the folding pathways of these structures. An RNA pseudoknot stimulates -1 PRF in conjunction with a heptanucleotide “slippery site” and an intervening spacer sequence. A comprehensive study of analyzing the sequence signatures and composition of all overlapping gene segments harboring these frameshift elements from four different RNA virus families was carried out. Chapter 4 describes the sequence composition of all overlapping gene segments in Astroviridae, Coronaviridae, Retroviridae and Luteoviridae viral families which are known to employ -1 PRF process for maintaining their protein products. Sequence analysis revealed preference for GC bases in the structure forming sequence regions. A comparative study between multiple sequence alignment and secondary structure prediction revealed that while pseudoknots have a clear preference for specific base-pairs in their stem regions, viral families that employ a hairpin loop as -1 PRF structure, doesn’t show this preference. Information derived from secondary structure prediction was then used for RNA ab initio modeling to generate tertiary structures. Furthermore, the structural parameters were calculated for the helices of the frameshift inducing pseudoknots and were compared with the values calculated for a set of non -1 PRF inducing H-type pseudo-knots. This study highlighted the differences between -1 PRF pseudoknots and other H-type pseudoknot structures as well as specific sequence and structural preferences of the former. Chapter 5 discusses the dynamics of a tRNA transport factor Exportint (Xpot), which transports mature tRNA molecules from nucleus to cytoplasm and belongs to Importitβ family of proteins. The global conformational dynamics of other transport receptors has been reported earlier, using coarse-grained modeling and Elastic Network Models (ENMs), but a detailed description of the dynamics at an all-atomic resolution was lacking. This transport requires association of Xpot with RanGTP, a G-protein, in the nucleus and hydrolysis of RanGTP in the cytoplasm. The chain of events leading to tRNA release from Xpot after RanGTP hydrolysis was not studied previously. With these objectives, several molecular complexes containing Xpot bound to Ran or tRNA or both in the GTP and GDP ligand states as well as free Xpot structures in nuclear and cytosolic forms were studied. A combination of conventional and accelerated molecular dynamics simulations was used to study these molecular complexes. The study highlighted various aspects associated with tRNA release and conformational change which occurs in Xpot in cytosolic form. The nuclear to cytosolic state transition in Xpot could be attributed to large fluctuations in C-terminal region and dynamic hinge-points located between specific HEAT repeats. A secondary role of Xpot in controlling the quality of tRNA transport has been proposed based on multiple sequence and structure alignment with Importin-β protein. The loss of critical contacts like hydrogen bonds and salt bridges between Xpot/Ran and Xpot/tRNA interface was evaluated in order to study the initial effects of RanGTP hydrolysis and how it influences receptor-cargo binding. This study revealed various aspects of tRNA transport process by Xpot, not understood previously. The results presented in this thesis illustrate the role of RNA sequence elements and pseudoknots present in RNA viruses in modulating -1 PRF process and how multiple environmental factors affect -1 PRF inducing ability of the structure. From the studies of Xpot and its complexes, the effects of GTP hydrolysis leading to tRNA dissociation have been presented and the progression of conformational transition in Xpot after tRNA dissociation has been highlighted. Chapter 6 summarizes major conclusions of this thesis work. The refolding of single stranded RNA chains, subjected to a previous unfolding simulation is studied. Appendix A describes this work and initial results. Appendix B describes the effect of improved molecular dynamics force fields, containing corrections for χ torsion angle for RNA, on the conformation of tertiary RNA structures. Part of the work presented in this thesis has been reported in the following publications. 1.Asmita Gupta and Manju Bansal. Local Structural and Environmental Factors De-fine the Efficiency of an RNA Pseudoknot Involved in Programmed Ribosomal Frameshift Process. J. Phys. Chem. B. 118 (41), pp 11905-11920. 2014 2.Asmita Gupta, Senthilkumar Kailasam and Manju Bansal. Insights Into Nucleo-cytoplasmic Transport of tRNA by Exportin-t. Manuscript under review. List of manuscripts that are being prepared from the work reported in Chapter 3 in this thesis. 1 Asmita Gupta and Manju Bansal. The role of sequence effects on altering the un-folding pathway of an RNA pseudoknot: a steered molecular dynamics study. Manuscript in preparation. 2 Asmita Gupta and Manju Bansal. Molecular basis for nucleocytoplasmic transport of tRNA by Exportin-t. Journal of Biomolecular Structure and Dynamics, May;33 Suppl 1:59-60, 2015

In eubacteria, ribosome stalling on broken messenger RNA transcripts can lead to cell death. The trans-translation quality control mechanism rescues many of these stalled ribosomes. In this process, tmRNA enters stalled ribosomes by mimicking a transfer RNA, accepting the stalled nascent peptide. The ribosome then releases the broken mRNA and resumes translation on a coding region within tmRNA itself. Translation of tmRNA marks the nascent peptide for destruction by the addition of a short proteolysis tag and the ribosome is released at a stop codon within the tmRNA open reading frame. An intriguing aspect of trans-translation is that the ribosome synthesizes one protein from two RNA templates. How is the proper site chosen on tmRNA to resume translation? Do the conserved pseudoknot structures help set the reading frame? Using a genetic selection to assay libraries of tmRNA mutants, we found that stable hairpin structures can functionally replace pseudoknot 1. We conclude that the role of pseudoknot 1 in tmRNA function is purely structural. Our results demonstrate that the inactivity of an RNA mutant designed to destroy a given structure should not be interpreted as proof that the structure is necessary for RNA function. Such mutations may only destabilize a global fold that could be formed equally well by an entirely different, stable structure. Broken mRNAs are not the only cause of ribosome stalling; stalling can also result from nascent peptide interactions with the ribosomal exit tunnel that inhibit peptidyl-transferase activity. SecM, TnaC, and ErmCL all stall ribosomes to regulate the expression of downstream genes. What other peptide sequences can cause ribosome stalling? We modified our tmRNA-based selection to screen libraries of random peptides and identified a number of novel stalling peptides, including the sequence FxxYxIWPP. This sequence interacts with the exit tunnel differently than SecM and TnaC as seen in studies using mutant ribosomes. Like SecM, stalling occurs on this sequence with the next aminoacyl tRNA trapped in the A site but unable to react with the nascent peptide. These results show that a variety of peptides can interact in the exit tunnel and peptidyl-transferase center to regulate ribosome activity.

Background: RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, spaceefficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models. Results: Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by n2, but are typically much smaller. The time complexity of RNA folding is reduced from O(n3) to O(n2 + nZ); the space complexity, from O(n2) to O(n + T + Z). Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases). Conclusions: The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA–RNA-interaction prediction are expected to profit even stronger than \"standard\" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.unileipzig. de/~will/Software/SparseMFEFold.