A database of everything

Nothing like a little hubris first thing Monday morning...

After various experiments, such as a triple store for ants (documented on the Semant blog) and bioGUID (documented on the bioGUID blog), I'm starting from scratch and working on a "database of everything". Put another way, I'm working on a database that aggregates metadata about specimens, sequences, literature, images, taxonomic names, etc. But beyond "merely" aggregating data I'm really interested in linking the data. Here are some design decisions I've made so far.

The first is that the database structure used to store metadata uses the Entity–Attribute–Value (EAV) model (for some background see the papers I've bookmarked on Connotea with the tag entity–attribute–value). This tends to send traditional database managers into fits, but for my purposes (storing objects of different kinds with frequently sparse metadata) it seems a natural choice. It's a little bit like a triple store, but I find triple stores frustrating when creating a database. Given the often low quality of the incoming data a lot of post-processing may be needed. Having the data easily accessible makes this task easier -- I view triple stores as "read only" databases. The data I store will be made available as RDF, so users could still use Semantic Web tools to analyse it.

Each object stored in the database gets an identifier based on a md5 hash of one of it's GUIDs (e.g., PubMed identifier, DOI, URL), a technique used by del.icio.us and Connotea (for example, the md5 hash of "http://dx.doi.org/10.2196/jmir.5.4.e27" is d00cf429c001c3c7ae4f2d730718dcc8, hence the Connotea URI for this article is http://www.connotea.org/article/d00cf429c001c3c7ae4f2d730718dcc8). The URIs for the objects in my database will also use these md5 hashes. The original GUIDs (such as DOIs, etc.) are stored within the database.

Much of the programming for this project involves retrieving metadata associated with an identifier. Taking the code I wrote for bioGUID as a starting point, I've added a lot of code to try and clean up the metadata (fixing dates, extracting latitude and longitudes and such like, see Metacrap), but also to extract additional identifiers from text. The database is fundamentally about these links between objects. Typically I write a client for a service that returns metadata for an identifier (typically in XML), transform it to JSON, then post process it.

Another decision is that names of genes and taxa are treated as tags, postponing any decision about what the names actually refer to, as well as whether two or more tags refer to the same thing. The expectation is that much of this can be worked out after the fact (in much the same way as I did for the TbMap project).

The database is being populated in two ways, spidering and bulk upload. Spidering involves taking an identifier, finding any linked identifiers, and resolving those. For example, a PubMed identifier may link to a set of nucleotide sequences, many of which may link to a specimen code. Bulk upload involves harvesting large numbers of records and adding them to the database.

The initial focus is on adding records related to TreeBASE, with a view to creating an annotated version of that database such that a user could ask questions like "find me all phylogenies in TreeBASE that include taxa from Australia."

How Shall I Integrate Thee? Let Me Count the Ways...

Leigh Dodds has a nice post How Shall I Integrate Thee? Let Me Count the Ways... about different ways to integrate data.

• The one where we share identifiers
• The one where we're describing the same thing
• The one where we're speaking different languages
• The one where we're using different units
• The one where we're speaking at different levels of abstraction

Apart from the suggestion that Leigh has been watching way too much Friends, there's much food for thought here. I suspect that "The one where we're describing the same thing" is the one I'll be making most use of.

In Rethinking LSIDs versus HTTP URI I argued that most applications will use HTTP URIs, which makes them accessible, but not terribly useful as identifiers, the reason being that I think it is unlikely that people will reuse HTTP URIs ("The one where we share identifiers"). A good example is Connotea, which has its own URIs for each paper its users bookmark. I won't use these URIs as identifiers in my database (if only because if a user resolves them, they get taken to Connotea's web site, not mine). However, I will store any PubMed and DOI identifiers, so that somebody aggregating information from Connotea (say to retrieve user tags) and my database (say, to get links to sequences and specimens) can work out that the Connotea URI and my URI are talking about the same thing.

Metacrap

Time for a rant. I spend a lot of time fussing with records from sources such as GenBank and DiGIR providers, trying to extract strings that might be identifiers, with a view to linking sequences to specimens (and thus to localities), sequences to publications, publications to GUIDs, etc. The goal is to be able to link all these resources together, so that I can go seamlessly from a phylogeny in TreeBASE to a locality on a map, and visa versa, of from a phylogeny for a parasite to that of its host, for example.

Time and again I come across extraordinarily frustrating messes. More and more I see why Cory Doctorow wrote Metacrap. According to this essay, the problems with metadata are:

1. People lie
2. People are lazy
3. People are stupid
4. Mission: Impossible -- know thyself
5. Schemas aren't neutral
6. Metrics influence results
7. There's more than one way to describe something

Amen. I know I've moaned about this before (e.g., Damn DiGIR, and AMNH Dspace and Openurl), but it's just amazing what people put into databases.

Co-ordinates

My current favourite is the junk that populates GenBank source records. This is where people provide information about the source of their sequence (e.g., the organism it came from, any voucher specimens, and the geographic locality of the source). All manner of junk ends up here.

You'd think that geographic location was a straightforward thing to record, but no. Consider sequence AY281248. The country field for this record is:

Australia: Gubbata, NSW (GPS: 33 38' 07'', 146  33' 12'')

Spot the problem? Leaving aside the fact that somebody has to parse this and extract the latitude and longitude (hmm, which one is which, can I rely on latitude coming first, ah the second must be longitude because latitude is never > 90°), the co-ordinates are not in Australia.


View Larger Map

Last time I checked, Australia was in the southern hemisphere, and not drifting of the coast of Japan. Now, latitude 33°38' 07''S is in Australia:


View Larger Map

Seems like a small deal to leave off "S" (or a minus sign), but changing hemispheres is a big deal. Then there are strings such as

Nicaragua: Rio San Juan, Near Isla de Diamante 
(ca. 15 km SE El Castillo on Rio San Juan), 10deg56'N 84deg18'W

from DQ502492. Sigh.

Now, you might say that this isn't GenBank's fault, because the country field wasn't supposed to have latitude and longitude information, that is the role of the lat_lon field. This format for this field is defined as:

degrees latitude and longitude in format "d[d.dd] N|S d[dd.dd] W|E"

Fine, but people don't always follow this format. For example, DQ226041 has

/lat_lon="6 28.06'N; 58 37.16'W"

Not hugely different, but the ";" needs to be removed before parsing. What's worse, I can't assume people will follow GenBank guidelines about how to store data in these fields.

Specimen codes

What I'm really after are specimen codes, as these can potentially be linked to digital records served by natural history collections. But, once again all manner of variations end up in GenBank records. For example, specimens in the Field Museum can be referred to as Field Museum of Natural History 167358 (DQ023431) or as FMNH 167358 ( AY324464 ), and there are other variations I've come across as well. Furthermore, FMNH 167358 isn't enough by itself to retrieve a record from the Field Museum, I need to know the address of the DiGIR provider, and whether the specimen is a mammal or some other vertebrate (museum specimen codes are often not unique across the institution). In my opinion the single biggest failure of specimen digitisation efforts is the lack of a globally unique, resolvable identifier. Sure, it's coming, but in the meantime we have chaos.

Tools like GBIF show us what can be done when we aggregate lots of specimen records, but I'd argue the real fun starts when we link resources together, and we can only do this is we have stable, shared identifiers. As an example, Steppan et al. (2003) (doi:10.1111/j.1095-8312.2003.00274.x) published a study of Apomys biogeography. If I get a sequence from this study from GenBank (e.g., AY324464 mentioned above) I have a GenBank record with very few links. There's no PubMed record, for example. If I use an OpenURL resolver (such as the one I wrote for bioGUID) I can retrieve a DOI from the citation Biol. J. Linn. Soc. Lond. 80 (4), 699-715 (2003). This gives me a GUID for the paper, as well as a way to link to the text. The specimen code FMNH 167358 can be used to retrieve details from the Field Museum (once I've parsed the GenBank taxonomy string to discover that Apomys datae is a mammal). This gives me the latitude and longitude of the locality from which the specimen was collected, so I can put it on a map:


View Larger Map

So, I've added information to the GenBank record. But this isn't really the goal. What I want to do is link these elements together. For example, here's a graph showing the link between the publication, the sequence, and the specimen:



Basically, this is the immediate neighbourhood of the sequence AY324464. If I get the neighbourhood of the specimen:



Note that this includes another sequence, DQ023431 (the "tag" refers to the uBio record for Apomys datae -- I treat taxonomic names as tags, but that's another story). I could then navigate to DQ023431, and then onto the publication that refers to that sequence, and so on. Very quickly we get a web of data. This is, of course, the vision of the Semantic Web and related projects, such as Linking Open Data. Wonderful idea, it's just such hard work getting there...

EDIT meeting

Spent the week in Portugal at the EDIT Future Trends of Taxonomy meeting, held at the View from cave, at the beach in front of the Hotel Tivoli Almansor, Carvoeiro. Pretty venue, and an interesting conference (for the sociology, if nothing else).

Ancient rock pools, Algar Seco
Originally uploaded by Roderic Page

What I did find fascinating was the local geology, especially what appear to be ancient rock pools several metres above the existing sea level. These can be seen around Algar Seco. The pools are deep, often with smooth edges ground by rocks, some of which are still lying in the centre.
Looks like the sea level here was once several metres higher. When I have a chance I should follow this up (e.g., doi:10.1016/j.geomorph.2006.04.014).

Transitive reduction

Quick note to self, having stumbled on the Wikipedia page on transitive reduction. Given a graph like this:

the transitive reduction is:

Note that the original graph has an edge a -> d, but this is absent after the reduction because we can get from a to d via b (or c).


What's the point? Well, it occurs to me that a quick way of harvesting information about existing taxonomies (e.g., if we want to assemble an all embracing classification of life to hep navigate a database) is to make use of the titles of taxonomic papers, e.g., the title Platyprotus phyllosoma, gen. nov., sp. nov., from Enderby Land, Antarctica, an unusual munnopsidid without natatory pereopods (Crustacea: Isopoda: Asellota) gives us:

Crustacea -> Isopoda -> Asellota ->Platyprotus -> phyllosoma

From the paper, and or other sources we can get paths such as Asellota -> Munnopsididae -> Platyprotus and Isopoda -> Munnopsididae. Imagine that we have a set of these paths, and want to assemble a classification (for example, we want to grow the Species 2000 classification, which lacks this isopod). Here's the graph:


This clearly gives us information on the classification of the isopod, but it's not a hierarchy. The transitive reduction, however, is:



It would be fun to explore using this technique to mine taxonomic papers and automate the extraction of classifications, as well as names.

Interview

Paulo Nuin recently interviewed me for his Blind.Scientist blog. The interview is part of his SciView series.

Thesis online

One side effect of the trend towards digitising everything is that stuff one forgot about (or, perhaps, would like to forget about) comes back to haunt you. My alma mater, the University of Auckland is digitising theses, and my PhD thesis "Panbiogeography: a cladistic approach" is now online (hdl:2292/1999). Here's the abstract:

This thesis develops a quantitative cladistic approach to panbiogeography. Algorithms for constructing and comparing area cladograms are developed and implemented in a computer program. Examples of the use of this software are described. The principle results of this thesis are: (1) The description of algorithms for implementing Nelson and Platnick's (1981) methods for constructing area cladograms. These algorithms have been incorporated into a computer program. (2) Zandee and Roos' (1987) methods based on "component-compatibility" are shown to be flawed. (3) Recent criticisms of Nelson and Platnick's methods by E. O. Wiley are rebutted. (4) A quantitative reanalysis of Hafner and Nadler's (1988) allozyme data for gophers and their parasitic lice illustrates the utility of information on timing of speciation events in interpreting apparent incongruence between host and parasite cladograms. In addition the thesis contains a survey of some current themes in biogeography, a reply to criticisms of my earlier work on track analysis, and an application of bootstrap and consensus methods to place confidence limits on estimates of cladograms.

1990. Ah, happy days...

Phyloinformatics workshop online

Slides from the recent Phyloinformatics workshop in Edinburgh are now online at the e-Science Institute. In case the e-Science Institute site disappears I've posted the slides on slideshare.

| View | Upload your own

Heiko Schmidt has also posted some photos of the proceedings, demonstrating how distraught the particpants were that I couldn't make it.

GBIF data evaluation

Interesting paper in PLoS ONE (doi:10.1371/journal.pone.0001124) on the quality of data housed in GBIF. The study looked at 630,871 georeferenced legume records in GBIF, and concluded that 84% of these records are valid. As examples of those that aren't, below is a map of legumes placed in the sea (there are no marine legumes).

Although the abstract warns of the dire consequences of data deficencies, the conclusions make for interesting reading:

The GBIF point data are largely correct: 84% passed our conservative criteria. A serious problem is the uneven coverage of both species and areas in these data. It is possible to retrieve large numbers of accurate data points, but without appropriate adjustment these will give a misleading view of biodiversity patterns. Coverage associates negatively with species richness. There is a need to focus on databasing mega-diverse countries and biodiversity hotspots if we are to gain a balanced picture of global biodiversity. A major challenge for GBIF in the immediate future is a political one: to negotiate access to the several substantial biodiversity databases that are not yet publicly and freely available to the global science community. GBIF has taken substantial steps to achieve its goals for primary data provision, but support is needed to encourage more data providers to digitise and supply their records.

Amber spider

Really just a shameless attempt to get one over David Shorthouse, but there has been some buzz about Very High Resolution X-Ray Computed Tomography (VHR-CT) of a fossil of Cenotextricella simon.


The paper describing the work is in Zootaxa (link here). Zootaxa is doing great things for taxonomic publishing, but they really need to get some sort of stable identifier set up. Linking to ZooTaxa articles is not straightforward. If they had DOIs (or even OpenURL access) they wuld make it much easier for people to convert lists of papers that include ZooTaxa publications to lists of resolvable links.

Universal Serial Item Names

Following on from the discussion of BHL and DOIs, I stumbled across some remarkable work by Robert Cameron at SFU. Cameron has developed Universal Serial Item Names (USIN). The approach is spelled out in detail in Towards Universal Serial Item Names (also on Scribd). This lengthy document deals with how to develop user-friendly identifiers for journal articles, books, and other documents. The solution looks less baroque than SICIs, which I've discussed earlier.

There is also a web site (USIN.org), complete with examples and source code. Identifiers for books are straightforward, for instance bibp:ISBN/0-86542-889-1 identifies a certain book:

For journals things are slightly more complicated. However, Cameron simplified things a little in his subsequent paper Scholar-Friendly DOI Suffixes with JACC: Journal Article Citation Convention (also on Scribd).

JACC (Journal Article Citation Convention) is proposed as an alternative to SICI (Serial Item and Contribution Identifier) as a convention for specifying journal articles in DOI (Digital Object Identifier) suffixes. JACC is intended to provide a very simple tool for scholars to easily create Web links to DOIs and to also support interoperability between legacy article citation systems and DOI-based services. The simplicity of JACC in comparison to SICI should be a boon both to the scholar and to the implementor of DOI responders.

USIN and JACC use the minimal number of elements in order to identifier an article, such as journal code (e.g., ISSN or an accepted acronym), volume number, and starting page. Using ISSNs ensures globally unique identifiers for journals, but the scheme can also use acronyms, hence those journals that lack ISSNs could be catered for. The scheme is simple, and in many cases will provide the bare minimum of information necessary to locate an item via an OpenURL resolver. Indeed, one simple way to implement USIN identifiers would be to have a service that takes URIs of the form <journal-code>:<volume>@<page> and resolves them behind the scenes using OpenURL. Hence we get simple identifiers that are resolvable, without the baroque approach of SICIs.

When I get the chance I may add support for something like this to bioGUID.

Taxonomy is dead, long live taxonomy

No, not taxonomy the discipline (although I've given a talk asking this question), but taxonomy.zoology.gla.ac.uk, my long-running web server hosting such venerable software projects as TreeView, NDE, and GeneTree, along with my home page.

A series of power cuts in my building while I was away finally did for my ancient Sun Sparcstation5, running the CERN web server (yes, it's that old). I can remember the thrill (mixed with mild terror) of taking delivery of the Sparcstation and having to manually assemble it (the CD ROM and floppy drives came separately), and the painful introduction to the Unix command line. The joy of getting a web server to run (way back in late 1995), followed by Samba, AppleTalk, and CVS.

For the time being a backup copy of the documents and software hosted on the Sparcstation are being served from a Mac. The only tricky thing was setting up the CVS server that I use for version control for my projects. Yes, I know CVS is also ancient, and that Linus Torvalds will think me a moron, but for now it's what I use. CVS comes with Apple's developer tools, but I wanted to set up remote access. I found the articles by Daniel Côté Setting up a CVS server on Mac OS X and on Mac OSX Hints Enable CVS pserver on 10.2 to be helpful. Basically I initialised a new CVS repository, then copied across the backed repository from a DVD. I then replaced some files in CVSROOT that listed things like the modules in the repository and notifications sent when code is comitted. Getting the pserver up and running required some work. I created a file called cvspserver inside /etc/xinetd.d/, with the following contents.

service cvspserver
{
        disable = no
        socket_type     = stream
        wait            = no
        user            = root
        server          = /usr/bin/cvs
        server_args     = -f --allow-root=/usr/local/CVS pserver
        groups          = yes
        flags           = REUSE
}

Then I started the service:

sudo /sbin/service cvspserver start

So far, so good, but I couldn't log in to CVS. Discovered that this is because Mac OS X uses ShadowHash authentication_authority. Hence, on a Mac CVS won't use the system user names and passwords (probably a good thing). Therefore, we uncomment the line

# Set this to "no" if pserver shouldn't check system users/passwords
SystemAuth=no

in the file CVSROOT/config, then create a file CVSROOT/passwd. This file contains the username, hash password, and the actual Mac OS X username (nicely explained in Daniel Côté's article). To generate a hash password, do this:

darwin: openssl passwd
Password: 123
Verifying - Password: 123
yrp85EUNQl01E

At last it all seems to work, and I can get back to coding. This is about as geeky as this blog gets, but if you want a real geek overload, spend some time listening to this talk by Linus Torvalds.

BHL and DOis

In a series of emails Chris Freeland, David Shorthouse, and I have been discussing DOIs in the context of the Biodiversity Heritage Library (BHL). I thought it worthwhile to capture some thoughts here.
In an email Chris wrote:

Sure, DOIs have been around for a while, but how many nomenclators or species databases record them? Few, from what I've seen - instead they record citations in traditional text form. I'm trying to find the middle ground between guys like the two of you, who want machine-readable lit (RDF), and most everyone else I talk with, including regular users of Botanicus & BHL, who want human-readable lit (PDF). I'm not overstating - it really does break down into these 2 camps (for now), with much more weight over on the PDF side (again, for now).

I think the perception that there are two "camps" is unfortunate. I guess for a working taxonomist, it would be great if for a given taxonomic name there was a way to see the original publication of the name, even if it is simply a bitmap image (such as a JPEG). Hence, a database that links names to images of text would be a useful resource. If this is what BHL is aiming for, then I agree, DOIs may seem to be of little use, apart from being one way to address the issue of persistent identifiers.

But it seems to me that there are lots of tasks for which DOIs (or more precisely, the infrastructure underlying them) can help. For example, given a bibliographic citation such as

Fiers, F. and T. M. Iliffe (2000) Nitocrellopsis texana n. sp. from central TX (U.S.A.) and N. ahaggarensis n. sp. from the central Algerian Sahara (Copepoda, Harpacticoida). Hydrobiologia, 418:81-97.

how do I find a digital version of this article? Given this citation

Fiers, F. & T. M. Iliffe (2000). Hydrobiologia, 418:81.

how do I decide that this is the same article? If I want to see whether somebody has cited this paper (and perhaps changed the name of the copepod) how do I do that? If I want follow up the references in this paper, how do I do that?

These are the kinds of thing that DOIs address. This article has the DOI doi:10.1023/A:1003892200897. This gives me a globally unique identifier for the article. The DOI foundation provides a resolver whereby I can go to a site that will provide me with access (albeit possibly for a fee) to the article. CrossRef provides an OpenURL service whereby I can

• Retrieve metadata about the article given the DOI


• Given metadata I can search for a DOI

To an end user much of this is irrelevant, but to people building the links between taxonomic names and taxonomic literature, these are pressing issues. Previously I've given some examples before where taxonomic databases such as Cataloggue of Life and ITIS store only text citations, not identifiers (such as DOIs or Handles). As a result, the user has to search for each paper "by hand". Surely in an ideal world there would be a link to the publication? If so, how do we get there? How do IPNI, Index Fungorum, ITIS, Sp2000, ZooBank, and so on link their names and references to digitised content? This is where a CrossRef-style infrastructure comes in.

Publishers "get this". Given the nature of the web where users expect to be able follow links, CrossRef deals with the issue of converting the literature cited section of a paper into a set of clickable links. Don't we want the same thing for our databases of taxonomic names? And, don't we want this for our taxonomic literature?

It is worth noting that the perception that DOIs only cover modern literature is erroneous. For example, here's the description of Megalania prisca Owen (doi:10.1098/rstl.1859.0002), which was published in 1859. The Royal Society of London has DOIs for articles published in the 18th century.

If the Royal Society can do this, why can't BHL?

Phyloinformatics workshop - primal scream

Argh!!! The phyloinformatics workshop at Edinburgh's eScience Centre is underway (program of talks available here as an iCalendar file), and I'm stranded in Germany for personal reasons I won't bore readers with. The best and brightest gather less than an hour from my home town to talk about one of my favourite subjects, and I can't be there. Talk about frustration!

How can they they possibly proceed without yours truly to interject "it sucks" at regular intervals? What, things are going just fine? Next, you'll be suggesting that Systematic Biology can function without me as editor … wait, what's that you say? Jack's running the show without a hitch … gack, I'm redundant.

Getting into Nature ... sort of

The kind people at Nature have taken pity on my rapidly fading research career, and have highlighted my note "Towards a Taxonomically Intelligent Phylogenetic Database" in Nature Precedings (doi:10.1038/npre.2007.1028.1) on the Nature web site. Frankly this is probably the only way I'll be getting into Nature...

Pygmybrowse GBIF classification

Here is a live demo of Pygmybrowse using the Catalogue of Life classification of animals provided by GBIF. It's embedded in this post in an <iframe> tag, so you can play with it. Just click on a node.

Taxa in bold have ten or more children, the numbers of children are displayed in parentheses "()". Each subtree is fetched on the fly from GBIF.

Pygmybrowse revisited

As yet another example of avoiding what I should really be doing, a quick note about a reworked version of PygmyBrowse (see earlier posts here and here). Last September I put together a working demo written in PHP. I've now rewritten it entirely in Javascript, apart from PHP script that returns information about a node in a classification. For example, this link returns details about the Animalia in ITIS.

You can view the new version live. Going "view source" in your browser will show you the code. It's mostly a matter of Javacsript and CSS, with some AJAX thrown in (based on the article Dynamic HTML and XML: the XMLHttpRequest object on Apple's ADC web site).

One advantage of making it entirely in Javascript is that it can be easily integrated into web sites that don't use PHP. As an example, David Shorthouse has inserted a version into the species pages in The Neartic Spider database (for example, visit the page for Agelena labyrinthica and click on the little "Browse tree" link).

Frog deja vu

While using iSpecies to explore some names (e.g., Sooglossus sechellensis in the Frost et al. amphibian tree mentioned in the last post, I stumbled across two papers that both described a new genus of frog for the same two taxa in the Seychelles. The papers (doi:10.1111/j.1095-8312.2007.00800.x and www.connotea.org/uri/6567cfd7531a77588ee62d78e7b4359b) were published within a couple of months of each other.

Was about to blog this, when I discovered that Christopher Taylor had beaten me to it with his post Sooglossidae: Deja vu all over again. Amongst the commentary on this post is a note by Darren Naish (now here) pointing to an interesting article by Jerald D. Harris entitled ‘Published Works’ in the electronic age: recommended amendments to Articles 8 and 9 of the Code, in which he states:

I propose to the Commission that, under Article 78.3 (‘Amendments to the Code’), Articles 8 and 9 of the current Code require both pro- and retroactive (to the effective date of the Fourth Edition, 1 January 2000) modification to accommodate the following issue: documents published electronically with DOI numbers and that are followed by hard-copy printing and distribution be exempt from Article 9.8 and be recognized as valid, citable sources of zoological taxonomic information and that their electronic publication dates be considered definitive.

It's an interesting read.

Visualising very big trees Part VI

I've tidied up the big phylogeny viewer mentioned earlier, and added a simple web form for anybody interested to upload a NEXUS or Newick tree and have a play.

Examples:

• Ants from TreeBASE


• trichodectid lice from TreeBASE


• Bats from TreeBASE


• Frost et al amphibian tree

To create your own tree viewer, simply go to http://linnaeus.zoology.gla.ac.uk/~rpage/bigtrees/tv2/ and upload a tree. After some debugging code and images scroll past, a link to the widget appears at the bottom of the page. I'll tidy this all up when I get the chance, but for now it's good enough to play with.

processing PhylOData (pPOD)

The first pPod workshop happened last month at NESCent, and some of the presentations are online on the pPod Wiki. Although I'm a "consultant" I couldn't be there, which is a pity because it looks to have been an interesting meeting. When pPod was first announced I blogged some of my own thoughts on phylogenetics databases. The first meeting had lots of interesting stuff on workflows and data integration, as well as outlining the problems faced by large-scale systematics. Some relevant links (partly here to as a reminder to myself to explore these further):

• Orchestra a collaborative data sharing system
• MIAPA Minimal Information About a Phylogenetic Analysis (see also doi:10.1089/omi.2006.10.231)
• BioSQL persistent storage of sequences and features

Mesquite does Google Earth files

The latest version of the David and Wayne Maddison's Cartographer module for their program Mesquite can export KML files for Google Earth. They graciously acknowledge my crude efforts in this direction, and Bill Piel's work -- he really started this whole thing rolling.

So, those of you inspired to try your hand at Google Earth trees, and who were frustrated by the lack of tools should grab a copy of Mesquite and take it for a spin.

Parallels

Quick note to say how much fun it is to use Parallels Desktop. It's a great advantage to have Windows XP and Fedora Core 7 running on my Mac. As much as I dislike Internet Explorer, it caught some bugs in my code. It's always useful to try different environments when debugging code, either stand alone or for the Web.

Nature Precedings

Nature precedings is pre-publication server launched by Nature a few months ago. To quote from the website:

Nature Precedings is a place for researchers to share pre-publication research, unpublished manuscripts, presentations, posters, white papers, technical papers, supplementary findings, and other scientific documents. Submissions are screened by our professional curation team for relevance and quality, but are not subjected to peer review. We welcome high-quality contributions from biology, medicine (except clinical trials), chemistry and the earth sciences.

Unable to resist, I've uploaded three manuscripts previously languishing as "Technical Reports" on my old server. The three I uploaded now have bright shiny DOIs, which may take a little while to register with CrossRef. The manuscripts are:

Treemap Versus BPA (Again): A Response to Dowling doi:10.1038/npre.2007.1030.1 (a response to a critique of my ancient TreeMap program).

On The Dangers Of Aligning RNA Sequences Using "Conserved" Motifs doi:10.1038/npre.2007.1029.1 (a short note on Hickson et al.'s (2000) use of conserved motifs to evaulate RNA alignment).

Towards a Taxonomically Intelligent Phylogenetic Database doi:10.1038/npre.2007.1028.1 (a paper written for DBiBD 2005, basically a rewrite of a grant proposal).

All three are under the evolution and ecology subject heading. Visitors to Nature precedings can comment on papers, and vote for which ones they like. The fact that I've uploaded some manuscripts probably says nothing good about me, but I'll be checking every so often to see if anybody has anything to say...

Matching names in phylogeny data files

In an earlier post I described the TBMap database (doi:10.1186/1471-2105-8-158), which contains a mapping of TreeBASE taxon names onto names in other databases. While this is one step towards making it easier to query TreeBASE, what I'd really like is to link the data in TreeBASE to sources such as GenBank and specimen databases. Part of the challenge of doing this (and also doing it more generally, such as taking a NEXUS file from the web and using that) is that the names people use in a NEXUS data file are often not the actual taxonomic names. So, if I take a table from a paper that lists GenBank accession numbers, voucher specimens, etc., I'm left with the problem of matching two sets of names -- those in the data file to those in the table.

For example, this is a TreeBASE taxon Apomys_sp._B_145699. Using a script I grabbed the sequences in this study and constructed a table listing the name and specimen voucher for each sequence. The name corresponding to the TreeBASE taxon is Apomys "sibuyan b" FMNH 145699. Clearly a similar string, but not the same.

The approach I've taken is to compare strings using the longest common subsequence algorithm. Below are the two strings, with their longest common subsequence highlighted in green.


Apomys_sp._B_145699

Apomys "sibuyan b" FMNH 145699

The length of this subsequence is used to compute a measure of distance between the two strings. If len1 is the length of the first string, len2 is the length of the second string, and lcs is the length of the longest common subsequence, then

d = (len1 + len2) - 2 × lcs

We can normalise this by dividing by len1 + len2, so that d ranges from 0 (identical) to 1.0 (no similarity).

So, now we have a measure of how similar the strings are, I still need to find the set of matchings between file and table names. This can be modelled an example of a maximum weight bipartite matching problem. Given a bipartite graph, we want to find the matching with the highest weight. A "matching" is where each node is connected to just one other node. For example, given this graph:


a maximum weight matching is:



In this example, four pairs of nodes are matched, one is "orphaned". Applying this to the data matching problem, I take a list of names form the NEXUS file, and a list of names from the paper (or supplementary data file, etc.) and compute a maximum weight matching. Because I'm looking for the maximum weighted matching I actually want similarity of names, hence I subtract the normalised d from 1.0.

So, the algorithm consists of taking the two lists of names (taxa from dataset and names from a table), computing the distance between all pairs of names, then obtain the maximum weight bipartite matching. Because for large sets of names the n × m the bipartite graph becomes huge, and because in practice most matches are poor, for each node in the graph I only draw the edges corresponding to the five most similar pairs of strings.

RAxML BlackBox

Alexis Stamatakis and Jacques Rougemont have released RAxML BlackBox, a prototype Web-Server for RAxML which is attached to a 200 CPU-cluster located at the Vital-IT unit of the Swiss Institute of Bioinformatics. You can upload your data and the cluster will mul it over for up to 24 hours, so typically you can analyse alignments up to 1,000 to 1,500 sequences at present. The software itself can handle bigger data sets (see the RAxML page at CIPRES).

Alexis has also doe some work on phylogeny visualisation, including using treemaps. See (doi:10.1007/11573067_29, PDF here).

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.

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.

Bird supertree project - "Open Source" phylogenetics

Black Browed Albatross
Originally uploaded by QuestingBeast

Today is the day Katie Davis and I are launching the Bird Supertree Project. Partly an effort to distribute the task of building the tree, partly an experiment in "open source phylogenetics", we're curious (if not anxious) to see how this works out. We encourage anybody who is interested in constructing big trees to visit the site, grab the data and have a play. You can upload your results (and see who is the best tree builder), and view the trees using one of the methods for viewing big trees that I mentioned earlier. I'm frantically trying to improve this viewer, so the more trees we get the greater the incentive for me to improve it.

Expand-Ahead: A Space-Filling Strategy for Browsing Trees

For the "to do" list, expand-ahead browsing looks like a useful approach to build upon PygmyBrowse (see my live demo). The approach is described in "Expand-Ahead: A Space-Filling Strategy for Browsing Trees" by McGuffin et al. (doi:10.1109/INFOVIS.2004.21, PDF also here).

There is a video on Ravin Balakrishnan's site, which is an AVI file that I haven't bee able to coerce my Mac into playing, hence I've posted it on YouTube.

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

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.

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.

Viewing very large trees

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

I hate computers

The PC hosting linnaeus.zoology.gla.ac.uk and darwin.zoology.gla.ac.uk has died, and this spells the end of my interest in (a) using generic PC hardware and (b) running Linux. The former keeps breaking down, the later is just harder than it needs to be (much as I like the idea). From now on, it's Macs only. No more geeky knapsacks for me.

Because of this crash a lot of my experimental web sites are offline. I'm slowly putting some back up, driven mainly by what my current interests are, what people have asked for, or things linked to by my various blogs. So far, these pages are back online:

• TreeView X
• LSID tester
• TreeBASE name mapping
• iSpecies

A lot of the other stuff will have to wait.

I hate computers...

LSID wars

Well, the LSID discussion has just exploded in the last few weeks. I touched on this in my earlier post Rethinking LSIDs versus HTTP URI, but since then the TDWG discussion has become more vigourous (albeit mainly focussed on technical issues, although I suspect that these are symptoms of a larger problem), while public-semweb-lifesci@w3.org list for July has mushroomed into a near slugfest of discussion about URIs, LSIDs, OWL, the goals of the Semantic Web, etc. There are also blog posts, such as Benjamin Good's The main problem with LSIDs, Mark Wilkinson's numerous posts on his blog, and Pierre Lindebaum's commentary.

I have no comment to make on this, I'm merely bookmarking them for when I find the time to wade through all this...

Phyloinformatics Workshop in Edinburgh October 22-24 2007

This October 22-24 there is a phyloinformatics workshop at the e-Science Institute in Edinburgh, Scotland, hosted in conjunction with the Isaac Newton Institute for Mathematical Sciences's Phylogenetics Programme.

As phylogenetics scales up to grapple with the tree of life, new informatics challenges have emerged. Some are essentially algorithmic - the underlying problem of inferring phylogeny is computationally very hard. Large trees not only pose computational problems, but can be hard to visualise and navigate efficiently. Methodological issues abound, such as what is the most efficient way to mine large databases for phylogenetic analysis, and is the "tree of life" the appropriate metaphor given evidence for extensive lateral gene transfer and hybridisation between different branches of the tree. Phylogenies themselves are intrinsically interesting, but their real utility to biologists comes when they are integrated with other data from genomics, geography, stratigraphy, ecology, and development. This poses informatics challenges, ranging from the more general problem of integrating diverse sources of biological data, to how best to store and query phylogenies. Can we express phylogenetic queries using existing database langauges, or is it time for a phylogenetic query language? All these topics can be gathered together under the heading "phyloinformatics". This workshop brings together researchers with backgrounds in biology, computer science, databasing, and mathematics. The aim is to survey the state of the art, present new results, and explore more closely the connections between these topics. The 3 day workshop will consist of 10 talks from invited experts (45 minutes each), plus 3 group discussion sessions (45 mins - 1 hour each). A poster session will be held in the middle of the meeting for investigators who wish to present their results, and there be also be time set aside for additional discussion and interaction.

The invited speakers are:

• Prof. Mike Sanderson (USA)
  http://ginger.ucdavis.edu/sanderson.html
• Professor Mark Blaxter
  http://www.nematodes.org/
• Professor Todd Vision
  http://www.bio.unc.edu/Faculty/Vision/
• Dr. William Piel (USA)
  http://www.acsu.buffalo.edu/~wpiel/
• Prof. David Hibbett (USA)
  http://mor.clarku.edu/
• Dr. Alexis Stamatakis (CH)
  http://diwww.epfl.ch/~stamatak/
• Prof. Olaf Bininda-Emonds (DE)
  http://www.personal.uni-jena.de/~b6biol2/
• Prof. Rod Page (UK)
  http://taxonomy.zoology.gla.ac.uk/rod/rod.html
• Dr. Charles Semple (NZ)
  http://www.math.canterbury.ac.nz/~cas83/
• Prof. Stephen Willson (USA)
  http://www.public.iastate.edu/~swillson/

For more details visit the web site.