New representation and algorithm for drawing RNA structure with pseudoknots

Visualization of a complex molecular structure is a valuable tool in understanding the structure. A drawing of RNA pseudoknot structures is a graph (and a possibly nonplanar graph) with inner cycles within a pseudoknot as well as possible outer cycles formed between a pseudoknot and other structural elements. Thus, drawing RNA pseudoknot structures is computationally more difficult than depicting RNA secondary structures. Although several algorithms have been developed for drawing RNA secondary structures, none of these can be used to draw RNA pseudoknots and thus visualizing RNA pseudoknots relies on significant amount of manual work. Visualizing RNA pseudoknots by manual work becomes more difficult and yields worse results as the size and complexity of the RNA structures increase. We have developed a new representation method and an algorithm for visualizing RNA pseudoknots as a twodimensional drawing and implemented the algorithm in a program. The new representation produces uniform and clear drawings with no edge crossing for all kinds of pseudoknots, including H-type and other complex types. Given RNA structure data, we represent the whole structure as a tree rather than as a graph by hiding the inner cycles as well as the outer cycles in the nodes of the abstract tree. Once the top-level RNA structure is represented as a tree, nodes of the tree are placed and drawn in increasing order of their depth values. Experimental results demonstrate that the algorithm generates a clear and aesthetically pleasing drawing of large-scale RNA structures, containing any number of pseudoknots. This is the first algorithm for automatically drawing RNA structure with pseudoknots.