General Modularity Example Module Projects & Files Commands & Scripting
Windows Menus Charts Tables Buttons & tools
Trees and Taxa Characters & Models Documentation General Utilities
Taxa and associated classes Trees and associated classes Tree drawing
Taxa: class Taxon class Taxa class Clade class Clades class TaxaGroup class TaxaPartition
Trees: Interface Tree Interface AdjustableTree class MesquiteTree class TreeVector
Drawing: class TreeDisplay class TreeDrawing class TreeDisplayExtra class TreeDecorator

Trees in Mesquite

(updated August 2005)

Trees in Mesquite are typically stored in objects of the class MesquiteTree. However, most modules receive trees as input merely as objects satisfying the interface Tree.

It might seem natural to also have a Node class, and a Tree would make reference to objects of the classes Node and Taxon. Nodes would maintain references to the Node objects that are linked directly to them in the tree (the ancestor and descendants). However, for reasons of speed, memory, and ease of use, the references to taxa and nodes within a Tree are done in shorthand, by integers referring to array position. Thus, nodes are referred to by number (node number 2, node number 3, etc.).

Interface Tree

This interface has methods for querying the tree object about what node is the root, what are the descendants and ancestors of a node, and so on. There are no methods for changing the tree topology (these are covered by the sub-interface AdjustableTree). The reason an interface is used as much as possible in Mesquite is to allow trees from other packages to be used in Mesquite's calculations by minor modification or a translator class.

To allow polytomies, the tree topology is indicated by a first daughter / next sister system. This is a similar system to that used in PAUP (Swofford) but is different from that used by PHYLIP (Felsenstein). Thus, to recurse upward from the root to the tips, at each node one goes to all of its daughter nodes by first visiting the node's first daughter, then the next sister of the first daughter, then the next sister of that next sister, and so on, until there are no more next sisters. Thus, a simple recursive procedure through the tree could be built as follows:

void recurse (Tree tree, int node) {
   for(int d = tree.firstDaughterOfNode(node); tree.nodeExists(d); d=tree.nextSisterOfNode(d))
	     recurse(tree, d);
}

The recursion can be started at the root as follows: recurse(tree, tree.getRoot());

There are some methods that allow the tree to be treated as purely unrooted (the methods ending in UR). These methods need to be passed both the current node and the previous node, to establish a temporary polarity, to yield the daughters according to the polarity. The tree can be entered at any node by calling the following procedure by recurseUnrooted(tree, node, node);



void recurseUnrooted (Tree tree, int anc, int node){
   for (int d = tree.firstDaughterOfNodeUR(anc, node); tree.nodeExists(d); d = tree.nextSisterOfNodeUR(anc, node, d))
      recurseUnrooted(tree, node, d);
}

Interface AdjustableTree (extends Tree)

This interface adds methods to change branching and branch lengths in the tree.

Class MesquiteTree (implements AdjustableTree)

A MesquiteTree object is one of the better-refined objects in Mesquite at the moment, which is perhaps not too surprising. It stores a phylogenetic tree, perhaps with branch lengths, and has many methods for querying for information about the tree and for modifying the tree.

The internal representation of tree information is private, in part because it may change and in part to protect the information against inappropriate adjustment. For the interested, the tree structure is stored entirely in integer arrays whose ith element stores some information relevant to node i (e.g., the number of its mother node).

TreeVector

A TreeVector object is a set of stored trees, and corresponds to a TREES block in a NEXUS file.


© W. Maddison & D. Maddison 1999-2005