next up previous
Next: Bibliography Up: Using Traveling Salesman Problem Previous: Examples

Discussion

We have introduced a new tree construction method that constructs the tree with the minimum score for a given set of sequences. By using a Traveling Salesman approach to find a circular tour and the sequence data, we can construct the the tree with the minimum score in $O(n \log(n))$ time. We can guarantee that the reconstructed tree is correct, if the error of the distance measurement does not exceed $\frac{x}{2}$, where x is the shortest edge. The probability to get a wrong circular order is very low, as all other correct circular orders have to be worse than the wrong order. If the errors of the distance measurements are very large, then better results can be achieved via dynamic programming. But we think it still is important to use different tree construction algorithms and to compare the results and decide in each case which tree is suited best.

Chantal Korostensky
1999-07-14