One of the striking pictures in Tamara Munzner et al.'s paper "TreeJuxtaposer: Scalable Tree Comparison using Focus+Context with Guaranteed Visibility" (doi:10.1145/882262.882291, also available here) is that of a biologist struggling to visualise a large phylogeny. The figure caption states that:
Biologists faced with inadequate tools for comparing large trees have fallen back on paper, tape, and highlighter pens.
I've been struggling with this problem in the context of display trees on a web page (see an earlier post). Viewing large trees has received a lot of attention, and there are some fun tools such as Tamara Munzner's TreeJuxtaposer and Mike Sanderson's Paloverde (doi:10.1093/bioinformatics/btl044 ), which was used to create the cover for the October 2006 issue of Systematic Biology. And let's not forget Google Earth.
The problem with standalone tools like these is that they are just that - standalone. They are meant to support interactive visualisation in an application, not viewing a tree on a web page. This is a particular problem facing TreeBASE. A user wanting to view, say, the marsupial supertree published by Cardillo et al. (doi:10.1017/S0952836904005539, TreeBASE study S1035) is greeted by the message:
This tree is too large to be seen using the usual GUI. We recommend that you view the tree using the java applet ATV or the program TreeView (see below). Alternatively, you can download the data matrix and view the tree(s) in MacClade, PAUP, or any other nexus-compatible software.and the tree is displayed as Newick text string:
(((((((((((Abacetus, ((((Agonum, Glyptolenus), Europhilus, Tanystoma, Platynus), ((Morion, Moriosomus), Stenocrepis)), (((Licinus, Zargus, Badister), (Panagaeus, Tefflus)), Melanchiton)), ((Amara, Zabrus), (Harpalus, Dicheirotrichus, Parophonus, Trichocellus, Ophonus, Trichotichnus, Diachromus, Pseudoophonus, Stenolophus, Notobia, Bradycellus, Nesacinopus, Anisodactylus, Acupalpus, Acinopus, Xestonotus)), ((Anthia, Thermophilum), ((Corsyra, Discoptera), Graphipterus)), (((Apenes, (Chlaenius, Callistus)), Oodes), ((Calophaena, ((Ctenodactyla, Leptotrachelus), Galerita)), (Pseudaptinus, Zuphius))), (((Calleida, Hyboptera), Lebia), Cymindis, Demetrias, Dromius, Lionychus, Microlestes, Syntomus), ((Calybe, Lachnophorus), Odacantha), (Catapiesis, (Desera, Drypta)), Cnemalobus, (Coelostomus, (Eripus, Pelecium)), ...
Not the most compelling visualisation. What I hope to do in this and following posts is describe my own efforts to come to grips with this problem.Requirements
To put the problem into perspective, what I'm looking for is a simple way to draw large trees for display in a web browser. This places severe limits on the kind of interactivity that is possible (unless we go down the root of Java applets, which I will avoid like the plague). This rules out, for example, trying to emulate TreeJuxtaposer's functionality. Initially I started looking at SVG, which renders graphics nicely, supports interaction, and being essentially an XML file, is easy to manipulate (for an example see my earlier post on SVG maps). However, SVG is not well supported in all browsers (FireFox does pretty well, most other browsers are variable). All browsers, however, support bitmap graphics (GIF, PNG, JPEG, etc.). When drawing complex things like trees bitmaps have some advantages, especially with regards to labelling. Small bitmap fonts tend to be more legible than anti-aliased fonts at the same size (see article at MiniFonts for background.
Animation
Comments so far on this post have focussed on animation (e.g., using Flash). Here is a video of TreeJuxtaposer taken from Tamara Munzner's web site.
For me the most interesting features of TreeJuxtaposer are that the entire tree is always visible (thus retaining context, unlike pan and zoom), and the user can select bits to view by drawing a rectangle on the screen. The processing to compute the transformations needed for large trees is fairly heavy duty, although newer algorithms have reduced this somewhat (see here).
