L-infinity optimization to linear spaces and phylogenetic trees

DOI10.1137/16M1101027MaRDI QIDQ5346563zbMATHOpenAlexWikidataFDO

Authors Daniel Irving Bernstein, Colby Long

Publication date 24 May 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05127

zbMATH Keywords

tree metricultrametricoriented matroidzonotopedistance-based methodssubdominant ultrametric

Mathematics Subject Classification ID

Problems related to evolution (92D15) Oriented matroids in discrete geometry (52C40) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: Given a distance matrix consisting of pairwise distances between species, a distance-based phylogenetic reconstruction method returns a tree metric or equidistant tree metric (ultrametric) that best fits the data. We investigate distance-based phylogenetic reconstruction using the $l^{i}nfty$-metric. In particular, we analyze the set of $l^{i}nfty$-closest ultrametrics and tree metrics to an arbitrary dissimilarity map to determine its dimension and the tree topologies it represents. In the case of ultrametrics, we decompose the space of dissimilarity maps on 3 elements and on 4 elements relative to the tree topologies represented. Our approach is to first address uniqueness issues arising in $l^{i}nfty$-optimization to linear spaces. We show that the $l^{i}nfty$-closest point in a linear space is unique if and only if the underlying matroid of the linear space is uniform. We also give a polyhedral decomposition of $r^m$ based on the dimension of the set of $l^{i}nfty$-closest points in a linear space.

Recommendations

• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Fitting distances by tree metrics with increment error
• Constructing ultrametric and additive trees based on the \(L_1\) norm.
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• \(l_\infty\)-approximation via subdominants.

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Convexity in tree spaces
• Lectures on Polytopes
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Subdominant matroid ultrametrics
• The Bergman complex of a matroid and phylogenetic trees
• The tropical Grassmannian
• Tropical Fermat-Weber points
• \(l_\infty\)-approximation via subdominants.

Cited in

(7)

• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope
• \(l_\infty\)-approximation via subdominants.
• Tropical geometric variation of tree shapes
• New Gromov-inspired metrics on phylogenetic tree space
• Subdominant matroid ultrametrics
• Tropical Fermat-Weber points

Describes a project that uses

Uses Software

• Maple

This page was built for publication: L-infinity optimization to linear spaces and phylogenetic trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346563)