Supertree

by Rod Page (r.page@bio.gla.ac.uk)

Supertree is an experimental command line program for constructing supertrees. It implements Semple and Steel's algorithm MinCutSupertree (original and modified), as well as MRP coding. It can also compute cluster graphs. An early version is available online through the supertree server and TreeBASE.

The program is in a very early stage of development, so expect bugs. Feedback is welcome. Future plans include adding a graphical user interface, perhaps by making the supertree program a "plugin" for TreeView X.

Papers

Papers

The algorithm used in the supertre program is described here:

Page, R.D.. Modified mincut supertrees. Submitted to WABI 2002. [PS] [PDF].

Download

Source for Unix/Linux boxes (supertree-0.3.tgz)

Executable for MacOS X (supertree.macosx.hqx)

Executable for Mac OS 8/9 (supertree.PPC.hqx)

Compiling supertree

Supertree can be compiled on a Unix machine using gcc 2.95.2 or later.

Requirements

You will need a copy of the Graph Template Library. Install this before compiling supertree.

Mac OS X notes

There are problems with automake/sed on Mac OS X, so the configure script for GTL won't work. To get around this, follow these steps

Download the file version.h and place it in the include/GTL folder
Download the make file makefile.macosx and place it in the root of the GTL folder
In a terminal window type make -f makefile.macosx

Alternatively, there is a binary installer for GTL 1.1.0 for Mac OS 10.2.x ("Jaguar") available to registered users of GTL.

Building supertree

Create a directory (e.g., "supertree") and copy the source archive (e.g. supertree-0.2.tgz) into that directory.
Do gunzip supertree-0.2.tgz and tar -xvf supertree-0.2.tar to get the source.
type make

Running supertree

Input files

The Supertree Server accepts tree files in either Newick or NEXUS format. The Newick format is simply a list of the trees in the standard nested parenthesis format,, one tree description per line. For NEXUS files the trees must all be in a single TREES block. For the example in Semple and Steel, the Newick file is

(((a,b),c),(d,e));
((a,b),(c,d));

and the NEXUS file is:

#nexus

[! Semple, C. and Steel, M. "A supertree method for rooted trees", Figure 1]

begin trees;
	tree T1 = [&R] [&W 1] (((a,b),c),(d,e));
	tree T2 = [&R] [&W 1] ((a,b),(c,d));
end;

Command line

Option	Action	Remarks
-v	show version information
-g	write ST and ST/Emax to GML file(s)	GML files can be viewed using Graphlet
-l	output taxon labels when writing graph files	The default is to label the nodes by taxon number
-d	write ST and ST/EMax to dot files	.dot file can be viewed using the graphviz tools
-b	verbose	Print the input trees, and extra information about the progress of the algorithm to the screen
-n filename	write NEXUS file	Write the supertree to a NEXUS file <filename>
-w	use tree weights	By default each tree has equal weight. If weights are included in the NEXUS file, the -w option will use those weights
-m filename	write MRP matrix to file <filename>	The MRP matrix is in NEXUS format for analysis using PAUP.
-k filename	write Newick file	Write the supertree to a Newick tree file <filename>
-a n	choose algorithm, either 1 for Rod Page modification, or 0 for original Semple and Steel
-c n	compute cluster graph for k=n	The program will construct the cluster graph for the input value of k, then finds all components of that graph and outputs the trees belong to each component to a file called cluster.<k>.<count>.<size>.tre where count is the running count of the number of components of the graph, and size is the number of trees in that component. You can use this option to generate well connect sets of tres for further analysis. If the -g or -d options are on, then the cluster graph is written to the file "cluster.gml" or "cluster.dot", respectively.
-p filename	write tree to Postscript file <filename>

Simple example command lines include:

supertree -a0 -n s.nex TreeLib/steel.tre

This uses the original Semple and Steel mincut algorithm (a0) to build the supertree from the input file TreeLib/steel.tre, and outputs the result in NEXUS format to the file s.nex.

supertree -a1 -n s.nex TreeLib/steel.tre

does the same but uses a modified algorithm.

supertree -a0 -k s.tre TreeLib/steel.tre

would output a Newick tree description.

Viewing the results

The output tree can be displayed in TreeView or TreeView X.

Drawing graphs

Supertree can output ST, ST/Emax, and cluster graphs in GML and .dot formats. GML files can be displayed by Graphlet (Windows, Linux, and Solaris), .dot format files can be displayed by AT&T's free Graphviz package (binaries available for most platforms). Pixelglow Software have a released a nice Mac OS X GUI to Graphivz. Command line versions of the GraphViz programs for Mac OS X are also available.

The supertree distribution also comes with a small script g2ps, which will generate Postscript files for all .dot files in the current directory using neato. The Postscript files can then be viewed using your system's Postscript viewer.

Supertree

Papers

Download

Compiling supertree

Requirements

Mac OS X notes

Building supertree

Running supertree

Input files

Command line

Viewing the results

Drawing graphs

Links

Supertree programs

Supertree concepts

Graph libraries