No description available.

Thesis advisor: Peter Clote / RNA folding pathways play an important role in various biological processes, such as 1) the conformational switch in spliced leader RNA from Leptomonas collosoma, which controls transsplicing of a portion of the 5’ exon, and 2) riboswitches–portions of the 5’ untranslated region of mRNA that regulate genes by allostery. Since RNA folding pathways are determined by the thermodynamic landscape, we have developed a number of novel algorithms—including FFTbor and FFTbor2D—which efficiently compute the coarse-grained energy landscape for a given RNA sequence. These energy landscapes can then be used to produce a model for RNA folding kinetics that can compute both the mean first passage time (MFPT) and equilibrium time in a deterministic and efficient manner, using a new software package we call Hermes. The speed of the software provided within Hermes—namely FFTmfpt and FFTeq—present what we believe to be the first suite of kinetic analysis tools for RNA sequences that are suitable for high throughput usage, something we believe to be of interest in the field of synthetic design. / Thesis (PhD) — Boston College, 2015. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Biology.

Many methods can be used to predict the secondary structure of an RNA sequence. One of the methods is the dynamic programming approach. However, the dynamic programming approach takes too much time. Thus, it is not practical to solve the problem of long sequences with dynamic programming. RAGA (RNA Sequence Alignment by the Genetic Algorithm) is a genetic algorithm to align two similar sequences that the structure of one of them (master sequence) is known and another (slave sequence) is unknown. We can predict an RNA sequence by analyzing several homologous sequence alignment. In this thesis, we add an operator to mutate the residues of the base pairs in the master sequence and realign two sequences again. We compare our operator with other traditional operators, such as crossover and mutation. The experiment results show that our new operator gets a big improvement.

Thesis advisor: Peter Clote / RNA molecules play important roles in living organisms, such as protein translation, gene regulation, and RNA processing. It is known that RNA secondary structure is a scaffold for tertiary structure leading to extensive amount of interest in RNA secondary structure. This thesis is primarily focused on the development of novel algorithms for the analysis of RNA secondary structure evolution and folding kinetics. We describe a software RNAsampleCDS to generate mRNA sequences coding user-specified peptides overlapping in up to six open reading frames. Sampled mRNAs are then analyzed with other tools to provide an estimate of their secondary structure properties. We investigate homology of RNAs with respect to both sequence and secondary structure information as well. RNAmountAlign an efficient software package for multiple global, local, and semiglobal alignment of RNAs using a weighted combination of sequence and structural similarity with statistical support is presented. Furthermore, we approach RNA folding kinetics from a novel network perspective, presenting algorithms for the shortest path and expected degree of nodes in the network of all secondary structures of an RNA. In these algorithms we consider move set MS2 , allowing addition, removal and shift of base pairs used by several widely-used RNA secondary structure folding kinetics software that implement Gillespie’s algorithm. We describe MS2distance software to compute the shortest MS2 folding trajectory between any two given RNA secondary structures. Moreover, RNAdegree software implements the first algorithm to efficiently compute the expected degree of an RNA MS2 network of secondary structures. The source code for all the software and webservers for RNAmountAlign, MS2distance, and RNAdegree are publicly available at http://bioinformatics.bc.edu/clotelab/. / Thesis (PhD) — Boston College, 2018. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Biology.

Thesis advisor: Michelle M. Meyer / Thesis advisor: Peter Clote / Structured RNAs have many biological functions ranging from catalysis of chemical reactions to gene regulation. Many of these homologous structured RNAs display most of their conservation at the secondary or tertiary structure level. As a result, strategies for natural structured RNA discovery rely heavily on identification of sequences sharing a common stable secondary structure. However, correctly identifying the functional elements of the structure continues to be challenging. In addition to studying natural RNAs, we improve our ability to distinguish functional elements by studying sequences derived from in vitro selection experiments to select structured RNAs that bind specific proteins. In this thesis, we seek to improve methods for distinguishing functional RNA structures from arbitrarily predicted structures in sequencing data. To do so, we developed novel algorithms that prioritize the structural properties of the RNA that are under selection. In order to identify natural structured ncRNAs, we bring concepts from evolutionary biology to bear on the de novo RNA discovery process. Since there is selective pressure to maintain the structure, we apply molecular evolution concepts such as neutrality to identify functional RNA structures. We hypothesize that alignments corresponding to structured RNAs should consist of neutral sequences. During the course of this work, we developed a novel measure of neutrality, the structure ensemble neutrality (SEN), which calculates neutrality by averaging the magnitude of structure retained over all single point mutations to a given sequence. In order to analyze in vitro selection data for RNA-protein binding motifs, we developed a novel framework that identifies enriched substructures in the sequence pool. Our method accounts for both sequence and structure components by abstracting the overall secondary structure into smaller substructures composed of a single base-pair stack. Unlike many current tools, our algorithm is designed to deal with the large data sets coming from high-throughput sequencing. In conclusion, our algorithms have similar performance to existing programs. However, unlike previous methods, our algorithms are designed to leverage the evolutionary selective pressures in order to emphasize functional structure conservation. / Thesis (PhD) — Boston College, 2016. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Biology.

RNA molecules play important roles, including catalysis of chemical reactions and control of gene expression, and their functions largely depend on their folded structures. Since determining these structures by biochemical means is expensive, there is increased demand for computational predictions of RNA structures. One computational approach is to find the secondary structure (a set of base pairs) that minimizes a free energy function for a given RNA conformation. The forces driving RNA folding can be approximated by means of a free energy model, which associates a free energy parameter to a distinct considered feature. The main goal of this thesis is to develop state-of-the-art computational approaches that can significantly increase the accuracy (i.e., maximize the number of correctly predicted base pairs) of RNA secondary structure prediction methods, by improving and refining the parameters of the underlying RNA free energy model. We propose two general approaches to estimate RNA free energy parameters. The Constraint Generation (CG) approach is based on iteratively generating constraints that enforce known structures to have energies lower than other structures for the same molecule. The Boltzmann Likelihood (BL) approach infers a set of RNA free energy parameters which maximize the conditional likelihood of a set of known RNA structures. We discuss several variants and extensions of these two approaches, including a linear Gaussian Bayesian network that defines relationships between features. Overall, BL gives slightly better results than CG, but it is over ten times more expensive to run. In addition, CG requires software that is much simpler to implement. We obtain significant improvements in the accuracy of RNA minimum free energy secondary structure prediction with and without pseudoknots (regions of non-nested base pairs), when measured on large sets of RNA molecules with known structures. For the Turner model, which has been the gold-standard model without pseudoknots for more than a decade, the average prediction accuracy of our new parameters increases from 60% to 71%. For two models with pseudoknots, we obtain an increase of 9% and 6%, respectively. To the best of our knowledge, our parameters are currently state-of-the-art for the three considered models.

Sequence alignment is a basic but powerful technique in molecular biology. Macromolecular sequences (DNA, RNA and protein sequences) can be aligned based on some criteria. The goal of sequence alignment is to find the similarity and the difference of input sequences. With various purposes, there are different algorithms In this thesis, we present a new algorithm which aligns sequences with consideration of secondary structures. Traditionally, a sequence alignment algorithm considers only the primary structure, which is the amino acid chain. When we make use of the information of protein secondary structure such as alpha helix, beta sheet etc, the sensitivity of pairwise alignment can be improved.

Ribosomal RNA (rRNA) molecules form highly conserved secondary and tertiary structures via rRNA-rRNA and rRNA-protein interactions that collectively comprise the macromolecule that is the ribosome. Because of their cellular universality, rRNA molecules are commonly used for phylogeny estimations spanning all divergences of life. In this dissertation, I elucidate the structure of several rRNAs by analyzing multiply aligned sequences for basepair covariation and conserved higher order structural motifs. Specifically, I predict novel structures for expansion segments D2 and D3 of the nuclear large subunit rRNA (28S) and variable regions V4-V9 of the nuclear small subunit rRNA (18S) from from 249 galerucine leaf beetles (Coleoptera: Chrysomelidae). I describe a novel means for characterizing regions of alignment ambiguity that improves methods for retaining phylogenetic information without violating nucleotide positional homology. In the program PHASE, I explore a variety of RNA maximum likelihood models using the 28S rRNA dataset and discuss the utitilty of these models in light of their performance under Bayesian analysis. I conclude that seven-state models are likely the best models to use for phylogenetic estimation, although I cannot determine with confidence which of the two seven-state models (7A or 7D) is better. Evaluation of the unpaired sites within both rRNAs in Modeltest provided a similar model of evolution for these non-pairing regions (TrN+ I+G). In addition, a sequenced region of the mitochondrial cytochrome oxidase I gene (COI) from the galerucines was evaluated in Modeltest, with each codon position modeled separately (GTR+I+G for positions 1 and 2, GTR+G for position 3). The combined galerucine dataset (28S+18S rRNA helices, 28S+18S rRNA unpaired sites, COI 1st, 2nd and 3rd positions) provided for two mixedmodel Bayesian analysis of five discretely-modeled partitions (using 7A and 7D). The results of these analyses are compared with those obtained from equally weighted parsimony to provide a robust phylogenetic estimate of the Galerucinae and related leaf beetle taxa. Finally, the odd characteristics of strepsipteran 18S rRNA are evaluated through comparison of 12 strepsipterans with 163 structurally-aligned arthropod sequences. Among other interesting results, I identify errors in previously published strepsipteran sequences and predict structures not previously known from metazoan rRNA.

RNA molecules play important roles, including catalysis of chemical reactions and control of gene expression, and their functions largely depend on their folded structures. Since determining these structures by biochemical means is expensive, there is increased demand for computational predictions of RNA structures. One computational approach is to find the secondary structure (a set of base pairs) that minimizes a free energy function for a given RNA conformation. The forces driving RNA folding can be approximated by means of a free energy model, which associates a free energy parameter to a distinct considered feature. The main goal of this thesis is to develop state-of-the-art computational approaches that can significantly increase the accuracy (i.e., maximize the number of correctly predicted base pairs) of RNA secondary structure prediction methods, by improving and refining the parameters of the underlying RNA free energy model. We propose two general approaches to estimate RNA free energy parameters. The Constraint Generation (CG) approach is based on iteratively generating constraints that enforce known structures to have energies lower than other structures for the same molecule. The Boltzmann Likelihood (BL) approach infers a set of RNA free energy parameters which maximize the conditional likelihood of a set of known RNA structures. We discuss several variants and extensions of these two approaches, including a linear Gaussian Bayesian network that defines relationships between features. Overall, BL gives slightly better results than CG, but it is over ten times more expensive to run. In addition, CG requires software that is much simpler to implement. We obtain significant improvements in the accuracy of RNA minimum free energy secondary structure prediction with and without pseudoknots (regions of non-nested base pairs), when measured on large sets of RNA molecules with known structures. For the Turner model, which has been the gold-standard model without pseudoknots for more than a decade, the average prediction accuracy of our new parameters increases from 60% to 71%. For two models with pseudoknots, we obtain an increase of 9% and 6%, respectively. To the best of our knowledge, our parameters are currently state-of-the-art for the three considered models.

A brief explanation of RNA and its general structure on dierent levels is given. The standard continuous Frenet frame is explained. A discrete version of the Frenet frame is explained in detail and constructed for a piecewise linear curve. The results of the application of the discrete Frenet frame to RNA is shown in the form of several distributions. An analysis of these distributions is conducted and gives some results regarding tiny structures in RNA. / <p>Master Degree Project thesis</p>