University of Glasgow

Roderic Page

OK, time to put my money where my mouth is. Here\'s a first stab at
displaying big trees in a browser. Not terribly sophisticated, but
reasonably fast. Take a look at [Big
Trees](http://linnaeus.zoology.gla.ac.uk/~rpage/bigtrees/).  
  
**Approach**  
Given a tree I simply draw it in a predetermined area (in these examples
400 x 600 pixels). If there are more leaves than can be drawn without
overlapping I simply cull the leaf labels. If there are internal node
labels I draw vertical lines corresponding to the **span** of the
corresponding subtree, which is simply the range between the left-most
and right-most decendants of that node. If internal node labels are
nested (e.g., \"Mammalia\" and \"Primates\") I draw the most recent
internal node label, the rationale being that I want only a single set
of vertical bars. This gives the visual effect of partitioning up the
leaves into non-overlapping sets. This gives us a diagram like this:  
  
[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEirqwmgPxCUvB764vcpn6wfQk3M4G1Qfyb6q70gNymo_4qK9QoInZLFRe64JjSoFRnnFMW6_HgHe4mzcjA8u3TFuD6vdn0R-24VZnAxFcq-KqU43DZ_GZKbX3pseOJPHLq6bvSQ/s320/whales.tre.gif){#BLOGGER_PHOTO_ID_5094496760969186482
style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEirqwmgPxCUvB764vcpn6wfQk3M4G1Qfyb6q70gNymo_4qK9QoInZLFRe64JjSoFRnnFMW6_HgHe4mzcjA8u3TFuD6vdn0R-24VZnAxFcq-KqU43DZ_GZKbX3pseOJPHLq6bvSQ/s1600-h/whales.tre.gif)  
OK, but what about all the nodes we can\'t see? What I do here is make
the tree \"clickable\" in the following way. If there are internal node
labels I make the corresponding tree clickable. I also traverse the tree
looking for well defined clusters \-- basically subtrees that are
isolated by a long branch from their nearest neighbours \-- and make
these clickable. This approach is partly a hang over form earlier
experiments on automatically folding a tree (partly inspired by
[doi:10.1111/1467-8659.00235](http://dx.doi.org/10.1111/1467-8659.00235)).
The key point is I\'m trying to avoid testing for mouse clicks on nodes
and edges, as many of these will be ocluded by other nodes and edges,
and it will also be expensive to do hit testing on nodes and edges in a
big tree.  
  
If you click on one the script extracts the subtree and reloads the
display showing just that part of the tree, using exactly the same
approach as above. Behind the scenes the code is doing a least common
ancestor (LCA) query, hence it defines subtrees rather like the
Phylocode does ([oh the
irony](http://iphylo.blogspot.com/2007/01/phylocode.html)).  
  
**Pros**  

- Reasonably fast (everything you see is done live \"on the fly\").
- Works in any modern browser, no dependence on plugins or technology
  that has limited support.
- Image is clear, text is small but legible.
- Entirely automated layout

  
  
**Cons**  

- Reloading a new page is costly in terms of time, and potentially
  disorienting (you loose sense of the larger tree).
- It is not obvious where to click on the tree (needs to be
  highlighted).
- Text is not clickable. This is would be really useful for internal
  node labels.


OK, time to put my money where my mouth is. Here's a first stab at displaying big trees in a browser. Not terribly sophisticated, but reasonably fast. Take a look at Big Trees.
<strong>
 Approach
</strong>
Given a tree I simply draw it in a predetermined area (in these examples 400 x 600 pixels). If there are more leaves than can be drawn without overlapping I simply cull the leaf labels.

Visualising very big trees, Part II

[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOqJtLsp0qpYYqltXTpisoQv2Zs0CCwvS5EIeJ1H3XelqhHCK2uaB_hl2Z3rgSounEXU0U480m8_6bM_nj4_5BVkp62g9Gi06TDwXOqjl6VxPxyvHdLGuZuIMi7TfR9XTOk_m5/s320/will.small.jpg){#BLOGGER_PHOTO_ID_5094021016031743090
style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOqJtLsp0qpYYqltXTpisoQv2Zs0CCwvS5EIeJ1H3XelqhHCK2uaB_hl2Z3rgSounEXU0U480m8_6bM_nj4_5BVkp62g9Gi06TDwXOqjl6VxPxyvHdLGuZuIMi7TfR9XTOk_m5/s1600-h/will.small.jpg){onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"}  
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](http://dx.doi.org/10.1145/882262.882291),
also available [here](http://www.cs.ubc.ca/~tmm/papers/tj/)) 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](http://iphylo.blogspot.com/2005/12/visualising-tree-of-life.html)).
Viewing large trees has received a lot of attention, and there are some
fun tools such as Tamara Munzner\'s
[TreeJuxtaposer](http://olduvai.sourceforge.net/) and Mike Sanderson\'s
[Paloverde](http://loco.biosci.arizona.edu/paloverde/paloverde.html)
([doi:10.1093/bioinformatics/btl044](http://dx.doi.org/10.1093/bioinformatics/btl044%20)
), which was used to create the cover for the [October
2006](http://journalsonline.tandf.co.uk/openurl.asp?genre=issue&eissn=1076-836X&volume=55&issue=5)
issue of *Systematic Biology*. And let\'s not forget [Google
Earth](http://iphylo.blogspot.com/2007/06/earth-not-flat-official.html).  
[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGHKF_-1BBhZC76S4U_Yo2GhCnE62oxuR6XafpLtPMXQBZlRrEQvUIwnh-EhtlznyZc_stwzB1MthFpYQhOU8gt7zzRa5Um1SKJIFzWs-nNIIsH-lRnabqtivQt9t-Pjb_z9nG/s200/teaser.png){#BLOGGER_PHOTO_ID_5094024069753490578
style="float:left; margin:0 10px 10px 0;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGHKF_-1BBhZC76S4U_Yo2GhCnE62oxuR6XafpLtPMXQBZlRrEQvUIwnh-EhtlznyZc_stwzB1MthFpYQhOU8gt7zzRa5Um1SKJIFzWs-nNIIsH-lRnabqtivQt9t-Pjb_z9nG/s1600-h/teaser.png){onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"}  
  
  
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](http://www.treebase.org). A user
wanting to view, say, the marsupial supertree published by Cardillo et
al.
([doi:10.1017/S0952836904005539](http://dx.doi.org/10.1017/S0952836904005539),
TreeBASE study
[S1035](http://www.treebase.org/cgi-bin/treebase.pl?StudyID=S1035&Submit=Study+ID))
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:  

::: {style="font-family:fixed,Courier;font-size:10px;"}
(((((((((((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)), \...
:::

  
  
[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgROo42Esv9VMSxp6Ek1AW8yhXYazeRdlgIY59fvAN-rDiXzNOlOg2b5ZtDtMoORId3DEotFOSdqoID8HePJDk0jKAMn93t39kX7rz_yp4ioBq-ghHklulmqdnt8yWUsBC5M1Hd/s320/october2006RGB.jpg){#BLOGGER_PHOTO_ID_5094020865707887714
style="float:left; margin:0 10px 10px 0;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgROo42Esv9VMSxp6Ek1AW8yhXYazeRdlgIY59fvAN-rDiXzNOlOg2b5ZtDtMoORId3DEotFOSdqoID8HePJDk0jKAMn93t39kX7rz_yp4ioBq-ghHklulmqdnt8yWUsBC5M1Hd/s1600-h/october2006RGB.jpg){onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"}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](http://semant.blogspot.com/2006/11/svg-specimen-maps-from-sparql-results.html)).
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](http://www.minifonts.com/info.html) 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](http://olduvai.sourceforge.net/tj/publications.shtml)).


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.

Viewing very large trees

[![](https://www.nescent.org/wg/EvoViz/images/f/f1/Hylidae_allpolygons.png){style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px;"
border="0"}](https://www.nescent.org/wg/EvoViz/images/f/f1/Hylidae_allpolygons.png)  
David Kidd has put together [evoviz.org](http://evoviz.org/). To quote
from the wiki:  

> EvoViz is a collaborative Wiki space within which scientists,
> educators and artists can present and discuss the visualization of
> evolutionary concepts, processes and data.

  
There is movie demo online at
[GUBA](http://www.guba.com/watch/3000037924).


David Kidd has put together evoviz.org. To quote from the wiki:There is movie demo online at GUBA.

Publicaciones de Rogue Scholar

Visualising very big trees, Part II

Viewing very large trees

EvoViz