Predicting RNA secondary structure using a stochastic conjunctive grammar

Abstract

In this thesis I extend a class of grammars called conjunctive grammars to a stochastic form called stochastic conjunctive grammars. This extension allows the grammars to predict pseudoknotted RNA secondary structure. Since observing sec- ondary structure is hard and expensive to do with today's technology, there is a need for computational solutions to this problem. A conjunctive grammar can handle pseudoknotted structure because of the way one sequence is generated by combining multiple parse trees. I create several grammars that are designed to predict pseudoknotted RNA sec- ondary structure. One grammar is designed to predict all types of pseudoknots and the others are made to only predict a pseudoknot called H-type. These grammars are trained and tested and the results are collected. I am able to obtain a sensitivity of over 75% and a speci city of over 89% on H-type pseudoknots