RNA Secondary Structure Visualization Using Tree Edit Distance

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10336792" target="_blank" >RIV/00216208:11320/16:10336792 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.17706/ijbbb.2016.6.1.9-17" target="_blank" >http://dx.doi.org/10.17706/ijbbb.2016.6.1.9-17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.17706/ijbbb.2016.6.1.9-17" target="_blank" >10.17706/ijbbb.2016.6.1.9-17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

RNA Secondary Structure Visualization Using Tree Edit Distance

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

RNA Secondary Structure Visualization Using Tree Edit Distance

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

International Journal of Bioscience, Biochemistry and Bioinformatics

ISSN

2010-3638

e-ISSN

—

Svazek periodika

6

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

8

Strana od-do

9-17

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—