Maximum Common Substructure Extraction in RNA Secondary Structures Using Clique Detection Approach

Shih-Yi Chao
November 2008
Proceedings of World Academy of Science: Engineering & Technolog;Nov2008, Vol. 47, p219
Academic Journal
The similarity comparison of RNA secondary structures is important in studying the functions of RNAs. In recent years, most existing tools represent the secondary structures by tree-based presentation and calculate the similarity by tree alignment distance. Different to previous approaches, we propose a new method based on maximum clique detection algorithm to extract the maximum common structural elements in compared RNA secondary structures. A new graph-based similarity measurement and maximum common subgraph detection procedures for comparing purely RNA secondary structures is introduced. Given two RNA secondary structures, the proposed algorithm consists of a process to determine the score of the structural similarity, followed by comparing vertices labelling, the labelled edges and the exact degree of each vertex. The proposed algorithm also consists of a process to extract the common structural elements between compared secondary structures based on a proposed maximum clique detection of the problem. This graph-based model also can work with NC-IUB code to perform the pattern-based searching. Therefore, it can be used to identify functional RNA motifs from database or to extract common substructures between complex RNA secondary structures. We have proved the performance of this proposed algorithm by experimental results. It provides a new idea of comparing RNA secondary structures. This tool is helpful to those who are interested in structural bioinformatics.


Related Articles

  • New method to predict conserved RNA structures. Mironov, A.A. // Molecular Biology;Jul2007, Vol. 41 Issue 4, p642 

    RNA secondary structure prediction is one of the classic problems of bioinformatics. The most efficient approaches to solving this problem are based on comparative analysis. As a rule, multiple RNA sequence alignment and subsequent determination of a common secondary structure are used. A new...

  • DNA Sequence Alignment based on Bioinformatics. Sharma, Shivani; Singh, Amardeep // International Journal of Computer Science Engineering & Technolo;Jul2012, Vol. 2 Issue 7, p1305 

    DNA Sequence alignmentis the most fundamental and essential task of computational biology and forms the base for other tasks of bioinformatics. The two basic alignment algorithms i.e. Smith Waterman for local alignment and Needleman Wunsch for global alignment have been used in this paper. The...

  • Novel Parallel MSA Algorithm Implementation Approach on a Computer Cluster. Somasundaram, K.; Karthikeyan, S.; Nayangam, M. Gomathi; Radhakrishnan, S. // Journal of Computational Intelligence in Bioinformatics;2009, Vol. 2 Issue 1-2, p85 

    Multiple sequence alignment is computationally difficult and classified as a NP-Hard problem; so approximate algorithm(s) are generally required for most multiple alignment tasks. The Molecular Biologist may require the alignment of thousands of sequences that each can be of many hundreds or...

  • 4SALE -- A tool for synchronous RNA sequence and secondary structure alignment and editing. Seibel, Philipp N; Müller, Tobias; Thomas6Dandekar; Schultz, Jörg; Wolf, Matthias // BMC Bioinformatics;2006, Vol. 7, p1 

    Background: In sequence analysis the multiple alignment builds the fundament of all proceeding analyses. Errors in an alignment could strongly influence all succeeding analyses and therefore could lead to wrong predictions. Hand-crafted and hand-improved alignments are necessary and meanwhile...

  • Tree and rate estimation by local evaluation of heterochronous nucleotide data. Zhu Yang; John D. O'Brien // Bioinformatics;Jan2007, Vol. 23 Issue 2, p169 

    Motivation: Heterochronous gene sequence data is important for characterizing the evolutionary processes of fast-evolving organisms such as RNA viruses. A limited set of algorithms exists for estimating the rate of nucleotide substitution and inferring phylogenetic trees from such data. The...

  • RSEARCH: Finding homologs of single structured RNA sequences. Klein, Robert J.; Eddy, Sean R. // BMC Bioinformatics;2003, Vol. 4, p44 

    Background: For many RNA molecules, secondary structure rather than primary sequence is the evolutionarily conserved feature. No programs have yet been published that allow searching a sequence database for homologs of a single RNA molecule on the basis of secondary structure. Results: We have...

  • Structural RNA alignment by multi-objective optimization. Schnattinger, Thomas; Schöning, Uwe; Kestler, Hans A. // Bioinformatics;Jul2013, Vol. 29 Issue 13, p1607 

    Motivation: The calculation of reliable alignments for structured RNA is still considered as an open problem. One approach is the incorporation of secondary structure information into the optimization criteria by using a weighted sum of sequence and structure components as an objective function....

  • DAFGA: diversity analysis of functional gene amplicons. Kim, Yongkyu; Liesack, Werner // Bioinformatics;Oct2014, Vol. 30 Issue 19, p2820 

    Summary: Diversity analysis of functional marker genes provides physiological insights into microbial guilds that perform an ecologically relevant process. However, it is challenging to group functional gene sequences to valid taxonomic units, primarily because of differences in the evolutionary...

  • Usage of U7 snRNA in gene therapy of hemoglobin S disorder - is it feasible? Wiwanitkit, Viroj // Turkish Journal of Hematology;Sep2009, Vol. 26 Issue 3, p159 

    The article discusses the study which examined the role of U7 small nuclear RNAs (SnRNAs) in gene therapy of hemoglobin (Hb) S disorder, one of the most common forms of hemoglobinopathies. The study evaluated how co-expression affects nucleic acid sequence for human Hb S beta globin chain and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics