implementations of the HGT algorithms

HGT/FP implementation

The HGT/FP algorithm of evolutionary tree reconstruction is implemented in C, and is available under the GNU General Public License. Download hgtfp.c, and tell me whether you like it (csuros AT iro.umontreal.ca).

HGT and Fast-HGT implementation in Perl

(This is mostly legacy code...)

The Harmonic Greedy Triplets and Fast Harmonic Greedy Triplets algorithms, along with some extra code for simulation experiments, are implemented in Perl. The implementation consists of several perl modules and some example scripts. It is in a preliminary state, without extensive testing done. If you want to download them, make sure to download all modules and put them in the same directory, called fHGT (simplest is to copy the directory structure at this location). Alternatively, a gzipped tar archive (28k) can be downloaded, which comprises all the files.

Perl modules

The modules are expected to be in a directory called fHGT, relative to the script that wants to use them. A short man-style documentation is available for scripts. The available modules are the following.

fHGT::Algo - documentation or source code (20k)
Main package implementing the phylogeny building algorithms' top-level steps.
fHGT::Split - documentation or source code (14k)
Subroutines used by the tree building algorithms for selecting triplets.
fHGT::Distance - documentation or source code (10k)
Manipulation of pairwise distances.
fHGT::Node - documentation or source code (6k)
Object-oriented package for tree node access.
fHGT::Tree - documentation or source code (22k)
Implemenation of the tree structure.
fHGT::Bipartition - documentation or source code (3k)
Subroutines for calculating bipartitions, used for comparing phylogenies.
fHGT::Simulation - documentation or source code (22k)
Subroutines for simulations: sample generation etc.

Example scripts

The scripts have been tested on Linux and MacOS (Classic). In order to run them on Mac, you need MacPerl. For Unix or Linux machines, don't forget to change the first lines to refer to the location of perl on your system (usually /usr/local/bin/perl on Unix, /usr/bin/perl on Linux). This can be done using the setperl.csh csh script.

All scripts give a description of their arguments when called with the -h switch.

There are three file formats pertinent to these scripts. The sample file is an ``almost-Newick-compatible'' file for aligned sample sequences. (As of now, I haven't written a subroutine to read one in, but there is a script that generates a sample file. Huh!) The closeness file (more details in fHGT::Distance) is produced from a sample, it contains the pairwise closeness values between taxa (closeness is exp(-distance)). The tree file (more details in fHGT::Tree) is a Newick format description of a phylogeny.

There are some examples available using these scripts.

buildtree_HGT - source code
Builds an unrooted phylogeny from a closeness file using the HGT algorithm.
buildtree_fHGT - source code
Builds an unrooted phylogeny from a closeness file using the Fast-HGT algorithm.
genclose - source code
Generates a closeness file for a given phylogeny.
random_tree - source code
Generates a random tree (see fHGT::Simulation::Random_Tree()).
experiment_HGT - source code
Generates a sample from a tree, runs the HGT algorithm and checks whether the result matches the original tree.
experiment_fHGT - source code
Generates a sample from a tree, runs the Fast-HGT algorithm and checks whether the result matches the original tree.
compare_trees - source code
Compares two phylogenies with the same terminal taxa using the Robinson-Foulds distance.