A robust model for finding optimal evolutionary tree

DOI10.1007/BF01188585zbMath0831.92019MaRDI QIDQ1902471

Yanyan Li

Publication date: 12 February 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

clusteringNP-hardpolynomial-time algorithmsefficient algorithmsultrametric matricesNP- completeadditive treesultrametric treesdistance-based methodsadditive distance matrixevolutionary tree reconstruction

Mathematics Subject Classification ID

Problems related to evolution (92D15) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational methods for problems pertaining to biology (92-08)

Related Items

Testing metric properties ⋮ An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree ⋮ Tree edge decomposition with an application to minimum ultrametric tree approximation ⋮ An algorithm for finding a representation of a subtree distance ⋮ A branch-price-and-cut algorithm for the minimum evolution problem ⋮ A constructive algorithm for realizing a distance matrix ⋮ Discrete convexity in joint winner property ⋮ Completion of tree metrics and rank 2 matrices ⋮ Tree reconstruction from triplet cover distances ⋮ Unnamed Item ⋮ A note on tree realizations of matrices ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ UPGMA and the normalized equidistant minimum evolution problem ⋮ On the extension of a partial metric to a tree metric ⋮ `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers ⋮ A few logs suffice to build (almost) all trees. II ⋮ The balanced minimum evolution problem under uncertain data ⋮ Finding the closest ultrametric ⋮ On the hardness of inferring phylogenies from triplet-dissimilarities ⋮ Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem ⋮ \(\Delta\) additive and \(\Delta\) ultra-additive maps, Gromov's trees, and the Farris transform ⋮ The minimum evolution problem: Overview and classification ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Approximation algorithms for the shortest total path length spanning tree problem ⋮ \(l_\infty\)-approximation via subdominants. ⋮ Distinguished Minimal Topological Lassos ⋮ A structured family of clustering and tree construction methods ⋮ Fishing for minimum evolution trees with neighbor-nets ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of inferring phylogenies from dissimilarity matrices
• The complexity of ultrametric partitions on graphs
• Sequence comparison with concave weighting functions
• A fast algorithm for constructing trees from distance matrices
• The complexity of reconstructing trees from qualitative characters and subtrees
• A molecular sequence metric and evolutionary trees
• The structure and construction of taxonomic hierarchies
• Fast Algorithms for Finding Nearest Common Ancestors
• Simple method for constructing phylogenetic trees from distance matrices.
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• On the hardness of approximating minimization problems