18th October 2006

                 Supertree Construction with Constraint Programming
                 --------------------------------------------------


Getting started
---------------
After unpacking the files (supertrees.tgz) you need to install the JChoco jar file (JChoco is a constraint 
programming toolkit and you can find more about it here http://choco.sourceforge.net/).
Then you are ready to run the superTree builders

To install the jar file in unix
-------------------------------
Include in your .cshrc file the following

    setenv CLASSPATH /yourPathInfo/choco-1_0b003.jar:.

where yourPathInfo is the location that you have placed the file choco-1_0b003.jar

To install the jar file in micro$oft windows
--------------------------------------------
Go to settings -> control panel -> system
Select advanced
Select Environment Variables
Edit CLASSPATH to include the following

   X:\yourPathInfo\choco-1_0b003.jar;.;

where again X:\yourPathinfo\ is the location that you have placed the file choco-1_0b003.jar


OneTree
-------
To build a superTree go to directory OneTree. You can combine two trees or combine many trees
(a forest). 

 Combine two trees
 -----------------

  java Build birdsA.tre birdsB.tre

Note that the resultant tree is output in Newick format along with the ultrametric matrix
and a list of species in that tree. This might be captured in an output file, such as 
stree.tre, and then displayed using Rod Page's treeView 
(http://taxonomy.zoology.gla.ac.uk/rod/treeview.html)


 Combine a forest
 ----------------
  
  java FBuild forestABDF

Note that the file forestABDF contains first an integer (the number of trees input) and then
a number of file names of trees to combine. Again, the resultant tree is output in Newick 
format along with the ultrametric matrix and a list of species in that tree. Again, capture
this in a file and display using treeView.


RBuild
------
This is ``Rank Build''. Go to directory RBuild

  Combine two ranked trees
  ------------------------

   java RBuild cats1.tre cats2.tre 

Again, the resultant tree is output in Newick format along with the ultrametric matrix and a 
list of species in that tree. Again, capture this in a file and display using treeView.


Future
------
This directory contains ``future'' work. It is essentially RBuild above but is enhanced to find
all trees or the ``best'' tree (by best I mean the super tree with minimal fans).

 Combine two ranked trees
 ------------------------

    java RBuild cats1.tre cats2.tre option

 where option is first\all\best


conventional
------------
Directory conventional contains code that breaks up and then builds a supertree using
the algorithms from Ng & Wormald's paper in DAM 69 (1996) pages 19-31 "Reconstruction
of rooted trees from subtrees". This respects triples and fans. Again it is called as
follows:

   java Build birdaA.tre birdsB.tre

You can use this to compare outputs with the constraint programming modules. If a supertree
can't be produced then the program prints out "FAIL" and then generates a load of rubbish.

NOTE
---- 
The "conventional" output includes a "null" before the closing ";". If you use this
to combine two supertrees, i.e. combine A+B to get X then combine C+D to get Y,
and then combine X+Y to get Z, you must edit X and Y to remove the null. Sorry about this.
I will try and fix it soon


Warning
-------
There are no guarantees with this software. Do not attempt to use it as part of an
air traffic control system, a weapons guidance system, a control system for a nuclear 
power station, or making critical decisions on medications for cancer patients.


Acknowledgements
-----------------
Pierre Flener and Xavier Lorca have been a great help in developing and debugging this code. 
Judgement day will come, I will have to come good, and buy them loads of beer.


Patrick Prosser
July 2006


Bugs (a history)
----------------
July 2006
I think the date is correct, but here's the bug. The constraint programming encoding 
enforces the ultrametric constraint between 3 variables. That means fans must only involve
3 variables. If we have the fan (a,b,c,d) we produced only the fans (a,b,c) and (b,c,d).
This is not enough. We need to produce all possible 3-fans, i.e. (a,b,c), (a,b,d), (a,c,d),
(b,c,d) and that is Choose 3 from n where the fan contains n species. 


October 2006 
Pierre and Xavier found a bug in the breakUp method. If in the process of
breaking up we reach the root of the tree and it has more than 2 leafs the method
terminates without producing a fan (as it should). This has been fixed. Test data
is in the directory ``flener'' of the OneTree directory

