Abstrakt
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.