RNA structure analysis : algorithms and applications

In this doctoral thesis, efficient algorithms for aligning RNA secondary structures and mining unknown RNA motifs are presented. As the major contribution, a structure alignment algorithm, which combines both primary and secondary structure information, can find the optimal alignment between two given structures where one of them could be either a pattern structure of a known motif or a real query structure and the other be a subject structure. Motivated by widely used algorithms for RNA folding, the proposed algorithm decomposes an RNA secondary structure into a set of atomic structural components that can be further organized in a tree model to capture the structural particularities. The novel structure alignment algorithm is implemented using dynamic programming techniques coupled by position-independent scoring matrices. The algorithm can find the optimal global and local alignments between two RNA secondary structures at quadratic time complexity. When applied to searching a structure database, the algorithm can find similar RNA substructures and therefore can be used to identify functional RNA motifs. Extension of the algorithm has also been accomplished to deal with position-dependent scoring matrix in the purpose of aligning multiple structures. All algorithms have been implemented in a package under the name RSmatch and applied to searching mRNA UTR structure database and mining RNA motifs. The experimental results showed high efficiency and effectiveness of the proposed techniques.

Name thesis:degree_name

Doctor of Philosophy in Computing Sciences - (Ph.D.)

Discipline thesis:degree_discipline

Computer Science

Year

2005

Author dc:creator

• Liu, Jianghui

Contributors dc:contributor

• Jason T. L. Wang
• Bin Tian
• James A. McHugh

• RNA Structure
• Algorithm
• RNA Motif
• Bioinformatics
• Dynamic programming
• Computer Sciences

Repository record dc:identifier

https://digitalcommons.njit.edu/dissertations/730

OAI identifier oai:identifier

oai:digitalcommons.njit.edu:dissertations-1785