Fitting Distances by Tree Metrics with Increment Error

Abstract

The Lp-min increment fit and Lp-min increment ultrametric fit problems are two popular optimization problems arising from distance methods for reconstructing phylogenetic trees. This paper proves 1. An O (n2) algorithm for approximating L∞-min increment fit within ratio 3. 2. A ratio-O(n1/p) polynomial time approximation to Lp-min increment ultrametric fit. 3. The neighbor-joining algorithm can correctly reconstruct a phylogenetic tree T when increment errors are small enough under L∞-norm.