Combining polynomial running time and fast convergence for the disk-covering method

摘要

This paper treats polynomial-time algorithms for reconstruction of phylogenetic trees. The disc-covering method (DCM) presented by Huson et al. (J. Comput. Biol. 6 (3/4) (1999) 369) is a method that boosts the performance of phylogenetic tree construction algorithms. Actually, they gave two variations of DCM-Buneman. The first variation was guaranteed to recover the true tree with high probability from polynomial-length sequences (i.e. polynomial in the number of given taxa), but it was not proven to run in polynomial time. The second variation was guaranteed to run in polynomial time. However, it is a heuristic in the sense that it was not proven to recover the true tree with high probability from polynomial-length sequences.We present an improved DCM. The difference between our improved DCM and the heuristic variation of the original DCM is marginal. The main contribution of this paper is the analysis of the algorithm. Our analysis shows that the improved DCM combines the desirable properties of the two variations of the original DCM. That is, it runs in polynomial time and it recovers the true tree with high probability from polynomial-length sequences. Moreover, this is true when the improved DCM is applied to the Neighbor-Joining, the Buneman, as well as the Agarwala algorithm. A key observation for the result of Huson et al. was that threshold graphs of additive distance functions are chordal. We prove a chordal graph theorem concerning minimal triangulations of threshold graphs constructed from distance functions which are close to being additive. This theorem is the key observation behind our improved DCM and it may be interesting in its own right.