Showing posts with label trees. Show all posts
Showing posts with label trees. Show all posts

Monday, February 28, 2011

Live demo of zooming a large tree

After the teaser on Friday (see Deep zooming a large 2D tree) I've put a live demo of my experiments with viewing a large tree online at:

http://iphylo.org/~rpage/deeptree/

The first example (Experiment 1) is the NCBI classification for frogs:

This version displays internal node labels, leaf labels (as many as can be displayed at a given zoom level), and works in Safari, Firefox, and Internet Explorer 8. Obviously this is all pretty rough, but take it for a spin, I'd welcome any feedback.

Thursday, February 24, 2011

Why 3D phylogeny viewers don't work

Matt Yoder (@mjyoder had a Twitter conversation yesterday about phylogeny viewers, prompted by my tweeting about my latest displacement activity, a 2D tree browser using the tiling approach made popular by Google Maps.

As part of that conversation, Matt tweeted:
RT @rdmpage: @mjyoder - I think 3D is the worse thing we could do, there's no natural mapping to 3D. <- meh, where's the imagination?

Well, Matt's imagination has gone into overdrive, and he's blogged about his ideas.

3d_tree_browsing.jpg


This issue deserves more exploration, but here are some quick thoughts. 3D has been used in a number of phylogeny browsers, such as Mike Sanderson's Paloverde, Walrus, and the Wellcome Trust's Tree of Life. I don't find any terribly successful, pretty as they may be. I think there are several problems with trees in general, and 3D versions in particular.

Trees aren't real
Trees aren't real in the same way that the physical world is (or even imagined physical worlds). Trees are conceptual structures. The history of web interfaces is littered with attempts to visualise conceptual space, for example to summarise search results. These have been failures, a simple top ten list as used by Google wins. I don't think this is because Google's designers lack imagination, it's because it works. Furthermore, this is actually a very successful visualisation:


I think elaborate attempts to depict conceptual spaces on screens are mostly going to fail.

Trees are empty
Compared to, say, a geographic map, trees are largely empty space. In a map every pixel counts, in that it potentially represents something. Think of the satellite view in Google Maps. Each pixel on the screen has information. Trees are largely empty, hence much of the display space is wasted. Moving trees to 3D just gives us more space to waste.

Trees don't have a natural ordering
Even if we accept that trees are useful visualisations, they have problems. Given the tree ((1,2),(3,4)); we have a lot of (perhaps too much) freedom in how we can depict that tree. For example, both diagrams below depict this tree. In the x-axis there is a partial order of internal nodes (the ancestor of {1,2} must be to the right of the ancestor {1,2,3,4}), but the tree ((1,2),(3,4)); says nothing about the relative ordering of {1,2} versus {3,4}. We are free to choose. A natural linear ordering would be divergence time, but estimates of those times can be contested, or unavailable.

order.png


Phylogenies are unordered trees in the sense that I can rotate any node about it's ancestor and still have the same tree (compare the two trees above). Phylogenies are like mobiles:


The practical consequence of this is that different tree viewers can render the same tree in very different ways, making navigation across viewers unpredictable. Compare this to maps. Even if I use different projections, the maps remain recognisably similar, and most maps retain similar relationships between areas. If I look at a map of Glasgow and move left I will end up in the Atlantic Ocean, no matter if I use Google Maps or Microsoft Maps. Furthermore, trees grow in a way that maps don't (at least, not much). If I add nodes to a tree it may radically change shape, destroying navigation cues that I may have relied on before. Typically maps change by the addition of layers, not by moving bits around (paleogeographic maps excepted).

Trees aren't 3D
There's nothing intrinsically 3D about trees, which means any mapping to 3D space is going to be arbitrary. Indeed, most 3D viewers simply avoid any mapping and show a 2D tree in 3D space, which seems rather pointless.

Perhaps it's because I don't play computer games much (went through an Angry Birds phase, and occasionally pick up an X-Box controller, only to be mercilessly slaughtered by my son), but I'm not inspired by the analogy with computer games. I'm not denying that there are useful things to learn from games (I'm sure the controls in Google Earth owe something to games). But games also rely on a visceral connection with the play, and an understanding of the visual vocabulary (how to unlock treasure, etc.). Matt's 3D model requires users to learn a whole visual vocabulary, much of which (e.g., "Fruit on your tree? Someone has left comment(s) or feedback. ") seems forced.

My sense is that the most successful interfaces make the minimal demands on users, don't fight their intuition, and don't force them to accept a particular visualisation of their own cognitive space.

I'll write more about this once I get my 2D tree viewer into shape where it can be shown. It will be a lot less imaginative than Matt's vision, all I'm shooting for is that it is usable.




Thursday, October 01, 2009

Co-located Collaborative Tree Comparison

Stumbled across this cool visualisation project by Petra Isenberg at Calgary University. Collaborative tree comparison uses a tabletop system to enable two (or more) people to interact when comparing (in this case) phylogenies. I want one!

The system is described in "Interactive Tree Comparison for Co-located Collaborative Information Visualization" (doi:10.1109/TVCG.2007.70568), a PDF of which is available from her web site (which also has a great video entitled "how co-located collaborative data analysis should not take place").



Wednesday, May 27, 2009

Visualizing the Evolutionary Tree of Life

Over on the EOL blog is a summary of a meeting Visualizing the Evolutionary Tree of Life. This sounds like it was a fun meeting, but part of me is suffering from déjà vu. Our community has tossed this subject around for a while now. I recall Tamara Munzner wowing us with the H3 hyperbolic browser at a meeting at UC Davis in 2000 (part of the original NSF TOL workshops, archived herel) -- the image of Joel Cracraft excitedly running up to the display screen to find various birds is forever etched into my brain. TreeJuxtaposer has been around for a while, to not much effect.

We seem to continue to fail to make much progress on this topic, despite meetings such as the EOL one, great reviews of the topic, fancy 3D visualisation, and Mike Sanderson's way kewl wall of monitors.

Maybe progress was made at the EOL meeting, but I don't get the sense that we're any further forward. It would be interesting to work out why we've struggled to satisfactorily solve this problem.

Friday, March 06, 2009

Photosynth for trees - supertrees revisited

It's Friday, so time for some random, half-baked ideas. Imagine that we have a database of evolutionary trees, and these overlap for a set of taxa that we are interested in. How do we summarise these trees? One approach is to make a supertree. It would be useful to display the subtrees that went into making this supertree, if only to give an idea of how much they agree with the supertree. How to do this?

One idea I've been toying with is inspired by Photosynth, from Microsoft labs (it only runs on Windows, sigh). Photosynth takes a series of pictures taken from different angles and stiches them together into a 3D model of the object being photographed:


One thing I like about Photosynth is that you can see the original pictures, so when you move around the view you get a sense of how they have contributed to the overall view. This is easier to see than explain:



Now, imagine if we did this with trees. We could create a supertree as a summary of the individual trees, then have the original trees layered on top. Perhaps we could do this in 3D, so that each individual tree is in a plane that is tilted with respect to the supertree in proportion to how much it disagrees with the supertree:

I think this could be a fun way to explore a set of trees, and it would give one the ability to quickly grasp how well the source trees agreed with the supertree. Note that I'm not (necessarily) arguing that the supertree represents the try phylogeny. Think of it as a convenient way to summarise the individual trees.

Part of what attracts me to this approach is that I think most, if not all, 3D phylogeny viewers (such as Paloverde and the Wellcome tree of life) don't make any real use of 3D, beyond the rather gimmicky (and I find ultimately confusing) ability to fly around a 2D tree. Is there a better way to exploit the possibilities of 3D?

Sunday, October 19, 2008

Monitor envy


Mike Sanderson's wall of monitors is getting some attention. Cool as it looks (and I'm positively green with envy), this strikes me as the LCD equivalent of Science's suggestion that the reader print out a tree on several bits of paper doi:10.1126/science.300.5626.169. If we can fit the planet on a monitor, can't we fit the tree of life?

Thursday, March 20, 2008

Phylowidget


Greg Jordan and Bill Piel have released PhyloWidget, a Java applet for viewing phylogenetic trees. It's very slick, with some nice visual effects courtesy of Processing.
PhyloWidget is open source, with code hosted by Google code. I'm a C++ luddite, so it took me a few moments to figure out how to build the applet, but it's simple enough, just type
ant PhyloWidget
at the command prompt. I got a couple of warnings about missing .keystore files (something to do with signing the applet), but otherwise things seemed to work.
The applet has a URL API, which makes it easy to view trees. For example, try this link to view the Frost et al. amphibian tree (doi:10.1206/0003-0090(2006)297[0001:TATOL]2.0.CO;2).

Monday, August 20, 2007

Internet Explorer -- argh!!!!!


I would prefer to avoid Microsoft-bashing, but today I've spent time trying to get my tree viewer to work under Internet Explorer 6 and 7, and it's hell. Here are the problems I've had to deal with:

Empty DIV bug
On IE 6 the top of the scrollbar overlapped the transparent area when the page first loads. Eventually discovered that this is a bug in IE. It gives empty DIVs a height approximately equal to the font-height for the DIV, even if the DIV has height:0px; (see here for a discussion). I set the CSS for this DIV to overflow:hidden;, and the DIV now behaves.

Opacity
The viewer makes use of opacity, that is, having DIVs that are coloured, but which you can see through. This enables me to add layers over the top of an image. IE doesn't support the standard way of doing this, so styles such as opacity:0.5; must also be written as filter:alpha(opacity=50); (thanks to David Shorthouse for pointing this out to me).

Background transparency
The DIV overlaying the big tree has background-color:transparent;, which means it refuses to accept any mouse clicks on the big tree. Changing the color to anything else meant the DIV received the clicks, so I ended up using a fairly ugly hack to include Internet Explorer-specific CSS for this DIV (idea borrowed from How to Use Different CSS Style Sheets For Different Browsers (and How to Hide CSS Code from Older Browsers)).

z-index bug
The final show stopper was the auto-complete drop down list of taxon names. On IE it disappeared behind the big tree. This is the infamous z-index bug. The drop down menu is a DIV created on the fly, and although it's z-index value (99) means it should be placed on top of the tree (so the user can see the list of taxa), it isn't. After some Googling I settled on the hack of setting the z-index for the DIV containing the big tree to -1 in IE only, and this seems to work.

IE is sometimes good
Sometimes it has to be said, IE has it's good points. The tree viewer failed in part because I'd failed to define a Javascript variable. Somehow FireFox and Safari were OK with this, but IE 6 broke. I defined the variable and it worked. I've also learnt to avoid some variable names, such as scroll. I find FireFox to a better browser for developing stuff, especially if the Firebug extension is installed. However, the Internet Explorer Developer Toolbar is useful if you need to figure out what IE is doing.

Conclusion
It's staggering how much time one can waste trying to cater to the weird and wonderful ways of Internet Explorer. However, the tree viewer should now work for those of you running Internet Explorer.

Saturday, August 18, 2007

Visualising very big trees, Part V

Inspired partly by the image viewers mentioned earlier, and tools like Google Finance's plot of stock prices, I've built yet another demo of one way to view large trees.


You can view the demo here. On the left is a thumbnail of the tree, on the right is the tree displayed "full scale", that is, you can read the labels of every leaf. In the middle appears a subset of any internal node labels. Top right is a text box in which you can search for a taxon in the tree.

You can navigate by dragging the scroll bar on the left, dragging the big tree, or using the mouse wheel (and you can jump to a taxon by name). It has been "tested" in Safari and Firefox on a Mac, I doubt it works on Internet Explorer. Getting that to happen is a whole other project.

The viewer is written entirely in HTML and Javascript, the underlying tree images (and some of the HTML and Javascript) are generated using a C++program that reads and draws trees, and I use ImageMagick to generate actaual images.

Saturday, August 11, 2007

Visualising very big trees, Part IV


Continuing the theme of viewing big trees, another approach to viewing large objects is tiling, which most people will have encountered if they've used Google Maps.The idea is to slice a large image into many smaller pieces ("tiles") at different reoslutions, and display only those tiles needed to show the view the user is interested in. I'd thought about doing this for trees but abandoned it. However, I think it is worth revisiting, based on discussion on the Nature Network Bioinformatics Forum, and looking at the Giant-Ass Image Viewer (version 2 is here), and Marc Paschal's blog.

As an example of what could be done, below is a phylogeny from Frost et al.'s "The amphibian tree of life" hdl:2246/5781, rendered using Zoomify's Zoomify Express. I just took a GIF I'd made of the entire tree, dropped it on the Zoomify Express icon, hacked some HTML, and got this:





Now, I don't think Zoomify itself is the answer, because what I'd like is to constrain the navigation to be in one dimension, to have a clearer sense of where I am in the tree, and to have a search function to locate nodes of interest. However, this approach seems worth having a look at. Looks like I'll need to learn a lot more Javascript...

Saturday, August 04, 2007

Visualising very big trees, Part III

I've refined my first efforts to now highlight where you are in the tree. The trees on display here now show the new look.

Basically I've abandoned image maps as they don't allow me to highlight the part of the tree being selected. After some fussing I switched to using HTML DIVs, which sit on top of the image. This took a little while to get working, CSS and DIV placement drives me nuts. The trick is to give each DIV the style position:absolute;, and (and this is important) make sure that the DIV is written as <div ...></div>, not <div .../>.

The trees now show a pale blue highlight when you mouse over an area you can click on, and if the corresponding subtree has an internal node label, that label is also highlighted. In the same way, if you mouse over the region on the right that corresponds to a labelled internal node, botht he label and the subtree are highlighted. I think this helps make it clear what parts you are selecting, and gives you the option of selecting using a name, rather than clicking on part of the tree.

Friday, August 03, 2007

Visualising very big trees, Part II

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.

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:


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). 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).

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.