×

Order distances and split systems. (English) Zbl 07566359

Summary: Given a pairwise distance \(\boldsymbol{D}\) on the elements in a finite set \(\boldsymbol{X}\), the order distance \(\boldsymbol{\Delta}\boldsymbol{(D)}\) on \(\boldsymbol{X}\) is defined by first associating a total preorder \(\preceq_x\) on \(\boldsymbol{X}\) to each \(x \in \boldsymbol{X}\) based on \(\boldsymbol{D}\), and then quantifying the pairwise disagreement between these total preorders. The order distance can be useful in relational analyses because using \(\boldsymbol{\Delta}\boldsymbol{(D)}\) instead of \(D\) may make such analyses less sensitive to small variations in \(\boldsymbol{D}\). Relatively little is known about properties of \(\boldsymbol{\Delta}\boldsymbol{(D)}\) for general distances \(\boldsymbol{D}\). Indeed, nearly all previous work has focused on understanding the order distance of a treelike distance, that is, a distance that arises as the shortest path distances in a tree with non-negative edge weights and \(\boldsymbol{X}\) mapped into its vertex set. In this paper we study the order distance \(\boldsymbol{\Delta}\boldsymbol{(D)}\) for distances \(\boldsymbol{D}\) that can be decomposed into sums of simpler distances called split-distances. Such distances \(\boldsymbol{D}\) generalize treelike distances, and have applications in areas such as classification theory and phylogenetics.

MSC:

06-XX Order, lattices, ordered algebraic structures

Software:

FlatNJ

References:

[1] Semple, C.; Steel, M., Phylogenetics (2003), Oxford: Oxford University Press, Oxford · Zbl 1043.92026
[2] Bonnot, F., Guénoche, A., Perrier, X.: Properties of an order distance associated to a tree distance. In: Diday, E. (ed.) Ordinal and Symbolic Data Analysis, pp 252-261. Springer, Berlin (1996) · Zbl 0901.92039
[3] Fagin, R.; Kumar, R.; Mahdian, M.; Sivakumar, D.; Vee, E., Comparing partial rankings, SIAM J. Discret. Math., 20, 628-648 (2006) · Zbl 1121.06002 · doi:10.1137/05063088X
[4] Giakoumakis, V.; Monjardet, B., Coefficients d’accord entre deux préordres totaux, Stat. Anal. Données, 12, 46-99 (1987) · Zbl 0645.06001
[5] Guénoche, A., Order distance associated with a hierarchy, J. Classif., 14, 101-115 (1997) · Zbl 0897.92044 · doi:10.1007/s003579900005
[6] Guénoche, A.: Order distances in tree reconstruction. In: Mirkin, B. (ed.) Mathematical Hierarchies and Biology, pp 171-182. American Mathematical Society, Providence (1997) · Zbl 0886.05051
[7] Guénoche, A., Ordinal properties of tree distances, Discret. Math., 192, 103-117 (1998) · Zbl 0956.05031 · doi:10.1016/S0012-365X(98)00068-5
[8] Deza, M.; Laurent, M., Geometry of Cuts and Metrics (1997), Berlin: Springer, Berlin · Zbl 1210.52001 · doi:10.1007/978-3-642-04295-9
[9] Kearney, P., A six-point condition for ordinal matrices, J. Comput. Biol., 4, 143-156 (1997) · doi:10.1089/cmb.1997.4.143
[10] Bandelt, H-J; Dress, A., A canonical decomposition theory for metrics on a finite set, Adv. Math., 92, 47-105 (1992) · Zbl 0789.54036 · doi:10.1016/0001-8708(92)90061-O
[11] Bryant, D.; Dress, A., Linearly independent split systems, Eur. J. Combi., 28, 1814-1831 (2007) · Zbl 1121.93015 · doi:10.1016/j.ejc.2006.04.007
[12] Spillner, A.; Nguyen, B.; Moulton, V., Constructing and drawing regular planar split networks, IEEE/ACM Trans. Comput. Biol. Bioinforma., 9, 395-407 (2012) · doi:10.1109/TCBB.2011.115
[13] Bryant, D.; Moulton, V., NeighborNet: An agglomerative method for the construction of phylogenetic networks, Mol. Biol. Evol., 21, 255-265 (2004) · doi:10.1093/molbev/msh018
[14] Balvočiūtė, M.; Spillner, A.; Moulton, V., FlatNJ: A novel network-based approach to visualize evolutionary and biogeographical relationships, Syst. Biol., 63, 383-396 (2014) · doi:10.1093/sysbio/syu001
[15] Felsner, S., Geometric Graphs and Arrangements (2004), Wiesbaden: Vieweg, Wiesbaden · Zbl 1051.05036 · doi:10.1007/978-3-322-80303-0
[16] Kalmanson, K., Edgeconvex circuits and the travelling salesman problem, Can. J. Math., 27, 1000-1010 (1975) · Zbl 0284.05117 · doi:10.4153/CJM-1975-104-6
[17] Chepoi, V.; Fichet, B., A note on circular decomposable metrics, Geom. Dedicata., 69, 237-240 (1998) · Zbl 0896.54013 · doi:10.1023/A:1004907919611
[18] Christopher, G., Farach, M., Trick, M.: The structure of circular decomposable metrics. In: Proc. 4th Annual European Symposium on Algorithms. LNCS. doi:10.1007/3-540-61680-2_77, pp 486-500. Springer, Berlin (1996) · Zbl 1380.90234
[19] Bansal, M.; Fernández-Baca, D., Computing distances between partial rankings, Inf. Process. Lett., 109, 238-241 (2009) · Zbl 1191.68820 · doi:10.1016/j.ipl.2008.10.010
[20] Moulton, V.; Spillner, A., Optimal algorithms for computing edge weights in planar split networks, J. Appl. Math. Comput., 39, 1-13 (2012) · Zbl 1297.68187 · doi:10.1007/s12190-011-0506-z
[21] Balvočiūtė, M.; Bryant, D.; Spillner, A., When can splits be drawn in the plane?, SIAM J. Discret. Math., 31, 839-856 (2017) · Zbl 1362.92049 · doi:10.1137/15M1040852
[22] Dress, A.; Huson, D., Constructing splits graphs, IEEE/ACM Trans. Comput. Biol. Bioinforma., 1, 109-115 (2004) · doi:10.1109/TCBB.2004.27
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.