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
Frequency: Bimonthly (2011-2015); Quarterly (Since 2016)
DOI: 10.17706/IJBBB
Editor-in-Chief: Prof. Ebtisam Heikal 
Abstracting/ Indexing: Electronic Journals Library, Chemical Abstracts Services (CAS), Google Scholar, and ProQuest.
E-mail: ijbbb@iap.org
  • Jun 25, 2018 News!

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

  • Apr 26, 2018 News!

    The papers published in Vol. 8, No. 3 have all received dois from Crossref. [Click]

  • Feb 24, 2018 News!

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

  • Feb 06, 2018 News!

    The papers published in Vol. 8, No. 2 have all received dois from Crossref. [Click]

  • Jan 31, 2018 News!

    IJBBB Vol. 8, No. 2 has been published online!  [Click]

  • Read more>>