Viewing missing methods/software, part VII: PHP+GD

I was getting dissatisfied with Processing for visualizing missing methods. It was nice to have animation of the diagrams, but it was just too brittle: it would only work in certain browsers, it stopped working sometimes when you moved between tabs or windows, it was hard to update and keep working. This is probably more due to my lack of experience in the language and the odd way I was using it (read a variable stored in Javascript on a page to talk to a PHP script to talk to a Postgres database and display the results in real time) than any inherent flaws in it. I had thought about going to Flash, but that also involved learning a new programming language. I had recently started using PHP with GD to visualize progress of my jobs on Duke's computing cluster and found it easy to use (though I'm having issues with transparency). I decided to try this with the method visualization (I wanted to get TreeTapper cleaned up a bit more before a job interview next week). I wrote a script that reads information stored in GET variables and saves an image and image map. In front of this I wrote a controller script that only calls the drawing script when an entry in the database is newer than the saved image and image map (using ideas from my Google Summer of Code student Paul McMillan, who put sophisticated caching in his DBGraphNav). The image and image map are displayed in an iframe in the calling page. There's a Javascript function that calls the controller script as a user chooses which options to display. There's also a Javascript function that uses a Panel object from YUI to display a lot of information about each node on the diagram on mouseover in a floating panel. This is a lot more flexible than the Processing implementation. For example, you can now go to a summary page for each node or click on an entry in the floating panel to go to an info page on just that item (such as a program).  Caching the images makes display a lot faster, though only a subset of possible combinations can be cached. The cache of images also provides some nice pictures for screen savers or talks.

You can try out the new interface here.

Here's a picture of the new display:

And some of the cached images:

Visualizing trees

We recently had a community summit at NESCent on directions for the future. As part of the biodiversity and phylogenetics breakout group (see notes here), one thing that came up was a need for better ways of visualizing trees [one good idea was inviting Ben Fry to NESCent to work on this]. Rod Page suggested putting tree visualization in TreeTapper as a category, which is a great idea, as there are dozens of programs (see partial list at Felsenstein's site). But why, with so many programs, do people feel that so much more work is needed?

Well, based on behavior, it's obvious that current solutions don't work. NESCent has a fairly sophisticated set of users and builders of trees. When they need to view a large tree (hundreds to thousands of taxa), they don't use any sort of cool tree stretching or zooming program -- they find an old Mac, open Paup in Classic, and print out a tree over multiple pages, which they then assemble using tape and scissors. I think the reason they do this comes down to resolution of paper versus monitors (see some of Edward Tufte's books for a more general and informed discussion of this). My 1920 x 1200 pixel giant Apple Cinema display monitor (a perk loaned to all NESCent postdocs) can display fewer than 600 distinguishable horizontal lines (one pixel thick with one pixel between them). Our laser printer has a resolution of ~1200 DPI, suggesting that it could print this many lines in about one inch (I might be slightly off if there are some sort of constraints on dot geometry, but the basic idea still holds). By this calculation, my entire monitor display can be reproduced pixel by pixel in a few square inches. Plus, a printed tree can be arbitrarily large (Michael Donoghue described one several feet in diameter). Speed of visually parsing such a tree is related to how quickly the eye can move around a page: focus closely on one section to read the taxon names, jump to look at the overall picture, etc. On a screen, one would have to move the mouse around and wait for the screen to update. Even with tremendous zoom, there are only 1200 vertical positions my cursor can occupy (assuming cursor resolution == screen resolution) -- a tree larger than this, and there's no way to display even a cartoon of the whole tree on one screen in such a way that moving the mouse can select just one taxon (other than a nesting of zooms within zooms). In contrast, even on a 11" high piece of paper, with half inch margins and default line spacing, I can print a column of 155 taxon names (using 4 point Times font, about the size used on insect labels), all easily readable. Just a few pieces of paper provide much more resolution than possible on a costly monitor. It's similar to the comparison between a paper map and a GPS navigation system (or Google Maps/Earth): in a given area, the paper map has much more detail. The advantage of the navigation system (besides the whole navigation bit) is that it allows you to zoom in and out for an unlimited amount of information. For looking at a tree, though, as for visualizing a trip, seeing the entire thing with a great amount of detail rather than zooming in and out constantly can be much easier.

One solution is to have even higher resolution displays (see Mike Sanderson's wall of monitors [taken from his web page] at the end of this post, for example). I think that there will be limits to this, and we might have to wait for other fields to advance first. Instead, it might be worthwhile to work on better ways to print out large trees on tiled pieces of paper. Imagine software that takes a set of bootstrap trees and can create a PDF you can print out and stitch together showing support values and branch lengths, perhaps with reconstruction of characters in color at the nodes, too. It seems appallingly low-tech and yet rather useful. As far as I know, Classic Paup is the only program that can do this, though Mesquite has some options for tree printing that might allow this [this will be much easier to know once this section of TreeTapper's database has been filled in]. The downside is that this doesn't help much the issue of displaying trees in papers, but there, perhaps some summary graphic would work better.


image from http://loco.biosci.arizona.edu

Flash rather than Processing?

I'm now wondering whether Processing was a bad choice for visualizing missing methods (though it's still better than the horribly slow Google Maps implementation). It results in Java applets, which can take quite some time to load on a page (see other general criticisms here). I had to do some hacky things (use Java code rather than stuff built into Processing) to get the applet to talk to Javascript on the page to find what items a user wants to examine, which might not be stable as Processing develops [and it probably prevents me from just converting to Processing.js or the like]. Also, on the stable site (http://www.treetapper.org, rather than http://treetapper.nescent.org), the existing Java applet I made doesn't work (to see a working version, go here). I've tried playing with the code (changing it to point to the stable site, of course, and looking at other potential issues) and it still doesn't work. Flash animations seem to work much faster and more stably across many browsers. Some versions (>4.0.5, <5.3.0) create Flash animations (the code's been moved into a separate install for later versions of PHP), so I could use that. I could just code it in ActionScript and somehow compile it. Either way, I don't know anything about coding Flash animations, how they can connect to the database and page elements, how to write them without depending on expensive software, etc., so it'd mean a bit of work to learn a new language. Any ideas?

Viewing missing methods/software, part VI: Processing done!

I've written the code to generate the missing methods/software tree diagram using Processing. The relevant page is http://treetapper.nescent.org/findneed.php . I've designed it so that as data streams back from the database via a PHP script, Processing draws this on the diagram in real time. As users update the sortable list of options (tree type, general question, etc.) (using YUI drag and drop), a Javascript function updates the string (stored in a Javascript variable) that is passed to the PHP script. Processing checks this string (so, Java talking to a Javascript object), and if it has changed, Processing closes its old connection to the PHP script and opens a new one using the new options. It thus dynamically updates the chart and is far faster than Google Maps API. It's also easy to do sophisticated animations easily in Processing: currently, I have the nodes flying out of their parents, zooming and shifting the image, and point highlighting on mouseover. These actually don't slow down the rendering: I have the script written so that it only adds a new node to the diagram once the previous node has reached its destination, which sets an upper limit on rendering speed, but I override this and put many nodes on the tree at once if there's a backlog (>10 nodes read from the server but not drawn yet). There is rarely such a backlog, indicating that nodes are being drawn as fast as the server is passing them to Processing. It's pretty cool to be able to visualize where our field needs work (or, rather, where I need to fill in the database) using a dynamic interface, and also surprising that it wasn't too bad to program (especially considering I didn't know Processing/Java, Javascript, PHP, or Postgres when I started this in November 2007). Here is a video showing the new site being used (also available here); you may need to widen your browser window to see it all. As always, suggestions are encouraged.

Viewing missing methods/software, part V: Processing

In my previous post, I was  bemoaning the slow speed of the visualization chart using Google Maps. Looking around in the Google Maps group, it seemed that there wasn't a good way to speed up the drawing of many markers, except for drawing them in another program first and storing them on image tiles. Since I was going to have to draw markers in a different program anyway, I decided to try using such a program by itself without involving Google Maps. First, I thought to create a static image using GD with PHP and then do an image map on top of that with javascript, but GD wasn't working on the NESCent server (this was fixed in just a couple of hours, as is common with NESCent's great tech support). While it was being fixed, I decided to learn Processing — I've been impressed by the quality of some of the diagrams it creates, and having a dynamic diagram might be more useful for users. It has good documentation and can parse XML, so within a few hours, I learned enough to be able to create the diagram below. 

Following advice from the TreeTapper design consultant (my wife), I made the nodes smaller and changed the color slightly, but otherwise it is the same as the Google diagram (though I don't have popups or mouseovers working yet), and is much faster to create. It does require users to have Java installed in their browsers, but might allow cool features later on.

Viewing missing methods/software, part IV: Sort of working

Well, I sort of have the visualization working. Users can choose which elements to graph (on Firefox) by dragging boxes to move them above or below a plotting line, and they can choose to limit to plotting only one of many options. See below.

On clicking the  update chart button, a tree is plotted using the Google Maps API, with branches colored based on whether they have no methods or software, methods but not software, or both methods and software [I originally had it update the map automatically on any change, but this is too slow]. Users can click on nodes to get an info window showing the choices made going from the tree root to the tips and links to any relevant software or methods. Just mousing over a node tells a user what option that node represents (i.e., "Treetype: Unrooted, polytomies, incomplete tree"). If a user has chosen just one setting for an option (as for criterion, below), the edge leading to that node is shorter and light gray edges are shown to indicate the options not examined.  See below (click to make larger).

The end product is beautiful and information-rich. It's also VERY slow. It takes literally minutes to generate the plot, and then >10 seconds between clicking on a node and getting the info window. Zooming in or out or moving the plot also take an agonizingly slow time. Getting info from the script that talks to the database to make code for the map takes a while, about 30 seconds, but the real slowdown comes when drawing the map. Google maps are slow with many markers and polylines: the map above has 221 markers and even more polylines, with the three circle polylines having 360 points each (using fewer makes a plot that's too rough). I'll have to decide what to do. I'd stayed away from Processing due to usability concerns, but it seems Google Maps isn't so great, either. I've read a little about generating image tiles rather than markers to speed up the map -- I'll look into this and other options. 

Viewing missing methods/software, part III: Table views

Repeat of the design goals for viewing missing methods/software: 

1. Allow users to see on a tree (using branch coloring) which questions don't have methods, which methods aren't in software, etc.
2. Allow users to arrange the order in which things are displayed: question->criterion->method, or question->character type 1 -> tree type -> branch length type -> data format -> software
3. Allow users to filter by option (only show methods relating to DNA data, for example)
4. Make it fast, intuitive, etc.

I think a way to address these is to create table views; one has all the available methods ("actualmethods"), one has all the available methods and software ("actualsoftware"), and one could have all the imaginable combinations of all options ("biggie"). That way, all the database logic for combining the primitive tables (method->methodtotreetypetobranchlengthtype->treetype, for example) is taken care of at the view creation step, rather than requiring it all to be created on the fly when a user re-orders options. [Aha: so this is a reason for using MVC]. To draw the tree of methods/software based on user choice, one gets the tree structure by looking in the [actually hypothetical] "biggie" table; combinations (edges on the display tree) present in the "actualsoftware" table are shown in the "+methods +software" color (purple?), combinations not present there but in the "actualmethods" table get the "+methods -software" color (black?), and others get the "-methods -software" color (gray?). The only problem with this is the size of the "biggie" table view: except for built-in relations between general and posed questions and posed questions and relevant combinations of characters (see schema), it's basically a massive cross join. That means that if there are 2 data formats, 6 tree formats, and 7 platforms, the table has 2 x 6 x 7 = 84 rows.  The actual "biggie" table, having info on all the imaginable options (input formats, tree types, character types, criteria, etc.) would currently have 1,361,817,600 (1.3 billion) distinct rows. Instead of creating such a huge table, I will have a view ("generaltoposedtochartype") containing the essential relations between general question, posed question, and character combinations (only 2,480 rows currently) and then just have the program returning possible branches for the tree know that all the other options can essentially be cross joined.

I had a bit of trouble creating the initial "actualmethods" view efficiently; Hilmar Lapp, an IT guru here at NESCent (codes for BioPerl, organizes hackathons, organizes people) edited the query to make it more efficient and eliminate return of duplicate rows (without using "distinct"). Below I've posted the sql statement used to make these views in case it's useful for others (or for me in the future).

-- All actual methods

CREATE VIEW 

actualmethods

(

actualmethods_generalquestion,

actualmethods_posedquestion,

actualmethods_char1,

actualmethods_char2,

actualmethods_char3,

actualmethods_treetype,

actualmethods_branchlengthtype,

actualmethods_criterion,

actualmethods_method

)

AS

SELECT

pq.posedquestion_generalquestion,

pq.posedquestion_id,

  cc.charactercombination_char1, 

cc.charactercombination_char2, 

cc.charactercombination_char3,

mttblt.methodtotreetypetobranchlengthtype_treetype,

mttblt.methodtotreetypetobranchlengthtype_branchlengthtype,

   mc.methodtocriterion_criterion,

mttblt.methodtotreetypetobranchlengthtype_method

FROM

methodtotreetypetobranchlengthtype mttblt,

methodtocriterion mc,

methodtocharactercombination mcc,

methodtoposedquestion mpq,

posedquestion pq,

charactercombination cc,

posedquestiontocharactercombination pqcc

WHERE

methodtocriterion_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_charactercombination=charactercombination_id

AND  

methodtoposedquestion_method=methodtotreetypetobranchlengthtype_method

AND

methodtoposedquestion_posedquestion=posedquestion_id

AND

posedquestiontocharactercombination_posedquestion=posedquestion_id

AND  

posedquestiontocharactercombination_charactercombination=charactercombination_id

;

-- all actual methods and software

CREATE VIEW 

actualsoftware

(

actualsoftware_generalquestion,

actualsoftware_posedquestion,

actualsoftware_char1,

actualsoftware_char2,

actualsoftware_char3,

actualsoftware_treetype,

actualsoftware_branchlengthtype,

actualsoftware_criterion,

actualsoftware_method,

actualsoftware_dataformat,

actualsoftware_treeformat,

actualsoftware_applicationkind,

actualsoftware_platform,

actualsoftware_program

)

AS

SELECT

pq.posedquestion_generalquestion,

pq.posedquestion_id,

cc.charactercombination_char1, 

cc.charactercombination_char2, 

cc.charactercombination_char3,

mttblt.methodtotreetypetobranchlengthtype_treetype,

mttblt.methodtotreetypetobranchlengthtype_branchlengthtype,

mc.methodtocriterion_criterion,

mttblt.methodtotreetypetobranchlengthtype_method,

pdf.programtodataformat_dataformat, 

ptf.programtotreeformat_treeformat, 

ppak.programtoplatformappkind_applicationkind, 

ppak.programtoplatformappkind_platform, 

  pmcc.programtomethodtocharactercombination_program

FROM

methodtotreetypetobranchlengthtype mttblt,

methodtocriterion mc,

methodtocharactercombination mcc,

methodtoposedquestion mpq,

posedquestion pq,

charactercombination cc,

posedquestiontocharactercombination pqcc,

programtodataformat pdf,

programtotreeformat ptf,

programtomethodtocharactercombination pmcc,

programtoplatformappkind ppak

WHERE

methodtocriterion_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_charactercombination=charactercombination_id

AND  

methodtoposedquestion_method=methodtotreetypetobranchlengthtype_method

AND 

methodtoposedquestion_posedquestion=posedquestion_id

AND 

posedquestiontocharactercombination_posedquestion=posedquestion_id

AND  

posedquestiontocharactercombination_charactercombination=charactercombination_id

AND 

programtomethodtocharactercombination_methodtocharactercombination=methodtocharactercombination_id

AND 

programtomethodtocharactercombination_program=programtodataformat_program

AND 

programtodataformat_program=programtotreeformat_program

AND 

programtotreeformat_program=programtoplatformappkind_program

;

-- all general+posedquestions+chartypes

CREATE VIEW

generaltoposedtochartype

(

generaltoposedtochartype_generalquestion,

generaltoposedtochartype_posedquestion,

generaltoposedtochartype_char1,

generaltoposedtochartype_char2,

generaltoposedtochartype_char3

)

AS

SELECT

generalquestion_id,

posedquestion_id, 

charactercombination.charactercombination_char1, 

charactercombination.charactercombination_char2, 

charactercombination.charactercombination_char3

FROM

charactercombination,

posedquestiontocharactercombination,

posedquestion,

generalquestion

WHERE

posedquestion_generalquestion=generalquestion_id

AND

posedquestiontocharactercombination_charactercombination=charactercombination_id

AND

posedquestiontocharactercombination_posedquestion=posedquestion_id

;

-- all conceivable combinations of parameters other than question and chartype (a massive cross join, probably not used)

CREATE VIEW

crossjoinoptions

(

crossjoinoptions_treetype,

crossjoinoptions_branchlengthtype,

crossjoinoptions_criterion,

crossjoinoptions_dataformat,

crossjoinoptions_treeformat,

crossjoinoptions_applicationkind,

crossjoinoptions_platform

)

AS

SELECT 

treetype_id, 

branchlengthtype_id, 

criterion_id,

dataformat_id,

treeformat_id,

applicationkind_id,

platform_id

FROM

treetype,

branchlengthtype,

criterion,

dataformat,

treeformat,

applicationkind,

platform

;

Viewing missing methods/software, part II

It appears the strategy of using Google Maps with YUI display of items to add to the map will basically work. Rather than doing drag and drop between YUI datatables, I'm using just the drag and drop YUI code on a list of options, each with the possibility of limiting it to one item (for example, one can first organize by optimality criterion, deciding to show all or just likelihood). The interface is based on the YUI example, but with just one list, with one element of a different color so that options placed above this element appear on the tree while ones below do not (inspired by "the line" on Google Summer of Code's mentorship application). I originally thought of having two lists side by side, allowing people to move elements from one list to the other, but this was too wide for some screens once the possibility of options selection was added. 

I've also gotten a plain white Google Map (to replace traditional geographic maps) working, as well as overlays. Google maps have a wrapper for XmlHttpRequest called GXmlHttp that should make refreshing the chart based on user-sorted options possible. Now the question is how to efficiently recover information from the database to draw the tree, highlighting which branches lead to software+methods, just methods, or nothing.

Viewing missing methods/software

The key interesting thing about TreeTapper for me is the ability to find missing methods or software. Any list of software and methods will tell you what's available (and isn't trivial to make), but for developers, finding what doesn't exist yet is key. At first, I was just doing a typical treeview (not in the phylogeny sense, but in the nested series of folders sense):

I started adding the beginnings of  bar plots (the red squares above) to show the number of techniques/question available for each topic. The problem with this is that it's very hard to get a quick overview of what's missing: a user has to drill down into each section and remember what's there (sensible display of some of this in with bar plots might help, but it's still not great).  But thinking about it, what would be good to show is an actual tree: for a given starting point (such as a topic: speciation rate), and then all possible descendants (such as all possible questions for this topic). Those descendants available in methods/software get one branch color (say, black), those not get another branch color (gray) [though it might be good to distinguish those present in methods but not software]. Here's a hand-drawn example for the basic idea:

And with colors and labels:

Under this approach, it's easy to distinguish areas with methods/software available (black/solid) from those lacking methods or software (gray/translucent). In the example above, the central dot represents a topic, the first circle represents questions, the second circle criteria, the third perhaps character type, etc. Derrick Zwickl had the good suggestion to allow users to set the order in which options are plotted; I'd also like to allow users to fix certain values (only look for missing methods under a likelihood criterion, for example).

The problem is that this is just a dummy layout, drawn in Apple Keynote, not actually a working image. The question becomes how to make it. I'm thinking of first having a YUI table with the various options to plot (criterion, method, character types, etc.), and then having a second table (or allowing ranking on the first table) where users can drag the options to plot them on the tree in the given order (see an example of something grossly similar here). One problem may be writing the logic to be able to look at all the options for variable Y when it descends from variable X, including which ones are and are not available, when what X and Y are is up to the user (perhaps comparing a cross-join and a left-join postgres table, or something like that, would be the key). Another question is how to actually generate the plot. There are  various Java libraries for interactive data plotting (the first thing I would try if I went this route would be generating an interface with Processing), but many of them failed when I tried them with the most recent version of Mac's Safari, and Java online (and on the desktop, too) always feels a bit clunky to me. There are various ways to make plots on the web (such as Google Charts and Yahoo Charts), but they only have a few mouseover options. I'm actually thinking of using the Google Maps API for this. Using that, plotting points, lines, and areas is now possible, and users can get information on nodes by clicking on them and one can add various javascript functions called onmouseover, onclick, etc. Users will be able to zoom in on parts of a tree. Finally, one can add custom map tiles to replace the Google tiles; in my case, I'd just have a white background, and do all the plotting with polylines and the like. This sort of use of Google Maps been done before; I remember Katy Böhner mentioning this in a talk (though I couldn't find anything on her lab's website), and there are other examples online. 

Well, we'll see how it goes. As with all posts, please feel free to make suggestions in the comments.