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.
The thesis author retains all proprietary rights (such as copyright and patent rights) over the content of this thesis, and has granted La Trobe University permission to reproduce and communicate this version of the thesis. The author has declared that any third party copyright material contained within the thesis made available here is reproduced and communicated with permission. If you believe that any material has been made available without permission of the copyright owner please contact us with the details.