Monday, June 7, 2010

PhyloBox: A better way to do phylogenetic trees on the web

A few weeks ago Rod Page posted his experiments with displaying phylogenetic trees on the web using the HTML5 Canvas and JavaScript. I was particularly interested, and a bit threatened, by this post. At the time I had been toying with the exact same idea with the hopes of entering such a solution in the iEvoBio Visualization Challenge. As a response, I needed to step up my game. Here are the steps for going from a simple HTML Canvas rendering a phylogenetic tree to our end result, PhyloBox.

Step 1: Get a bigger weapon

I love tinkering with code and playing with new technologies, but I am far from the top when it comes to browser based smarts. I was going to need some help on this one. My friend Sander Pick was nice enough to spend some time tackling the problem with me. This was particularly exciting to me, as Sander has not spent much time thinking about biology on the web, getting some fresh perspective was just what this needed (in my opinion). He dove right into thinking about how to make trees, and in particular very big-trees, accessible in the HTML5 Canvas in really cool ways. Almost every time we started talking about solutions he would bring up an idea that was entirely new and exciting for this project.

Step 2: Bring trees up to speed

Phylogenetic trees are great, I love them, I have never loved their notation. Parenthetic? Might as well be punch cards. Nexus? Ok, not bad for a text-file on steroids. PhyloXML? Here we go, this might be on to something. Yet, I’m one of those people who feel like XML is sooo 2005, or maybe the year before that. What do we need to make the data within a phylogenetic tree usuable in a web application? My vote, JSON. It is simple, fast, and perfect for applications relying on JavaScript. Although it may not be able to handle some of the more complex tree notation in PhyloXML, I haven't run into that yet.

I went about creating a PhyloXML -> PhyloJSON converter and then Sander and I spent some time refining what exactly the data needed to look like to call it PhyloJSON and make it valuable for web-based visualization. I figured that what we do isn’t going to be the end-all of phylogenetic data on the web, so we have included the converter as a REST service for you to use (see here). I have near-future plans to make parenthetic->PhyloJSON and Nexus/NeXML -> PhyloJSON converters also, but would like to gather some feedback first.

PhyloJSON is primarily a conversion of the elements of phyloXML (right now a limited subset, but I'm willing to expand rapidly to match demand) to a JSON object. We changed some of the element names to reduce their length and we added a bit more top level information to define the environment (e.g. where to root the tree for viewing, what color to draw the background, where to position the tree, etc). In the process, we also flatten that tree, we weren't fond of the super nested structure of PhyloXML when we wanted to reference nodes in the trees with JavaScript very quickly. You can see the spec, here, and you can see an example of PhyloJSON here.

Step 3: Build a Web-Publishing Framework for Phylogenies

We wanted people to not only be able to view a phylogeny on the web, we also want them to be able to edit them to their liking (while still giving an option to just view). I have been doing some development on Google App Engine anyway (see GeoPhylo), so I was comfortable building the system there. I wanted to free myself from any hardware maintenance. But secondly, for reasons expanded below, I wanted to allow for a lot of requests at busy times (elasticity) without having to question my server admin skills. Finally, I wanted to take advantage of the free quotas, good amount of free data storage, and super-simple user management that comes with App Engine; users with existing Google accounts will automatically have accounts on our system.
The features of our framework are many.
  • Anonymous tree viewing. This allows users to use our technology without the need to actually sign-in or authenticate. So, for example, our REST services will take either a PhyloXML file or PhyloJSON file (zip supported for big ones), and return all the needed bits to view that tree on the web without any authentication (we are working on OAuth as well though for greater control including versioning and stored tree defaults). You can even use our tree editor anonymously (although there are some good bits you might like to sign-in for).
  • User based project management. This allows users to save and return to phylogenetic trees that they own. It also allows users to invite collaborators to edit the same tree. Or fork their tree into a new version, preserving the older ones to track progress or changes and track how many much the tree is being viewed.
  • Creative commons publishing. The system is open from the start. This may scare you, but let me explain. When a tree is uploaded to our site, it is assigned a UUID. If you know the UUID, you can see the tree, but can’t edit it unless you own it. That means that you can share the URL with anyone you want, but because the UUID has 16^32 combinations, no one should stumble upon it. This is a very similar method to the one that Google Docs uses if you use their ‘Get the link to share’ option. This will ensure that you can use the tree that you own for anything you darn well please.
  • Project forking. This is something we are excited about, and hope it doesn’t make you run the other way. If you share a link to a tree with me, but I am not an owner or collaborator on that tree, I can’t edit it. That’s too bad because I may want to show you some other branch coloring scheme that would look better, or convey the data better. In the spirit of science, we made it so that I can fork the project. When I fork it, I get a completely new UUID to a new tree object with all the same info, which I can edit and re-share with you. The history of ownership and contribution is maintained. You will always be the original author, and if anyone forks the tree that I made from yours, you are still original author. The entire ‘lineage’ of that tree is also kept so that we can reconstruct where changes came from who added what. Cool? Here is an figure of the concept.
  • Project management console. This aspect is far from complete, but in this area, we will give original authors ways of seeing where there idea has gone, see how often it is being viewed etc. For now, you can see a list of your trees and number of views.
  • A growing API, where advanced users can take advantage of each part of our system, without any use of the graphical UI.
With the project management in place, we give people a lot of ways to take advantage of our phylogenetic tree viewing technology (which we’re getting to, relax). Let us know what you would like to see and we will think about it in all our free time ;). Just kidding, really, let us know what you would like to see.


Step 4: Build Better Web-Publishing Methods for Phylogenies


So now we have methods for you to control, create, and share your trees within our site. But what if you want the trees on your site? Yes, you could use our super simple ‘output image’ button and stick that image on your website. But don’t we all want something more than that? Not only do you want to show the tree on your site, you want to control the starting view (dendrogram or phylogram, branch lenth or not, camera starting angle) shown to users. You probably even want the tree being to be interactive. Okay, now you are getting pushy, we had to think about this one for a while. We knew that we had this Canvas element where we would render your tree, but how do you share a Canvas efficiently? And how do you make sure that all those JavaScript libraries are getting incorporated at the right times? And how can we continue to develop our services with the most up-to-date technologies next year, and still give you the best looking tree that you published on your website last year? Well, other people have already answered these questions.

If you look at YouTube or SlideShare, their widget always looks the same across the internet, regardless of when someone actually added it to their website. We wanted that! The problem is, we weren't going for a Flash based solution, so getting it wasn’t so straight forward. I’ll spare you a lot of the boring details on this, but we did it. After a lot of tinkering, we got a pure JavaScript widget that works in much the same way as a YouTube video. Here is an example of a PhyloBox Widget:







We wanted to make the code to add a widget to your page super small and easy to just plop in there. Much like the EMBED code you may be familiar with from a YouTube video, we achieved a nice small package. Here is the code it took to embed the widget above:


<div id="PhyloboxEmbed" >
<div width="375" height="344" style="width:375px;height:344px;" id="phylobox_phylobox-1-0-ecfa61d1-db2b-49a3-9c05-8f4f682e68d9" class="phylobox_embed_parent"><a href="http://phylobox.appspot.com"><img src="http://phylobox.appspot.com/api/image.png?k=phylobox-1-0-ecfa61d1-db2b-49a3-9c05-8f4f682e68d9" width="375" height="344" /></a>
</div>
</div>


In fact, you can click the ‘open tag-end tag’ icon on the widget itself and grab the code to put in your website! The interaction with that tree isn’t perfect yet. We just haven’t had time to get mouse or gesture based control yet, but go ahead and play with your arrow keys, or your A or Z keys or shift+V keys. There are others, but a lot of the interaction is being developed, so we will be changing a lot of it shortly. What is also cool here, is that while the rending of the tree isn’t perfect yet, as we improve our methods, the widget on this page will always show the most up-to-date version.
Some small caveats. The widget works on most all personal websites, so we assume your ScratchPads page or EOL Species Page can handle it no problem (but if not, we will work to make it happen real quick). However, blogs on BlogSpot don’t really like it, in fact flat out reject it, when you stick JavaScript in your blog posts. Well, “screw that” we said. In order to get around this, we made a small Gadget for you to add to your blog, you can see it in our sidebar (just the little link to PhyloBox). It just looks for the PhyloBox Widget Div element and if it exists in the current post, pulls in the necessary JavaScript to display your tree correctly. To get it running on your blog see our help page.
What was that? A YouTube sized display is too small for you to show a tree? Yeah, good point. Well, a YouTube sized display is probably too small to show a video a lot of times too. But that is just the reality of the web, real estate is needed for all sorts of things. That is why you can control the starting size right in the small snip of code, and that is also why YouTube so kindly has that fullscreen button on every video, and so do we! How cool is that? Because we hope people plug these in all over the web, we also expect (hope for) a large number of simultaneous requests. Oh, I should mention now, we haven’t even gone as far as scratching our heads over out-dated browsers. That would be like building highways for concrete wheels, we’re just not going to do it.
Buuuuuuut... If you really hate all of this and still just want to be able to put together a phylogenetic tree for the web and just insert an image of it on your website, we've got you covered.



is just,


<img src="http://phylobox.appspot.com/api/image.png?k=phylobox-1-0-ecfa61d1-db2b-49a3-9c05-8f4f682e68d9" style="max-width:300px; max-height:300px;" />


Or obviously you can just download the image and host it from your own site.

Step 5: Romance them with the framework, steal their hearts with the canvas
Displaying data on the canvas is easy, displaying information on the canvas is less easy, adding interaction and user control to that information is downright nutty fun. I used my previous experience drawing phylogenies (GeoPhylo) to do a first pass implementation to just display a tree on the canvas. Following that, Sander and I had a couple of build up sessions to figure out what exactly Version 1.0 should include. It was a lot. Primarily though, we wanted several different view types: Phylogram, Dendrogram, Circular-Dendrogram, and 3D. We also wanted to be able to display very big trees in useful ways that transition to more the more familar views (dendrogram or phylogram) when only a small part is within view. And we wanted a handful of tools to be ready from the get-go, but the ability to add a lot more as we move forward.

Sander began writing a rendering engine for the trees. The idea was one engine for all view types, 3D or 2D. A few days later I went by his house for a beer and he showed me the engine at work. At that point he was trying to push 1000 node+branch objects into the canvas, spinning, at up to 60fps with shading. It was on.
We toned it back for display on our site to ~12fps and in a widget to just 8fps. This will keep a blog post with a couple tree widgets from completely sucking up all your CPU. Then engine is incredibly efficient though. We can render the tree in 3D in your browser and give you complete control over the editing tools and display of that tree. If you would like to see an example of a big tree, see the Frost et al. (2006) Amphibian tree (see phyloxml.org) rendered in your browser, here

Another exciting thing we did was add support for URIs in the nodes. This is built into phyloXML and we incorporated it into our phyloJSON. By enabling the URI tool in the editor, a user can link from a node to a GenBank record, a video, an image or anything you like. This tree has a few URI nuggets for you to discover (you must enable the URI tooltip and select the primary URI first).

The engine also allows for multiple tree objects on the same canvas, although we haven’t unlocked this feature on the site yet.

Conclusion: PhyloBox

We made PhyloBox flexible enough that you can use it from afar to just display your data or you can dive in and use all these features. We have already been thinking of some other important features to add if people like it. For example, why draw your tree once for publication and once for the web? We are working on export of high quality TIFFs or SVGs directly from the browser, for now PNGs will have to do. You like that? Well how about publishing a link to your interactive tree right in your paper? How about publishing the Widget itself right in a PlosOne paper? You don’t want people to fork your project? We are thinking about adding an opt-out option, but frankly don’t like it, it seems anti-scientific. We would like to hear your feedback on this one, maybe we could let you opt-out for only a limited amount of time (say 1 year) for a tree? You want to develop something home-grown to display a tree you customized on PhyloBox? You got it, use our lookup service to just retrieve the PhyloJSON object for one of your trees. Want commenting on trees? We can do that, just need to know the demand. We were thinking of having commenting on individual nodes, branches, or trees. I know having only phyloXML support can be a drag, I should have at least a Newick converter and upload available in the next week.
We really hope people like the PhyloBox concept. If not, we’d like to hear that too, because we need to know if you want us to develop this into the future. PhyloBox is somewhere around Beta, but the iEvoBio deadline is right now, so that is that. There is so much more we can add to this!

7 comments:

blJOg said...

Great stuff! Like the idea of forking and don't see why researchers wouldn't like it and I think you are right that it would be best not to have an opt-out.
I think the idea of commenting on trees, nodes and leaves would be brilliant and to be able to link to those comments would be great. Even better if a user could keep control of his comments to make further edits or even delete it one day.
I know that PhyloXML is the new format for phylogenetics but all my trees are in Nexus (it might be an antiquated formatted but all the software I use saves in that format and it is short and simple). I look forward to a Nexus/NeXML -> PhyloJSON converter.

Rod Page said...

@andrewxhill Neat stuff. Is it just me, or are the branches in the example tree image a bit wonky? Is there a reason that they aren't rectangular?

Andrew W Hill said...

blJOg, thanks! I'll have a first pass nexus uploader in a few days, promise.
Rod thanks also! Yeah, branches are a bit wonky still just because of the way that we are drawing the reference point in 3D space for the bend. We'll fix it up shortly.
Here was our pure 2D version that we are moving towards, http://phylobox.appspot.com/tree/old?k=phylobox-1-0-ecfa61d1-db2b-49a3-9c05-8f4f682e68d9

sander said...

Actually, the branches are perfect rectangles. The wonkyness is the correct mathematical result of placing the branch corners on the same plane as the node and its children. This causes some nodes to have one branch corner at a different depth than its partner. Greater depth must mean different x,y screen position in order to maintain perspective...

This technique of maintaining the node-children plane at branch corners seems to be the intuitive approach. However, it makes sense that this wonkyness could be a nuisance when the user wants to see their tree in only 2D. One method to improve would be to just greatly reduce the z-step... which is currently equal to the x-step. ?

Andrew W Hill said...

@blJOg We now have Newick support. It covers names and branch lengths, but I need to go back and mess with branch lengths plus support values. Enjoy.

Andrew W Hill said...

Just starting to add some mouse support for tree navigating. Double-click to zoom, still need to press 'z' to zoom out, also drag the tree to add spin. You may need to refresh this page before the widget picks up the new code.

Andrew W Hill said...

Actually, dblclick in the widget is a bit funny, removing for now.