| 1. |
- Dress, Andreas, et al.
(författare)
-
Hereditarily Optimal Realizations of Consistent Metrics.
- 2006
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 10:1, s. 63-76
-
Tidskriftsartikel (refereegranskat)abstract
- One of the main problems in phylogenetics is to find good approximations of metrics by weighted trees. As an aid to solving this problem, it could be tempting to consider optimal realizations of metrics—the guiding principle being that, the (necessarily unique) optimal realization of a tree metric is the weighted tree that realizes this metric. And, although optimal realizations of arbitrary metrics are, in general, not trees, but rather weighted networks, one could still hope to obtain a phylogenetically informative representation of a given metric, maybe even more informative than the best approximating tree. However, optimal realizations are not only difficult to compute, they may also be non-unique. Here we focus on one possible way out of this dilemma: hereditarily optimal realizations. These are essentially unique, and can be described in a rather explicit way. In this paper, we recall what a hereditarily optimal realization of a metric is and how it is related to the 1-skeleton of the tight span of that metric, and we investigate under what conditions it coincides with this 1-skeleton. As a consequence, we will show that hereditarily optimal realizations for consistent metrics, a large class of phylogentically relevant metrics, can be computed in a straight-forward fashion.
|
|
| 2. |
|
|
| 3. |
- Herrmann, Sven, et al.
(författare)
-
Optimal realizations of two-dimensional, totally-decomposable metrics
- 2015
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 338:8, s. 1289-1299
-
Tidskriftsartikel (refereegranskat)abstract
- A realization of a metric d on a finite set X is a weighted graph (G, w) whose vertex set contains X such that the shortest-path distance between elements of X considered as vertices in G is equal to d. Such a realization (G, w) is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. A. Dress (1984) showed that the optimal realizations of a metric dare closely related to a certain polytopal complex that can be canonically associated to d called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of d must always contain an optimal realization as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally-decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realizations of two-dimensional totally-decomposable metrics. (C) 2015 Elsevier B.V. All rights reserved.
|
|
| 4. |
- Koolen, Jack, et al.
(författare)
-
Concerning the relationship between realizations and tight spans of finite metrics
- 2007
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 38:3, s. 605-614
-
Tidskriftsartikel (refereegranskat)abstract
- Given a metric d on a finite set X, a realization of d is a weighted graph $G=(V,E,w\colon \ E \to {\Bbb R}_{>0})$ with $X \subseteq V$ such that for all $x,y \in X$ the length of any shortest path in G between x and y equals d(x,y). In this paper we consider two special kinds of realizations, optimal realizations and hereditarily optimal realizations, and their relationship with the so-called tight span. In particular, we present an infinite family of metrics {dk}k≥1, and—using a new characterization for when the so-called underlying graph of a metric is an optimal realization that we also present—we prove that dk has (as a function of k) exponentially many optimal realizations with distinct degree sequences. We then show that this family of metrics provides counter-examples to a conjecture made by Dress in 1984 concerning the relationship between optimal realizations and the tight span, and a negative reply to a question posed by Althofer in 1988 on the relationship between optimal and hereditarily optimal realizations.
|
|
| 5. |
- Koolen, Jack H., et al.
(författare)
-
Injective optimal realizations of finite metric spaces
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:10, s. 1602-1610
-
Tidskriftsartikel (refereegranskat)abstract
- A realization of a finite metric space (X, d) is a weighted graph (G, w) whose vertex set contains X such that the distances between the elements of X in G correspond to those given by d. Such a realization is called optimal if it has minimal total edge weight. Optimal realizations have applications in fields such as phylogenetics, psychology, compression software and Internet tomography. Given an optimal realization (G, w) of (X, d), there always exist certain "proper" maps from the vertex set of G into the so-called tight span of d. In [A. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321-402], Dress conjectured that any such map must be injective. Although this conjecture was recently disproven, in this paper we show that it is possible to characterize those optimal realizations (G, w) for which certain generalizations of proper maps - that map the geometric realization of (G, w) into the tight span instead of its vertex set - must always be injective. We also prove that these "injective" optimal realizations always exist, and show how they may be constructed from non-injective ones. Ultimately it is hoped that these results will contribute towards developing new ways to compute optimal realizations from tight spans.
|
|
| 6. |
|
|
| 7. |
- Koolen, Jack, et al.
(författare)
-
Optimal realizations of generic 5-point metrics
- 2009
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 30:5, s. 1164-1171
-
Tidskriftsartikel (refereegranskat)abstract
- Given a metric cl oil a finite set X, a realization of d is a triple (G, phi, omega) consisting of a graph G = (V, E), a labeling phi : X -> V, and a weighting omega : E -> R->0 such that for all x, y is an element of X the length of any shortest path in G between phi(x) and phi(y) equals d(x, y). Such a realization is called optimal if parallel to G parallel to := Sigma(e is an element of E) omega(e) is minimal amongst all realizations of d. In this paper we will consider optimal realizations of generic five-point metric spaces. In particular, we show that there is a canonical subdivision C Of the metric fail of five-point metrics into cones such that (i) every metric d in the interior of a cone C is an element of C has a unique optimal realization (G, phi, omega), (ii) if d' is also in the interior of C with optimal realization (G', phi', omega') then (G, phi) and (G', phi') are isomorphic as labeled graphs, and (iii) any labeled graph that underlies all optimal realizations of the metrics in the interior of some cone C e C must belong to one of three isomorphism classes.
|
|
| 8. |
|
|
| 9. |
|
|
| 10. |
|
|
