L-Infinity optimization in tropical geometry and phylogenetics

MaRDI QIDQ6274533zbMATH OpenFDO

Authors Daniel Irving Bernstein, Colby Long

Publication date 12 June 2016

Abstract: We investigate uniqueness issues that arise in $l^{i}nfty$-optimization to linear spaces and Bergman fans of matroids. For linear spaces, we give a polyhedral decomposition of $mathbb{R}^n$ based on the dimension of the set of $l^{i}nfty$-nearest neighbors. This implies that the $l^{i}nfty$-nearest neighbor in a linear space is unique if and only if the underlying matroid is uniform. For Bergman fans of matroids, we show that the set of $l^{i}nfty$-nearest points is a tropical polytope and give an algorithm to compute its tropical vertices. A key ingredient here is a notion of topology that generalizes tree topology. These results have practical implications for distance-based phylogenetic reconstruction using the $l^{i}nfty$-metric. We analyze the possible dimensions of the set of $l^{i}nfty$-nearest equidistant tree metrics to an arbitrary dissimilarity map and the number of tree topologies represented in this set. For both 3 and 4-leaf trees, we decompose the space of dissimilarity maps relative to the tree topologies represented.

This page was built for publication: L-Infinity optimization in tropical geometry and phylogenetics

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