Files
Abstract
The major objective of bioinformatics research is to study biological systems with computational perspectives and methods. Structural bioinformatics is an important field in bioinformatics and focuses on the modeling, description and prediction of the tertiary and secondary structures of biological molecules. Due to the inherent complexity associated with the structures of biological molecules, many problems in structural bioinformatics are computationally hard. An important challenge is thus to find computationally efficient methods (approximate or heuristic) that can provide good quality results. This dissertation develops methods and models for noncoding RNA search and protein threading, which are two important problems in structural bioinformatics. In particular, we study statistical methods that can model RNA structures containing pseudoknots. Based on Parallel Communicating Grammar Systems (PCGSs), a memory efficient algorithm is developed to align an RNA sequence to a pseudoknot structure. In addition, we show that the sequence-structure alignment problem can be reduced to the maximum valued subgraph isomorphism problem. Based on the concept of graph tree decomposition, this problem can be solved efficiently when the tree width of the guest graph is small. Based on this technique, new methods are developed to solve the problems of noncoding RNA search and protein tertiary structure prediction. The computational core of both problems is the sequence- structure alignment problem, and our testing results with this new algorithm demonstrate its advantage over previous methods for both problems in accuracy and computational efficiency.