An Example of Why We Need the PhyloCode

I just ran Radish on Zea mays (maize, a.k.a. corn). Look what the combined taxonomies from uBio look like:

What a mess! Keep in mind that the multiplicity of paths is not due to differing phylogenies (they all seem to agree on that), but to differing nomenclature. Even if uBio were to add some of the more obvious synonymies (e.g., Embryophyta and "Embryophytes"), it'd still be pretty wild.

Eventually I plan to have Radish work with automatically-generated taxonomies, made by placing PhyloCode names (from RegNum) onto TreeBase phylogenies using Names on Nodes algorithms, but until then I guess this is the best option.

And Zea mays is just a particularly egregious example. In contrast, here's a nice, neat "radish" for Scarabaeus sacer:

Apart from the one errant use of Animalia, pretty nice!

Radish: Pulling Up Taxonomic Hierarchies From Leaf to Root

I've just released a small open-source Java library called Radish. It contains tools for interfacing with uBio (and hopefully other services in the future), with the purpose of looking up a taxon's hierarchy. It does this by synthesizing multiple taxonomies into a single graph. Here, for example, is the graph produced by looking up Homo sapiens Linnaeus 1758 (click the image to enlarge):

This is a synthesis of several taxonomies. Some have more ranks than others, but they all converge on a single chain, with the exception of the taxa above the "phylum level", where at least two of them use different schemes. (Although it may be tempting to synonymize Biota and "Cellular life", or Animalia and Metazoa, these are not objective synonymies, and arguably the former is a bad idea anyway.) Ideally the library would be able to figure out that "Cellular life" includes Biota (if the latter is a crown clade), and that Animalia either includes or is a synonym of Metazoa, but it can only work with the data it's given.


Why the name "Radish"? From the project's wiki:

The English word "radish" is derived from Latin "radicem" (nominative: "radix"), meaning "root". (This is also where the word "radical" comes from.) The idea of the Radish library is that by "grabbing a leaf" (i.e., selecting a smaller taxon), you can "pull up the root" (i.e., extract that taxon's hierarchy of supertaxa, up to the root of all life).

Radish is part of a larger project I am working on ... I should have more to say about that in the near future....

Two "Names on Nodes"-Related Launches

I'm still a clear way away from launching the beta application, but I've just made a couple of launches related to my long-time work-in-progress, Names on Nodes.

First up, and probably of more interest to most people, I've begun the documentation for the MathML definitions used by Names on Nodes. The document includes general reviews of relevant mathematical and biological concepts, a quick review of MathML and the technologies it's based on, some comments on correlating mathematical and biological concepts, and definitions for all entities (including operations) used by Names on Nodes. Note that this covers a lot of the same ground as in my 2007 paper, with a few minor changes in the symbols and terminology (e.g., I now call the ancestor of a clade a "cladogen" rather than a "cladogenetic set").

Secondly, I've made the project open-source, by moving it to Google Code. If you are a developer interested in checking this out, go here. It's incomplete, so I don't know if anyone will have any real interest in looking at it yet. (Honestly, I mostly posted so that, on the off chance that I unexpectedly kick the bucket, my magnum opus won't be lost forever.)

This information is also on the new Names on Nodes home page.

Refactoring "Names on Nodes" Entities, Part II

As I discussed previously, the Names on Nodes project had reached a point where the schema just wasn't working out. I went through a list of what was wrong with it: confusing nomenclature, various unnecessary classes, unnecessary references, and major practical problems with looking up contextual relations.

Another big problem was the home-brewed keyword search system I had going. Synchronizing the keyword lists was becoming problematic, and I realized there are already perfectly good (better, even) tools out there such as Hibernate Search. That's a chief rule of programming: don't reinvent something that people smarter than you, with more time on their hands, have already invented.

After a clear, honest look at the contextual relations, I came to a realization: they should be in the client, not the back end. No need to bog down the server with computing definition applications when it can be done in the client. That simplified things a great deal.

Another thing I didn't really need was categories. They were basically an ad hoc form of class inheritance, e.g., a species name is a nomen, a nomenclatural code is a publication, etc. For a little while I considered implementing this as a class hierarchy, as I had in earlier versions. But, really, this is irrelevant data—Names on Nodes doesn't really need to know what category an identifier falls in.

Finally, I had another problem in the way datasets and taxon identifiers (=signifiers) used qualified names. Each one was supposed to have a unique qualified name. While I was able to guarantee uniqueness within datasets and within taxon identifiers, I wasn't able to guarantee that qualified names would be unique between datasets and taxon identifiers.

So, here's the new version (click to magnify):
Again, white arrows indicate "is-a" relationships ("inheritance")—so a PhyloDefinition is a type of Definition, a Dataset is a type of Qualified object, etc. And black diamonds indicate "has-a" relationships ("composition")—so a TaxonIdentifier has one (and only one) Taxon, an Equation has at least two TaxonIdentifier objects, etc. (I've left out a few non-core classes, like BioFile and UserAccount.)

Brief discussions of each class:

Authority.—An authority can be a publication, a person, a bioinformatics file, a database, a specimen catalogue, etc. Each authority has a canonical name (e.g., "Yale Peabody Museum: Vertebrate Paleontology Collection") and an optional abbreviation (e.g., "YPM-VP").

AuthorityIdentifer.—One or more identifiers may be used to indicate an authority, each one associated with a unique URI. Examples:

• <urn:isbn:0853010064> (The International Code of Zoological Nomenclature, 4th Edition)
• <http://iczn.org/iczn> (Another way of referring to the ICZN.)
• <mailto:keesey@gmail.com> (myself)
• <http://peabody.yale.edu/collections/vp> (Yale Peabody Museum: Vertebrate Paleontology Collection)
• <urn:sha1:bc0ccc8a379edc44cf91b013d2da6238d4258a56> (a bioinformatics file, indicated by its SHA-1 hash key)

Qualified.—This new abstract class makes it possible for qualified names to be unique across all classes that use them. Each refers to an authority identifier and contains a local name, which is unique to that identifier. When combined, the identifier's URI and the local name form a qualified name, e.g., <urn:isbn:0853010064::Homo+sapiens> or <http://peabody.yale.edu/collections/vp::1450>.

TaxonIdentifier & Taxon.—Formerly called "signifiers", taxon identifiers are qualified objects that each refer to a taxon. Taxon identifiers may be scientific names, vernacular names, specimen identifiers, character state descriptions, etc. As with authorities, each taxon may have more than one identifier referring to it. For example, the following qualified names all refer to the same species: <urn:isbn:0853010064::Abeillia+abeillei>, <http://iucnredlist.org::species:142883>, and <http://iucnredlist.org::common_name:Eng:Emerald-chinned+Hummingbird>.

Label.—Authorities, datasets, and taxon identifiers are all labelled entities, possessing one label object. Each label has a name, an optional abbreviation, and a flag telling whether it should be italicized. Labels are merely cosmetic, and need not be unique. They are used as the targets of searches, using Hibernate Search.

Definition.—Each definition has one taxon identifier, and only one definition pertains to that taxon identifier. How do I accommodate differing definitions, then? I use a concept from the PhyloCode: conversion. Consider the name "Aves". Under the ICZN, it refers to a suprafamilial ranked taxon with no type. According to Sereno's TaxonSearch, it refers to a node-based clade including Archaeopteryx. According to Gauthier and de Queiroz (2001), it refers to a crown group. But instead of having multiples definitions for the same identifier, I consider each definition to define a different identifier, each indicating a (potentially) different taxon: <urn:isbn:0853010064::Aves>, <http://www.taxonsearch.org/Archive/stem-archosauria-1.0.php::Aves>, and <urn:bici:0912532572(200112)%3C7:FDFDCD%3E2.0.TX;2-H::Aves>, respectively. In cases of conversion, the definition also indicates the original identifier.

PhyloDefinition & RankDefinition.—These have not changed much, except that they now refer directly to their specifers and types, respectively. No more useless "Anchor" class.

Dataset.—Instead of storing a bunch of relations of unspecified type, each type of relation falls within its own set. I've also added optional ratios for converting weights in phylogenetic networks to generations and/or years.

Equation.—I almost called this "Synonymy". This is a new type of relation, which asserts that two or more identifiers refer to the same taxon.

Heredity & Inclusion.—Heredity was previously called "Parentage". The new nomenclature better reflects its real meaning, since it models ancestor-descendant relationships, not necessarily parent-child. These two classes are little changed, except that now they don't both descend from a useless Relation class, so their nomenclature can be clearer (predecessor and superset used to be "a"; successor and subset used to be "b").


This schema is much cleaner, and will make for a more efficient server-side. I've already implemented the entities, removed deprecated code, and updated the relevant code. After some hiccups with a Hibernate upgrade, unit tests are working again. The back-end should be complete fairly soon (pending some ideas about user accounts), and then it will be time to look at some massive refactorings for the front end!

Sets for ActionScript

It's been a busy couple of months!

One of the things keeping me busy is, of course, Names on Nodes, the web application I am developing that will automate phylogenetic nomenclature. As part of that project, I have developed a mathematics package that I would eventually like to release as its own package. One class, however, is so useful that I have decided to jump the gun and offer it on its own.

We (ActionScript programmers) all know how useful the Array class is. It can be used to store a sequence of anything, so it can be repurposed as a list, a vector, an edge—all manner of collections.

Well, not all manner of collections. Just ordered collections that allow duplicate elements. What if you want a set: an unordered collection with no duplicates? I find I need sets all the time, but I have to use arrays. And arrays are not optimal for looking up an element's membership, or preventing duplication. As lists they're great, but as sets they suck.

For a while I used a class I'd made called ArraySet that wrapped an array, but this was only an improvement in API, not in performance. Then I took a cue from Java and created: HashSet.

Download HashSet.as

The HashSet class wraps a Dictionary object, which it uses as a hash table. If an element belongs to the set, then that element is a self-referential key in the dictionary. If it doesn't, then there is no such key in the dictionary. And HashSet extends Proxy, so you can use bracket notation for many operations,. You can also use for..in and for each..in loops.

Here's a quick example:

// Create and populate the set.
var s:HashSet = HashSet.fromObject([1, 2, 3]);

trace(s.size); // 3
trace(s[1]); // 1
trace(s[2]); // 2
trace(s[0]); // undefined
trace(s.has(1)) // true

// Trace all elements of the set.
for each (var i:int in s)
{
   trace(i);
}
// Trace all elements of the set (different method).
for (var x:* in s)
{
   trace(x);
}

trace(s); // {1, 2, 3}
s.add(1);
trace(s); // {1, 2, 3}
s.add(4);
trace(s); // {1, 2, 3, 4}
s.remove(1);
trace(s); // {2, 3, 4}
delete s[2];
trace(s); // {3, 4}
s[3] = undefined;
trace(s); // {4}

...and so on. Full documentation is in the class itself, so you can figure out the details for yourself. I will mention that HashSet also has a number of functions in common with Array (every, filter, forEach, map, some) and others that are unique to sets (get empty, diff, intersect, prSubsetOf, subsetOf, union). It also has a few functions that Array really ought to have (clone, equals, remove).

Download it and try it! The full version is integrated into the mathematics package that I'm still tweaking, but this is too useful to keep to myself any longer. At least, I think so—let me know what you think.

Names on NEXUS: Under the Hood

I nearly have the basic data model and data processing functions pinned down for Names on NEXUS. Once again, that's my project, hinted at in a paper of mine (Keesey 2007), to relate the data in NEXUS files (Maddison et al. 1997) to definitions of names as governed by the PhyloCode.

I've had to learn some new technologies and code packages to accomplish this. Here's a rundown of some key ones:

BioJava
This is the most recent addition. Originally I had built my own library in ActionScript 3.0 to parse NEXUS files. But it had some limitations. NEXUS is a rather old format (as bioinformatics formats go), and different applications produce somewhat different versions. So rather than use my own ad hoc library, I decided I should get an open source one.

There aren't any in ActionScript, of course, but there are some in Java. This meant I had to switch NEXUS parsing from the front end to the back end, but in some ways that's better. It means I can stored parsed data in the database instead of having client application parse NEXUS data every time. In fact, it means that the client never has to actually see raw NEXUS data—it can just fetch the pre-parsed data.

I first looked into using the NEXUS-parsing code in Mesquite, an open-source phylogenetic analysis program. But it's not set up for simply using the parsing engine on its own—the parser is tied into a whole file-browsing package. Then I found BioJava, which had exactly what I needed. Just looka this package!

Unfortunately there are still some problems with opening certain NEXUS files. I downloaded some samples from TreeBASE and they flagged errors in the TREES section. The reason, as I found after hours of searching and considering whether it might be better just to write my own parser after all, turns out to be an extra comma in the TRANSLATE section. Still not exactly sure how I'm going to solve that one. But it works when I remove the comma!

Hibernate
Remember how I wrote a post a while ago about building classes that map from the Java back-end to the database? Turns out that was all unnecessary. Hibernate is a persistence layer that provides pretty seamless integration between Java and a database (in this case, a PostgreSQL database). Augmented by Hibernate Annotations and Hibernate Validator, it makes it fairly easy to set up and use a complex, well-organized database.

Well, okay, there's a bit of a learning curve first, but it's totally worth it. Incidentally, the book I used to learn it has what is possibly the best title ever.

Flex Data Management Services
Basically, Hibernate is to Java and databases as mx.data is to Flex and Java. It provides a persistence layer so that I don't have to keep track of whether or not I need to request certain data from the Java back-end. I just create DataService objects, tie them to Assembler classes on the back end, and it's all taken care of.

FlexUnit and JUnit
I've already extolled the virtues of unit testing. These wonderful (and, yes, comically-named) packages (huh huh) make it possible. I haven't built enough unit tests, really, but the few I have have been enormously useful in hunting down peculiar errors. And aside from that, since Eclipse can run JUnit tests natively, I can even use them to perform certain important tasks, such as setting up the database from annotated classes via Hibernate.

So What's Left For Me To Do?
Plenty. Although these premade packages help out enormously, I've still had to build an entire mathematics library, a MathML parser, and some tools for handling URIs. I've still got tons of work left to do on the user interface. (Event bubbling is helping a lot with that, by the way.) And, even when stuff is already built, just hooking up one pipe to another pipe can be more complicated than it seems.

Here's a rough list of what's left:

• Finalize the servlet for uploading and parsing NEXUS data. (I'm very close on this one.)
• Finish the required behind-the-scenes "search" features. Some of these might be a bit involved, like the ones that suggest possible links between NEXUS taxa and species or specimens or between NEXUS character states and apomorphies.
• Overhaul the way Names on NEXUS entities (particularly specifiers) are referenced in MathML.
• Finish the user interface. So far I just have a few forms. I still have to do tree visualization, stylesheets, high-level navigation, transitions, etc.
• Constrain access to certain functionality. Names on NEXUS is going to be a pretty open, collaborative tool, but I need to set a few boundaries. (E.g., I can't have any old person delete data.)
• Make sure the server's all optimized, with a static, JNDI-named Hibernate factory, etc.

And here are some things that aren't, strictly speaking, essential, but would be awfully nice:

• Create a servlet to provide permanent links for Names on NEXUS entities.
• Create unit tests for all relevant classes.
• Add JavaDoc and ASDoc comments to all code.

Part of me is also thinking about renaming the project. I mean, it's a good name for what it does right now, but what if I start to bring formats other than NEXUS into the fold? (Not that there are many, but....) Well, I'll probably cross that bridge when I come to it.

My goal is to get an alpha version online sometime this Spring and go open source with it by the Fall. We'll see....

March of Man: Image Feed

There is now an RSS feed that will show all the latest updates to the March of Man gallery. Point your blog-reading software to:

http://marchofman.org:8080/marchofman/imagefeed/

This was surprisingly easy to develop, thanks to the ROME library for Java. (I had a few problems deploying it, but that was my fault.)

The Wonderful Process of Refactoring

In many ways, programming is as much an art as a science. Good code is like good writing: crisp, clear, streamlined, and well-structured. But it's not always possible to foresee the best structure. When working on a project, you just do what seems best at the time. Eventually you'll finish it and work out the bugs, but the underlying code may not be elegant. There may be duplicated code, unclear functionality, unoptimized sections, and sections that do too much with sections that do too little. When you come back to the code to add or refine features, you often face a major headache.

This is why many developers use a general process called refactoring. Refactoring means that you change the design of the code without changing the functionality. An analogy would be rewriting a news article so that it reads better without changing what the article is actually about.

Ensuring that the functionality remains the same is not always easy. It involves frequent testing and retesting. Changing one section might affect another section, so the retesting has to be thorough. Testing a particular section during development is called unit testing.

Sometimes it's worth the extra time to create a program that actually does the testing for you. During heavy refactoring, this can save oodles of time. If you make changes, then you can just run a test that takes a few seconds, quickly showing whether you broke anything (and generally showing exactly what you broke).

I went through this process recently while working on March of Man.

The Setup

Typically a rich Internet application (RIA) has three tiers. The client-side application is something you view in a browser (for example, this website). The database is an application on the server that stores data. The server-side application facilitates communication between the database (and potentially other server-side information) and the client-side. To sum up:

user ↔ client-side app ↔ server-side app ↔ database

In case you were curious, for March of Man, the client-side application is an interactive Flash movie made with Flex Builder, the server-side application uses Java running on JBoss, and the database is PostgreSQL.

All this communication between tiers can get a bit complicated. Fortunately, Adobe provides an excellent tool called LiveCycle Data Services (LCDS) for communicating between the client- and server-side applications. What exactly does it do? Well, March of Man deals with certain types of data: user accounts, images, hominin taxa, location/time ranges, etc. In programming, these types are referred to as classes, and classes are instantiated (i.e., realized) as objects. Specifically, these ones would be considered value objects. So, for example, there is a class called Account that specifies certain types of data, like email address, personal name, password, etc. An instance of Account (i.e., an Account object) might represent a particular person. For the client-side, the Account class is written in ActionScript. For the server-side, it's written in Java. What LiveCycle does is take care of all of the translation: when I send an ActionScript Account object to the server, it is automatically recreated as a Java Account object, and vice versa when the server reports to the client.

As an example, when you log in, the client collects your email address and password, and sends them (encrypted) to the server, specifying a login method. That method looks up the information for the specified account, packages it as an Account object, and sends it back to the client. Voilà, you are logged in.

Unfortunately, there isn't a similarly easy tool for translating from the server-side application to the database, where data is stored in tables as rows and columns. The only way to interface is using SQL, a common language used for database queries. Java provides some ways to facilitate this (the java.sql package of classes), but it can't do everything.

So I created a package of classes called org.marchofman.mappers to map the information from Java to PostgreSQL and back. Each mapper class corresponds to a type of value object, e.g. AccountMapper handles Account objects, ImageMapper handles Image objects, etc. They all have certain functionality in common, such as what are called the "CRUD" commands: create, retrieve, update, and delete. When you register, the Java service uses the AccountMapper.create method. When you log in, it uses AccountMapper.retrieve. When you change your information, it uses AccountMapper.update. And, should you ever decide you don't want an account any more (heavens forfend), it would use AccountMapper.delete.

The Problem

For the initial version of the site (still up as of this writing, but soon to be upgraded), the "mapper" classes did their job. But all was not well under the hood. Since there were many different ways to select data, I sometimes had to make multiple mapper classes for the same type of value object. For example, a user might want to pull up information on a particular image, on their own images, on the images corresponding to a particular taxon, or just on all images. Each of these required a completely different method, and I had to struggle to keep the levels of duplicated code down. Duplicated code might sound like a minor annoyance, but it can have serious effects. It really complicates both testing and updating code.

Eventually I realized that the mapper classes should not be concerned with how to decide which objects to handle, only with how to handle them once they were specified. I created a new type of object, called a Qualifier, to store information on how to specify certain objects. As an example, a TotalQualifier object specifies all value objects of a given type. A FieldQualifier object specifies all value objects with a certain piece of data, for example, all accounts with a given email address. A KeyQualifier specifies one particular object by a unique identifier. And a ConjunctionQualifier qroups other qualifiers and selects only those objects which satisfy all of those qualifiers.

Formerly I had to write methods like retrieveForOwner, retrieveAll, retrieve, retrieveForTaxon, retrieveForLogin, etc. With the new structure, I could just have one method, retrieve, and pass it any kind of Qualifier object I wanted. The number of classes in the org.marchofman.mappers package shrunk down to a fraction of what it had been. Now it was down to the ideal: one mapper class for each type of value object.

Doing all this was a fair bit of work. Fortunately, I had already built automated unit tests using the excellent flexunit framework. Once I finished my initial refactoring work, I just ran the tests and could instantly see what I still needed to fix.

The Payoff

Now not only do I have a more streamlined and flexible server-side architecture, but also some generalized mapping classes which may greatly facilitate work on future projects. Is the code perfect? No, but it's much better than it was. And I can always refactor again if I need to....