Return to search

The Comparison of RNA Secondary Structures with Nested Arc Annotation

In recent years, RNA structural comparison becomes a crucial problem in bioinformatic research. Generally, it is a popular approach for representing the RNA secondary
structures with arc-annotation sets. Several methods can be used to compare two RNA structures, such as tree edit distance, longest arc-preserving common subsequence
(LAPCS) and stem-based alignment. However, these methods may be helpful only for small RNA structures because of their high time complexity. In this thesis, we propose
a simplified method to compare two RNA structures in O(mn)time, where m and n are the lengths of the two RNA sequences, respectively. Our method transforms the RNA
structures into specific sequences called object sequences, then compare these object sequences to find their common substructures. We test our comparison method with 118 RNA structures obtained from RNase P Database. For any two structures, we try to identify whether they are in the same family by both structure comparison and sequence comparison. In our experiment, we find that our method for comparing RNA structures can yield better hit rates and is faster than the traditional method to compare the RNA sequences. Therefore, our approach for comparing RNA secondary structures is more sensitive in biology and more efficient in time complexity.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0723104-181009
Date23 July 2004
CreatorsPeng, Yung-Hsing
ContributorsYe-In Chang, Maw-Shang Chang, Bang-Ye Wu, Yow-Ling Shiue, Chang-Biau Yang
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0723104-181009
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.0018 seconds