Les « arbres empilés »: une nouvelle approche pour la visualisation des grands dendrogrammes

ABSTRACT

In this paper, we describe a new visualisation method for hierarchical clustering named "stacked trees". Our goal is to display, at the same time, the relational structure of the top classes of a tree and a large number of information about its leaves. Thanks to this approach, one can visualize on a standard screen a dendrogram containing ten of thousands of nodes. Although this method has been imagined to explore the content of molecular libraries in chemoinformatic, our approach is generic enough to be used in many other domains. A prototype named STV (Stacked Trees Viewer) has been implemented as a Web application that is freely usable from our Web site.

REFERENCES

• 1: Aci S., Bisson G., Roy S. & Wieczorek S. (2007). Clustering of Molecules: Influence of the Similarity Measures. In Selected Contributions in Data Analysis and Classification. Springer. Brito P., Bertrand P., Cucumel G., De Carvalho F. (Eds). p 433--445.
• 2: Auman J., Boorman G., Wilson R., Travlos G. & Paules R. (2007). Heat map visualization of high-density clinical chemistry data. Physiological genomics 31(2):352--6.
• 3: Balzer M., Deussen O. & Lewerentz C. (2005). Voronoi treemaps for the visualization of software metrics. Proceedings of the 2005 ACM symposium on Software visualization. p 165--172.
• 4: Bar-Joseph Z., Giffor D. & Jaakkola T. (2001). Fast optimal leaf ordering for hierarchical clustering-Bioinformatics (Proceedings of ISMB 2001) 17(S1), pp 22--29.
• 5: J. P. Benzecri (1973). L'analyse des Données. La Taxinomie, Dunod. ISBN: 2-04-010891-2.
• 6: Böcker A. (2008). Toward an Improved Clustering of Large Data Sets Using Maximum Common Substructures and Topological Fingerprints. J. Chem. Inf. Model. Vol 48 (11), p 2097--2107.
• 7: Berkhin P. (2006). Survey of clustering data mining techniques. In Grouping Multidimensional Data. Springer Berlin Heidelberg. p 25--71.
• 8: Carriere J. & Kazman R. (1995). Interacting with Huge Hierarchies: Beyond Cone Trees. Proc. IEEE Information Visualization. p 74--81.
• 9: Diday E., Lemaire, J., Pouget J. & Testu F. (1982). Elééments d'analyse des données. Edition Dunod-Bordas.
• 10: Dubois J., Bourg S., Vrain C. & Morin-Allory L. (2008). Collections of Compounds - How to Deal with them? Current Computer - Aided Drug Design. Vol 4 (3), p 156--168.
• 11: Fekete J-D. & Plaisant C. (2002). Interactive Information Visualization of a Million Items. In Proceedings of the IEEE Symposium on information Visualization (InfoVis). Washington, DC, 117--126.
• 12: Forina M., Lanteri S., Casale M. & Concepcióón Cerrato Oliveros M. (2007). A new algorithm for seriation and its use in similarity dendrogram. Chemometrics and Intelligent Laboratory Systems. Vol 87. p 262--274.
• 13: Heard J., Kaufmann W. & Guan X. (2009). A Novel Method for Large Tree Visualization. Bioinformatics 25(4):557--558.
• 14: Henry N., Fekete J-D & J. McGuffin (2007). NodeTrix: a Hybrid Visualization of Social Networks. IEEE Transactions on Visualization and Computer Graphics, vol. 13, number 6. p 1302--1309.
• 15: Kibbey C. & Calvet A. (2005). Molecular Property eXplorer: A Novel Approach to Visualizing SAR Using Tree-Maps and Heatmaps. J. Chem. Inf. Model. Vol 45 (2), 523--532.
• 16: Lamping J, Rao R. & Pirolli P. (1995). A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies. Proceedings of ACM Conference Human Factors in Computing Systems. p 401--408.
• 17: Lipinski C. & Hopkins A. (2004). Navigating chemical space for biology and medicine. Nature 432 (7019). p 855--861.
• 18: Matero S., Lahtela-Kakkonen M., Korhonen O., Ketolenen J., Lappalainen R. & Poso A. (2006). Chemical space of orally active compounds. Chemometrics and intelligent laboratory systems. Vol. 84, no 1--2, p 134--141.
• 19: Munzner, T., Guimbretière, F., Tasiran, S., Zhang, L. & Zhou, Y. (2003). TreeJuxtaposer: scalable tree comparison using Focus+Context with guaranteed visibility. In proceedings ACM SIGGRAPH. San Diego. p 453--462.
• 20: Plaisant C., Grosjean J. & Bederson B. (2002). SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation. IEEE Symposium on Information Visualization (InfoVis). Washington, DC, 57--66.
• 21: Roberson G., Mackinlay J., & Card S. (1991). Cone Trees: Animated 3D Visualizations of Hierarchical Information. Proceedings of ACM SIGCHI conference on Human Factors in Computing Systems, p. 189--194.
• 22: Schuffenhauer A., Ertl P., Roggo S., Wetzel S., Koch M. & Waldmann H. (2007). The Scaffold Tree _ Visualization of the Scaffold Universe by Hierarchical Scaffold Classification. J. Chem. Inf. Model. Vol 47 (1), p 47--58.
• 23: Seo J. & Shneiderman B. (2002). Interactively Exploring Hierarchical Clustering Results. Computer, vol. 35, number 7. p 80--86.
• 24: Shneiderman B. (1992). Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v. 11 n. 1, p 92--99.
• 25: Zhao S., McGuffin & Chignell M. (2005). Elastic Hierarchies: Combining Treemaps and Node-Link Diagrams. IEEE Symposium on Information Visualization (InfoVis). p 57--64.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms

Keywords:
chemoinformatic, hierarchical clustering, large classification, stacked trees