Volume 6 Number 1 (Jan. 2016)
Home > Archive > 2016 > Volume 6 Number 1 (Jan. 2016) >
IJBBB 2016 Vol.6(1): 9-17 ISSN: 2010-3638
doi: 10.17706/ijbbb.2016.6.1.9-17

RNA Secondary Structure Visualization Using Tree Edit Distance

Richard Eliáš, David Hoksza
Abstract—RNA secondary structures, both experimental and predicted, are becoming increasingly available which is reflected in the increased demand for tools enabling their analysis. The common first step in the analysis of RNA molecules is visual inspection of their secondary structure. In order to correctly lay out an RNA structure, the notion of optimal layout is required. However, optimal layout of an RNA structure has never been formalized and is largely habitual. To tackle this problem we propose an algorithm capable of visualizing an RNA structure using a related structure with a well-defined layout. The algorithm first converts both structures into tree representations and then uses tree-edit distance algorithm to find out the minimum number of tree edit operations to convert one structure into the other. We couple each tree edit operation with a layout modification operation which is then used to gradually transform the known layout into the target one. The tree edit distance algorithm causes that the common motives are retained and only regions which differ in both the structures are changed in the resulting layout. Visual inspection and planarity evaluation reveals that the algorithm is able to give good layouts even for relatively distant structures while keeping the layout planar. The new method is well suited for situations when one needs to visualize a structure for which a homologous structure with a good visualization is already available.

Index Terms—RNA secondary structure, visualization, homology

Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic

Cite: Richard Eliáš, David Hoksza, "RNA Secondary Structure Visualization Using Tree Edit Distance," International Journal of Bioscience, Biochemistry and Bioinformatics vol. 6, no. 1, pp. 9-17, 2016.

General Information

ISSN: 2010-3638 (Online)
Abbreviated Title: Int. J. Biosci. Biochem. Bioinform.
Frequency: Quarterly 
DOI: 10.17706/IJBBB
Editor-in-Chief: Prof. Ebtisam Heikal 
Abstracting/ Indexing:  Electronic Journals Library, Chemical Abstracts Services (CAS), Engineering & Technology Digital Library, Google Scholar, and ProQuest.
E-mail: ijbbb@iap.org
  • Sep 29, 2022 News!

    IJBBB Vol 12, No 4 has been published online! [Click]

  • Jun 23, 2022 News!

    News | IJBBB Vol 12, No 3 has been published online! [Click]

  • Dec 20, 2021 News!

    IJBBB Vol 12, No 1 has been published online!  [Click]

  • Sep 23, 2021 News!

    IJBBB Vol 11, No 4 has been published online! [Click]

  • Jun 25, 2021 News!

    IJBBB Vol 11, No 3 has been published online! [Click]

  • Read more>>