Safe and Complete Prediction of RNA Secondary Structure

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-202001271159
Title: Safe and Complete Prediction of RNA Secondary Structure
Author: Kiirala, Niko
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2020
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-202001271159
http://hdl.handle.net/10138/310408
Thesis level: master's thesis
Discipline: Tietojenkäsittelytiede
Abstract: Ribonucleic acid, RNA, is an essential type of molecule for all known forms of life. It is a nucleic acid, like DNA. However, where DNA appears as two complementary strands that join and twist into a double helix structure, RNA has only a single strand. This strand can fold upon itself, pairing complementary bases. The resulting set of base pairs is the RNA secondary structure, also known as folding. It is typical that a prediction algorithm gives a large number of optimal or near-optimal foldings for an RNA sequence. Only in the simplest cases it is possible to manually go through all of these foldings, and in hard cases it is infeasible to even generate the full set of optimal foldings. In fact, we observe that the number of optimal foldings may be exponential in the sequence length, and that some naturally occurring RNA sequences of 2000–3000 bases in length have well over 10^100 optimal foldings, under the model of maximizing the number of base pairs. To help analyze the full set of optimal foldings, we apply the concept of safe and complete algorithms. In the presence of multiple optimal solutions, any partial solution that appears in all optimal solutions is called a safe part, and a safe and complete algorithm finds all of the safe parts. We show a trivial safe and complete algorithm that computes safety by going through the full set of optimal foldings. However, this algorithm is only practical for short RNA sequences that do not have too many optimal foldings. In order to analyze the harder RNA sequences, we develop and implement a novel polynomial-time safe and complete algorithm for RNA secondary structure prediction, using the model of maximizing base pairs. Using the dynamic programming approach, this new algorithm can compute how often each base pair and unpaired base appears in the full set of optimal foldings without having to produce the actual foldings. Our experimental evaluation shows that the safe parts of a folding are more likely to be biologically correct than the non-safe parts. We observe this both by using our implementation of the efficient safe and complete algorithm and by combining an existing predictor program with the trivial algorithm. As this existing predictor uses a modern minimum free energy model for predicting the RNA foldings, tests using this combination show that safety is a useful property, even beyond the simple maximum pairs model in our implementation.


Files in this item

Total number of downloads: Loading...

Files Size Format View
Kiirala_Niko_Pro_gradu_2019.pdf 955.1Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record