University of Georgia
Computational search of RNA pseudoknots and structural variations in genomes.
Degree: PhD, Computer Science, 2011, University of Georgia
Non-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.
Advisors/Committee Members: Liming Cai.
Subjects/Keywords: ncRNA structure search; Sequence structure alignment; pseudoknot; ncRNA structure variation; RNA structure evolution; Graph tree decomposition; Dynamic Programming
to Zotero / EndNote / Reference
APA (6th Edition):
Huang, Z. (2011). Computational search of RNA pseudoknots and structural variations in genomes. (Doctoral Dissertation). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/huang_zhibin_201105_phd
Chicago Manual of Style (16th Edition):
Huang, Zhibin. “Computational search of RNA pseudoknots and structural variations in genomes.” 2011. Doctoral Dissertation, University of Georgia. Accessed November 18, 2019.
MLA Handbook (7th Edition):
Huang, Zhibin. “Computational search of RNA pseudoknots and structural variations in genomes.” 2011. Web. 18 Nov 2019.
Huang Z. Computational search of RNA pseudoknots and structural variations in genomes. [Internet] [Doctoral dissertation]. University of Georgia; 2011. [cited 2019 Nov 18].
Available from: http://purl.galileo.usg.edu/uga_etd/huang_zhibin_201105_phd.
Council of Science Editors:
Huang Z. Computational search of RNA pseudoknots and structural variations in genomes. [Doctoral Dissertation]. University of Georgia; 2011. Available from: http://purl.galileo.usg.edu/uga_etd/huang_zhibin_201105_phd