mut

Minimum Ultrametric tree

Introduction

The minimum ultrametric tree is a distance method for constructing evolutionary tree among species. An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T=(V,E,w) with leaf set {1..n} such that the distance between any pair of leaves on the tree is no less than the given distance and the total weight on the tree edges is minimized. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology, but NP-hard.

An efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs is available here. The experimental results show that it can find an optimal solution for 25 species within reasonable time. The algorithm is described in the following paper:

Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang, Exact and approximation algorithms for constructing ultrametric trees from distance matrices, Journal of Combinatorial Optimization, vol. 3 pp. 199-211, 1999. A primary version appeared in Proceedings of the Fourth Annual International Computer and Combinatorial Conference (COCOON'98), LNCS 1449, pp. 299--308, Springer-Verlag, 1998.

Program Description

Environment: MS-DOS on PC.

Input: A text file for the input matrix (only upper triangle), the elements should be integers and the first line is the number of species. Example:
5
10 8 4 2
6 2 2
2 2
1

Output: a text file which is the standard parenthesis description of a tree. This file can be the input of some software for viewing tree, for example, TreeView.

Note: The will take lots of time when the number of species are more than (about) 15. For a 24*24 matrix input, it often need 24 hour to compute the optimum tree.

Program download: click here