Archive for July, 2015

Direction of tree growth

As someone with computer science degrees who is working on an evolutionary biology project, I have to be constantly vigilant about tree-growth direction confusions. Just now I found the following sentence in an article in Algorithmica:

For v, w nodes in T, we say that v lies below w if the path from v to the root of T passes through w.

Now real trees are oriented with their root(s) at the bottom, the trunk in the middle, then the branches, and the leaves (or needles) at the very top. If v is a leaf or branch, how can it lie below something that’s on the path from v to the root?

Maybe we should picture a hook-shaped or umbrella-shaped tree, with its trunk shooting up and all of its branches and leaves hanging down from the top of the trunk. There are trees like that, I think. Or, a hanging vine or epiphyte, growing downward from the spot where it’s planted. Then v could be below w with w on the path from v to the root. (Hmm, I don’t think an epiphyte would grow down; the whole point of their plant-on-tree adaptation is to obtain sunlight, which of course comes from above.)

Drawing trees sideways is a neutral solution to make life equally difficult for both cultures, and you see a lot of phylogenetic trees drawn this way in the literature.

The phylogenetics folks on the project speak of one node being ‘deeper’ than another. It took me a while to figure this out but their usage is in agreement with real trees if you imagine them submerged, as you’d see in the forests near the mouth of the Amazon, the ones that have frugivorous fish. Of course this is contrary to the way ‘depth’ is used in computer science. When computer scientists talk about depth-first search, they mean to start at the leaves and go toward the root.

How did trees get flipped upside down like this? I think it comes from sentence diagramming, where by convention all the trees are drawn upside down. I would guess the custom found its way from sentence diagramming to computer science via Chomsky, who was very influential in the early days of CS, probably more so than, say, Ernst Mayr (see figure here to see how he drew them).

Added 2015-07-30:

1. In lattice theory one speaks of lower and upper bounds, and top and bottom elements. One interpretation of a lattice is as a family of sets, and when this is done usually the bigger sets go toward the top and the smaller ones toward the bottom. This is reflected in the usual v-like symbol for least upper bound or “join”, which reminds me of the u-like set union symbol, and greatest lower bound or “meet”, which looks like intersection. (By duality you could treat everything the opposite and the theory would all still work.) If you think of taxa being set-like, this puts the small taxa at the bottom and the large ones at the top. This is the opposite of what the biologists would prefer.

People who work on the mathematics of phylogenetic trees often appeal to the theory of upper semilattices, which being a flavor of lattice theory puts the root of the tree at the top, so they will have at least as much disorientation risk as I do.

2. In traditional taxonomies there is the notion of ‘higher’ and ‘lower’ taxonomic rank. The ‘higher’ ones, like kingdom, are the ones closer to the root of the taxonomic tree, and the ‘lower’ ones like genus are closer to the tips. This inverted orientation comes from applying a different metaphor, one incompatible with trees. The image this conjures for me is medieval power structures where the more powerful you are the higher your elevation. The higher you are, the better you can be heard (to command), the further you can see (for intelligence gathering), and the better positioned you are for waging war. So even within biology there is no consistency.

[Added 2016-03-12: good discussion of tree orientation on Tufte’s site; study on effect of tree layout on comprehension. Thanks Jim Allman!]

Categories: Uncategorized