| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Visualization of Barrier Tree Sequences
September-October 2006 (vol. 12 no. 5)
pp. 781-788
Dynamical models that explain the formation of spatial structures of RNA molecules have reached a complexity that requires novel visualization methods that help to analyze the validity of these models. Here, we focus on the visualization of so-called folding landscapes of a growing RNA molecule. Folding landscapes describe the energy of a molecule as a function of its spatial configuration; thus they are huge and high dimensional. Their most salient features, however, are encapsulated by their so-called barrier tree that reflects the local minima and their connecting saddle points. For each length of the growing RNA chain there exists a folding landscape. We visualize the sequence of folding landscapes by an animation of the corresponding barrier trees. To generate the animation, we adapt the foresight layout with tolerance algorithm for general dynamic graph layout problems. Since it is very general, we give a detailed description of each phase: constructing a supergraph for the trees, layout of that supergraph using a modified DOT algorithm, and presentation techniques for the final animation.
[1] 781 U. Brandes, T. Dwyer, and F. Schreiber, Visualizing related metabolic pathways in two and a half dimensions. In Liotta [18], pages 111–122.[2] R. F. Cohen, G. di Battista, R. Tamassia, I. G. Tollis, and P. Bertolazzi, A framework for dynamic graph drawing. In Symposium on Computational Geometry, pages 261–270, 1992.[3] J. Cupal, I. L. Hofacker, and P. F. Stadler, Dynamic programming algorithm for the density of states of RNA secondary structures. In R. Hofst ädt, T. Lengauer, M. L öffler, and D. Schomburg, editors, Computer Science and Biology 96 (Proceedings of the German Conference on Bioinformatics), pages 184–186. Universität Leipzig, 1996.[4] G. di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for drawing graphs: An annotated bibliography. Computational Geometry: Theory and Applications, 4 (5): 235–282, 1994.[5] S. Diehl and C. Görg, Graphs, they are changing. In S. G. Kobourov and M. T. Goodrich, editors, Graph Drawing, volume 2528 of Lecture Notes in Computer Science, pages 23–30. Springer, 2002.[6] T. Dwyer and F. Schreiber, Optimal leaf ordering for two an and a half dimensional phylogenetic tree visualisation. In N. Churcher and C. Churcher, editors, In Vis.au, volume 35 of CRPIT, pages 109–115. Australian Computer Society, 2004.[7] C. Erten, P. J. Harding, S. G. Kobourov, K. Wampler, and G. V. Yee , Graphael: Graph animations with evolving layouts. In Liotta [18], pages 98–110.[8] G. Fayat, J.-F. Mayaux, C. Sacerdot, M. Fromant, M. Springer , M. Grunberg-Manago, and S. Blanquet, Escherichia coli phenylalanyltRNA synthetase operon region : Evidence for an attenuation mechanism. Identification of the gene for the ribosomal protein L20. J. Mol. Biol., 171 (3): 239–352, 1983.[9] C. Flamm, W. Fontana, I. L. Hofacker, and P. Schuster, RNA folding at elementary step resolution. RNA, 6: 325–338, 2000.[10] C. Flamm, I. L. Hofacker, P. F. Stadler, and M.T. Wolfinger, Barrier trees of degenerate landscapes. Z. Phys. Chem., 216:1–19, 2002.[11] C. Friedrich and P. Eades, Graph drawing in motion. J. Graph Algorithms Appl., 6 (3): 353–370, 2002.[12] Y. Frishman and A. Tal, Dynamic drawing of clustered graphs. In INFOVIS pages 191–198. IEEE Computer Society, 2004.[13] M. Gaertler and D. Wagner, A hybrid model for drawing dynamic and evolving graphs. In P. Healy and N. S. Nikolov, editors, Graph Drawing, volume 3843 of Lecture Notes in Computer Science, pages 189–200. Springer, 2005.[14] E. R. Gansner, E. Koutsofios, S. C. North, and K.-P. Vo, A technique for drawing directed graphs. IEEE Trans. Software Eng., 19 (3): 214–230, 1993.[15] U. Gerland, R. Bundschuh, and T. Hwa, Translocation of structured polynucleotides through nanopores. Phys. Biology, 1 (1–2): 19–26, 2004.[16] C. Görg, P. Birke, M. Pohl, and S. Diehl, Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In J. Pach, editor, Graph Drawing, volume 3383 of Lecture Notes in Computer Science, pages, 228–238. Springer, 2004.[17] I. Herman, G. Melançon, and M. S. Marshall, Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics, 06 (1): 24–43, 2000.[18] G. Liotta, editor. Graph Drawing, 11th International Symposium, GD 2003, Perugia, Italy, September 21–24, 2003, Revised Papers, volume 2912 of Lecture Notes in Computer Science. Springer, 2004.[19] I. M. Meyer and I. Miklos, Co-transcriptional folding is encoded within RNA genes. BMC Molecular Biology, 5 (10), 2004.[20] K. Misue, P. Eades, W. Lai, and K. Sugiyama, Layout adjust adjustment and the mental map. J. Visual Languages and Computing, 6 (2): 183–210, 1995.[21] S. Moen, Drawing dynamic trees. IEEE Software, 7 (4): 21–28, July 1990.[22] S. C. North, Incremental layout in dynadag. In Graph Drawing, pages 409–418, 1995.[23] K. Sugiyama, S. Tagawa, and M. Toda, Methods for visual understanding of hierarchical systems. IEEE Trans. Systems, Man, and Cybernetics, 11: 109–125, 1981.[24] R. Tamassia, Advances in the theory and practice of graph drawing. Theoretical Computer Science, 217 (2): 235–254, 1999.[25] M. T. Wolfinger, W. A. Svrcek-Seiler, C. Flamm, I. L. Hofacker, and P. F. Stadler, Exact folding dynamics of RNA secondary structures. J. Phys. A: Math.Gen., 37: 4731–4741, 2004.
Index Terms:
Graph drawing, dynamic graph, RNA folding, energy landscape, fitness landscape, barrier tree
Citation:
Christian Heine, Gerik Scheuermann, Christoph Flamm, Ivo L. Hofacker, Peter F. Stadler, "Visualization of Barrier Tree Sequences," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 781-788, Sept. 2006, doi:10.1109/TVCG.2006.196
