Fitting Distances by Tree Metrics with Increment Error

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

12 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)213-225
Journal / PublicationJournal of Combinatorial Optimization
Volume3
Issue number2-3
Publication statusPublished - 1999

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.

Research Area(s)

  • Neighbor-joining method, Phylogenes, Ultametric matrixes

Citation Format(s)

Fitting Distances by Tree Metrics with Increment Error. / Ma, Bin; Wang, Lusheng; Zhang, Louxin.

In: Journal of Combinatorial Optimization, Vol. 3, No. 2-3, 1999, p. 213-225.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review