Bioinformatics Vol. 16 no. 7 2000
Pages 619-627
© 2000 Oxford University Press
Original Paper |
Using traveling salesman problem algorithms for evolutionary tree construction
1 Institute for Scientific Computing, 8092 ETH Zurich, Switzerland
Received on September 13, 1999
; revised on January 21, 2000
; accepted on January 23, 2000
Motivation: The construction of evolutionary trees is one of the major problems in computational biology, mainly due to its complexity.
Results: We present a new tree construction method that
constructs a tree with minimum score for a given set of sequences,
where the score is the amount of evolution measured in PAM
distances. To do this, the problem of tree construction is reduced
to the Traveling Salesman Problem (TSP). The input for the TSP
algorithm are the pairwise distances of the sequences and the output
is a circular tour through the optimal, unknown tree plus the
minimum score of the tree. The circular order and the score can be
used to construct the topology of the optimal tree. Our method can
be used for any scoring function that correlates to the amount of
changes along the branches of an evolutionary tree, for instance it
could also be used for parsimony scores, but it cannot be used for
least squares fit of distances. A TSP solution reduces the space of
all possible trees to 
. Using this order, we can
guarantee that we reconstruct a correct evolutionary tree if the
absolute value of the error for each distance measurement is smaller
than 
, where
is the length of the shortest edge in the tree. For data
sets with large errors, a dynamic programming approach is used to
reconstruct the tree. Finally simulations and experiments with real
data are shown.
Availability: The software may be used via our cbrg server at http://cbrg.inf.ethz.ch/MultAlign.
Contact: chantal.roth{at}nobilitas.com
Supplementary information: An html and postscript version of this paper is available at http://chantal.nobilitas.com/(Papers section).