Show simple item record

dc.contributor.authorHuang, Zhibin
dc.description.abstractNon-coding RNA (ncRNA) secondary structural homologs can be detected effectively in genomes based on a covariance model (CM) and associated dynamic programming algorithms. However, the computational difficulty in aligning an RNA sequence to a pseudoknot structure has prohibited high throughput search for RNA pseudoknot structures in sequences. Due to the lack of appropriate ncRNA structural evolution models, accurate search of distant RNA structural homologs also remains difficult. The core of both problems is the sequence structure alignment that requires intensive computation for complex structure. Based on a conformational graph model we built to incorporate all the interactions of stem and loop, including the crossing stem pattern of pseudoknots, the sequence-structure alignment problem can be modeled as a subgraph isomorphism problem. Based on the graph tree decomposition and naturally small tree width in ncRNA structures including pseudoknots, the problem of searching ncRNA with pseudoknot structures in genomes can be solved efficiently by the tree decomposition based dynamic programming algorithm. Further, the sequence-structure alignment problem for distant RNA structural homolog search can be modeled as a graph homomorphism problem. Tree decomposition based dynamic programming algorithm equipped with the new technique of NULL stem is applied to solving the RNA structural variation search problem more effectively. In this dissertation, we developed two search frameworks, RNATOPS and its extension RNAv, based on a general conformational graph model. Our genome search test results demonstrate RNATOPS has an advantage over Infernal and other methods in accuracy and computational efficiency when searching for the ncRNA pseudoknot structures in genomes, and RNAv, with the capability of detecting pseudoknot, also has an advantage over Infernal in detection of some distant homologs.
dc.subjectncRNA structure search, Sequence structure alignment, pseudoknot, ncRNA structure variation, RNA structure evolution, Graph tree decomposition, Dynamic Programming
dc.titleComputational search of RNA pseudoknots and structural variations in genomes
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorLiming Cai
dc.description.committeeLiming Cai
dc.description.committeeYing Xu
dc.description.committeeKhaled Rasheed
dc.description.committeeRussell Malmberg

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record