Fitting Distances by Tree Metrics with Increment Error

Bin Ma (), Lusheng Wang () and Louxin Zhang ()
Additional contact information
Bin Ma: Peking University
Lusheng Wang: City University of Hong Kong
Louxin Zhang: National University of Singapore, Kent Ridge Digital Labs

Journal of Combinatorial Optimization, 1999, vol. 3, issue 2, No 5, 213-225

Abstract: 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 n 1/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.

Keywords: phylogenes; neighbor-joining method; ultametric matrixes (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009837726913 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:3:y:1999:i:2:d:10.1023_a:1009837726913

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009837726913

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().