Modeling and searching for ncRNA secondary structure

The discovery of functional non-coding RNAs (ncRNAs) has led to an increasing interest in efficient algorithms related to ncRNA secondary structure prediction and search for new ncRNA in genomes. The hidden Markov model and covariance model have been introduced to perform such tasks, but their limitations of modeling and computational complexity have compromised their practical application. Therefore, a tree-decomposition-based graph approach has been proposed to efficiently conduct the structure-sequence alignment, which underlies our computational tool, RNATOPS. As an essential part, the modeling and searching for accurate component candidates in a structure become one of major issues in the search process. In this thesis, a simplified model and many heuristic techniques have been proposed and exploited to address the issue. Comparisons between RNATOPS and Infernal have been conducted on several types of ncRNAs, which show the better performance of RNATOPS.