Structure-function relationship mining of RNA

Submission note: A thesis submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the Department of Computer Science and Information Technology, School of Engineering and Mathematical Sciences, College of Science, Health and Engineering, La Trobe University, Bundoora.

This thesis presents a new pairwise RNA secondary structure alignment heuristics, and a method to discover the frequent stem patterns in a set of RNA secondary structures. The proposed heuristics are able to efficiently compare a pair of structures containing arbitrary pseudoknots, including the topologically complex ones found from the pseudoknot complexity investigation. Such complex pseudoknots cause the intractability problem for secondary structure alignment, as well as many other structural analyses. Benchmarks results suggest that this heuristics produced better alignments than some existing alignment tools, and good alignments between these complex pseudoknots were also observed. Meanwhile, the intermediate stem matching results generated by the heuristics are utilized to derive the frequent stem patterns in a set of evolutionary similar secondary structures. The patterns discovered represent potential conserved structures which are likely to be related to the noncoding functions in ncRNAs. They also provide biological insights to the relationships between structure conservation and evolution in specific RNA families. Finally, for other RNA secondary structure analyses accepting only pseudoknot-free structures as inputs, a new pre-processing approach is also developed to remove any pseudoknots in the input structures according to specific criteria. It has been shown to be more efficient and flexible than the state-of-the-art method.