rooting an ultrametric tree

Rooting an ultrametric tree

By Bang Ye Wu, E-mail; Home Page

Introduction: An ultrametric tree is a rooted tree in which each internal node has the same length to all the the leaves in the subtree rooted at it. Usually the root of a tree is determined by OUTGROUPs. Here we developed an algorithm to determine the root by the observed distances. Given an unrooted tree and distances among species, the algorithm takes O(n^2) time to root the tree such that the size of the rooted ultrametric tree is minimum subject to that, for each pair of species, the distance on the tree is no less than the observed one.

The manuscript of the article (not available yet).
Download the program: a source in C, executable file (MS-DOS), a sample input file
Technical Notes

Documentation of the program

Command: "mutroot [input-file-name] [output-file-name]"
Input: the input file is a text file consisting of
    the number of species: n
    the binary tree in Phylip format: The species are labelled as integer between 0~n-1.
        The tree is arbitrarily rooted.
    the distances : the upper triangle of the distance matrix, in row major order, and separated by
        space or [carriage return].
Output: A text file containing the rooted tree in Phylip format. The branch lengths are included.
A sample input file :
5
((1,2),((3,0),4));
2.0 1.8 4.0 3.0
0.2 2.2 1.0
3.2 1.0
0.8
The first line => there are 5 species and labelled as 0,1,2,3,4.
The second line => the binary tree (arbitrary rooted)
3rd~6th lines=>   m[0,1]=2.0, m[0.2]=1.8, m[0,3]=4.0, m[0,4]=3.0,
                            m[1,2]=0.2,....
                            ....
                            m[3,4]=0.8

Technical Notes

Related topic: ultrametric tree reconstruction
How to compute the minimum ultrametric size of a rooted tree
=> see the article in the page ultrametric tree reconstruction.
The maximum number of species is defined by a constant MAX_N in the program. The number is limited by the limitation of memory under MS-DOS envirement.