betaFeedback

WorksMathematics

Distributions of metric nn-point invariants and applications to molecular evolution

Abstract

Datasets often arise as samples from a metric measure space whose geometry reflects the data-generating process. We introduce metric nn-point invariants, defined as functions of the pairwise distances of nn-point configurations, to study the geometry of such spaces. This provides a unified framework for existing concepts, such as the pairwise distance itself, the Gromov product, and Vietoris-Rips persistence diagrams. The distribution of a metric nn-point invariant FF over random nn-point configurations can be used to extract geometric information from the space and is obtained as the pushforward of Gromov's nn-th curvature measure μnμ_n along FF. Our main result is an explicit bound for the expected pp-Wasserstein distance between μnμ_n and the empirical curvature measure μ^n\hatμ_{n} of finitely many sampled nn-point configurations, and carries over to the associated distributions of Lipschitz metric nn-point invariants. From this we derive the sample size needed to achieve a prescribed accuracy and level of confidence in the approximation of the curvature measure. As an application, we use metric nn-point invariants to study molecular evolution. We describe how site-wise nucleotide frequencies shape the corresponding distributions in Jukes-Cantor and Halpern-Bruno substitution models, and analyse five million SARS-CoV-2 genomes, revealing increasingly common failures of the four-point condition, constrained nucleotide accessibility consistent with the biased mutation spectrum, and rare cycles in persistent homology reflecting recurrent mutations across lineages. These findings demonstrate the potential of our sampling-based approach to the geometry of data as a scalable, phylogeny-free tool for detecting and quantifying evolutionary structure in large genomic datasets.

Introduction

Let (X,dX,μX)(X,d_X,\mu_X) be a bounded metric measure space (mm-space), meaning that (X,dX)(X,d_X) is a Polish space of finite diameter diam⁡(X)\operatorname{diam}(X) and μX\mu_X is a Borel probability measure on XX, not necessarily fully supported. Many classical summaries of the geometry of XX are obtained by evaluating the distances between pairs, triples, or nn-tuples of points and then taking an average or an extremum. Instead of reducing these values to a single number, one can retain their full distribution over random configurations drawn from μX\mu_X. This distributional viewpoint is particularly natural when XX is accessible only through samples, either because XX itself is unknown or because it is too large to compute all pairwise distances, as is increasingly the case for modern datasets.

To treat all quantities that depend only on the distances among nn points in a unified way, we follow Gromov [31] and assign to an nn-tuple x=(x1,…,xn)\mathbf{x}=(x_1,\ldots,x_n) its distance matrix:

Ψn:Xn⟶Rn×n,Ψn(x)ij≔dX(xi,xj).\Psi_n:X^n\longrightarrow\mathbb{R}^{n\times n},\qquad\Psi_n(\mathbf{x})_{ij}\coloneqq d_X(x_i,x_j).

2020 Mathematics Subject Classification. Primary 60B10; Secondary 53C23, 62R20, 92D15.

Keywords. Metric measure spaces, curvature measures, Wasserstein distance, empirical measures, hyperbolicity, molecular evolution. The image of this map, Kn(X):=Ψn(Xn)\mathrm{K}_n(X) := \Psi_n(X^n), is known as the nn-th curvature set (Subsection 3.1), and the pushforward

μn:=(Ψn)#μX⊗n\mu_n := (\Psi_n)_{\#}\mu_X^{\otimes n}

is called the nn-th curvature measure. The measure μn\mu_n records the geometry of XX as seen by random nn-point configurations in XX. The full family (μn)n≥2(\mu_n)_{n \ge2} determines the mm-space up to the natural measure-preserving notion of isometry by the Gromov–Vershik reconstruction theorem [31 Sec. 3.5 & 3.7]; see also [62 Cor. 5].

Write Kn⊂Rn×n\mathrm{K}_n \subset\mathbb{R}^{n \times n} for the set of all distance matrices on nn points, also known as the nn-th metric cone. We define a metric nn-point invariant with values in a Polish space ZZ, or nn-invariant for short (§ 4), to be a measurable function

F:Kn→Z.F:\mathrm{K}_n \to Z.

In other words, an nn-invariant maps the pairwise distances among nn points to a value in ZZ. Examples include the pairwise distance, the area of a triangle, the four-point hyperbolicity deficit, and the persistence diagram of nn points, each capturing a particular geometric property of an nn-point configuration.

The distribution of FF over random nn-tuples of XX is the probability measure on ZZ given by the pushforward of the curvature measure of XX,

νF:=F#μn.\nu_F := F_{\#}\mu_n.

Throughout, we suppress the dependence of μn\mu_n and νF\nu_F on the mm-space (X,dX,μX)(X,d_X,\mu_X) whenever it is clear from context and record it in the subscript otherwise, as in μn,X\mu_{n,X}, νF,X\nu_{F,X}, or νF,μ\nu_{F,\mu}.

In data analysis, the geometry of XX is expected to carry information about the data-generating process and is often studied through the distributions of nn-invariants and their statistical summaries, such as the mean, median, or quantiles. Each νF\nu_F is simpler and often more tractable than μn\mu_n, but describes only one aspect of the geometry of nn-point configurations. In this article, we provide sample sizes that guarantee the approximation of μn\mu_n itself from samples of nn-tuples and show that they carry over to distributions of all Lipschitz nn-invariants, including those with high- or infinite-dimensional target spaces, such as persistence diagrams. Given independent samples x(1),…,x(N)∼μX⊗n\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)} \sim\mu_X^{\otimes n}, denote the empirical curvature measure by

μ^n,N:=1N∑i=1NδΨn(x(i)),\widehat{\mu}_{n,N} := \frac{1}{N}\sum_{i=1}^{N}\delta_{\Psi_n(\mathbf{x}^{(i)})},

where we write δy\delta_y for the Dirac measure at a point yy. For every nn-invariant FF, the same sample then yields ν^F,N:=F#μ^n,N\widehat{\nu}_{F,N} := F_{\#}\widehat{\mu}_{n,N}, the empirical distribution of the values of FF on the sampled nn-tuples.

Uniform approximation of the geometry of nn-point configurations. Our main result is an explicit bound for the expected pp-Wasserstein distance WpW_p between the empirical curvature measure μ^n,N\widehat{\mu}_{n,N} and the true curvature measure μn\mu_n. It is obtained by applying the Euclidean empirical-measure convergence rates of Fournier and Guillin [25], with the explicit constants due to Fournier [26], to μn\mu_n regarded as a measure on Rd\mathbb{R}^d.

Theorem A. Fix 1≤p<∞1 \le p < \infty and n≥2n \ge2, set d:=(n2)d := \binom{n}{2}, and suppose that p≠d/2p \ne d/2. Let (X,dX,μX)(X,d_X,\mu_X) be a bounded mm-space with fully supported probability measure. Then the expected pp-Wasserstein distance between the empirical curvature measure μ^n,N\widehat{\mu}_{n,N} and the true curvature measure μn\mu_n satisfies

E[Wp(μ^n,N,μn)p]≤C(d,p)diam⁡(X)pN−ed,p,ed,p:={1/2,p>d/2,p/d,p<d/2,\mathbb{E}\left[W_p(\widehat{\mu}_{n,N},\mu_n)^p\right] \le C(d,p)\operatorname{diam}(X)^p N^{-e_{d,p}}, \qquad e_{d,p}:= \begin{cases} 1/2, & p>d/2,\\ p/d, & p<d/2, \end{cases}

where C(d,p):=2d/2−11−2d/2−pC(d,p):=\frac{2^{d/2-1}}{1-2^{d/2-p}} if d<2pd<2p and C(d,p):=2p−2p/d(1−2−d/2)1−2p/d1−2p−d/2C(d,p):=\frac{2^{p-2p/d}(1-2^{-d/2})^{1-2p/d}}{1-2^{p-d/2}} if d>2pd>2p.

Corollary B. Under the assumptions of Theorem A, let F:Kn→ZF:\mathbf{K}_n\to Z be a Lipschitz metric nn-point invariant. Then

E[Wp(ν^F,N,νF)p]≤C(d,p)Lip⁡(F)pdiam⁡(X)pN−ed,p.\mathbb{E}\left[\mathsf{W}_p(\hat{\nu}_{F,N},\nu_F)^p\right]\leq C(d,p)\operatorname{Lip}(F)^p\operatorname{diam}(X)^pN^{-e_{d,p}}.

Corollary C. Choose an error margin ϵ>0\epsilon>0 and a confidence level 0<α<10<\alpha<1. Under the assumptions of Theorem A, there is an explicit N∗=N∗(n,p,ϵ,α)N_* = N_*(n,p,\epsilon,\alpha) such that, for every N>N∗N>N_*, with probability at least α\alpha,

Wp(μ^n,N,μn)≤ϵdiam⁡(X)W_p(\hat{\mu}_{n,N},\mu_n)\leq\epsilon\operatorname{diam}(X)

and, uniformly over all Lipschitz metric nn-point invariants F:Kn→ZF:\mathbf{K}_n\to Z,

Wp(ν^F,N,νF)≤ϵLip⁡(F)diam⁡(X).\mathsf{W}_p(\hat{\nu}_{F,N},\nu_F)\leq\epsilon\operatorname{Lip}(F)\operatorname{diam}(X).

These results are proved in § 6 as Theorem 6.1 and Corollaries 6.2 and 6.3. The first corollary is just the pushforward along a Lipschitz function, while the second relies on a standard bounded-differences concentration argument and McDiarmid’s inequality [64].

Approximating the full nn-th curvature measure guarantees that the results in Corollaries B and C hold uniformly over all Lipschitz nn-invariants F:Kn→ZF:\mathbf{K}_n\to Z. In the analysis of a concrete dataset, this allows us to determine the number N∗N_* of required nn-tuples for a prescribed accuracy and confidence in advance,1 and every subsequent analysis of the geometry of nn-point configurations of XX based on a single sample of this size inherits the guarantee without further sampling or corrections for multiple comparisons. This universality comes at a cost, as the convergence rates are governed by the rapidly growing dimension of the ambient Euclidean space that contains Kn\mathbf{K}_n. For a single nn-invariant with a low-dimensional target, applying the same techniques to νF\nu_F directly can substantially improve the convergence rate. For example, for a real-valued nn-invariant F:Kn→RF:\mathbf{K}_n\to\mathbb{R}, these techniques yield the rate N−1/2N^{-1/2} (cf. Proposition 6.6), in line with classical results, e.g. [7 Thm. 7.9]. However, if ZZ is high- or infinite-dimensional, as for persistence diagrams, such bounds may be poor or unavailable, and passing through μn\mu_n is the natural route to explicit rates.

The ambient dimension d=(n2)d=\binom{n}{2} of Kn⊂Rd\mathbf{K}_n\subset\mathbb{R}^d is often suboptimal since the curvature set Kn(X)\mathbf{K}_n(X) in question may have much smaller intrinsic dimension. Convergence rates for empirical measures in terms of intrinsic dimension go back to Dudley [22] and have since been further developed using covering dimensions of sets of full or almost full measure [8, 64, 16]. We obtain the following refinement for Ahlfors ss-regular spaces from bounds based on an intrinsic Wasserstein-dimension of measures due to Weed and Bach [64].

References

  1. [1][BBI01] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.DOI
  2. [3][BGMP14] Andrew J. Blumberg, Itamar Gal, Michael A. Mandell, and Matthew Pancia. Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces. Foundations of Computational Mathematics, 14(4):745–789, 2014.
  3. [5][Bil95] Patrick Billingsley. Probability and Measure. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York, third edition, 1995.
  4. [6][BK04] Mireille Boutin and Gregor Kemper. On reconstructing n-point configurations from the distribution of distances or areas. Advances in Applied Mathematics, 32(4):709–735, 2004.
  5. [7][BL19] Sergey Bobkov and Michel Ledoux. One-dimensional empirical measures, order statistics, and Kantorovich transport distances. Memoirs of the American Mathematical Society, 261(1259), 2019.DOI
  6. [8][BLG14] Emmanuel Boissard and Thibaut Le Gouic. On the mean speed of convergence of empirical and occupation measures in Wasserstein distance. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 50(2):539–563, 2014.arxiv.org/abs/1105.5263
  7. [9][BRR10] Rabi N. Bhattacharya and R. Ranga Rao. Normal Approximation and Asymptotic Expansions, volume 64 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, 2010.
  8. [10][Bun74] Peter Buneman. A note on the metric properties of trees. Journal of Combinatorial Theory, Series B, 17(1):48–50, 1974.DOI
  9. [11]Joseph Minhow Chan, Gunnar Carlsson, and Raul Rabadan. Topology of viral evolution. Proceedings of the National Academy of Sciences, 110(46):18566–18571, 2013.DOI
  10. [12]Frédéric Chazal, David Cohen-Steiner, Leonidas J. Guibas, Facundo Mémoli, and Steve Y. Oudot. Gromov–Hausdorff stable signatures for shapes using persistence. Computer Graphics Forum, 28(5):1393–1403, 2009.DOI
  11. [14]Sourav Chatterjee and Leila Sloman. Average Gromov hyperbolicity and the Parisi ansatz. Adv. Math., 376:107417, 2021.arxiv.org/abs/1907.03203
  12. [15]Robert Deltheil. Probabilités Géométriques, volume 2 of Traité du Calcul des Probabilités et de ses Applications. Gauthier-Villars, Paris, 1926.
  13. [16]Jérôme Dedecker, Aurélie Fischer, and Bertrand Michel. Concentration of the empirical measure in Wasserstein distance: bounds involving the covering dimension, 2026. Preprint: arXiv:2601.11133.
  14. [17]Andreas Dress, Katharina T. Huber, Jacobus Koolen, Vincent Moulton, and Andreas Spillner. An algorithm for computing cutpoints in finite metric spaces. Journal of Classification, 27(2):158–172, 2010.arxiv.org/abs/0910.2317
  15. [18]Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics, volume 15 of Algorithms and Combinatorics. Springer, Berlin, 1997.
  16. [19]Nicola De Maio, Conor R. Walker, Yatish Turakhia, Robert Lanfear, Russell Corbett-Detig, and Nick Goldman. Mutation rates and selection on synonymous mutations in SARS-CoV-2. Genome Biology and Evolution, 13(5):evab087, 2021.DOI
  17. [20]H. A. David and H. N. Nagaraja. Order Statistics. Wiley Series in Probability and Statistics. John Wiley & Sons, Hoboken, NJ, third edition, 2003.
  18. [21]Andreas W. M. 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(3):321–402, 1984.DOI
  19. [22]R. M. Dudley. The Speed of Mean Glivenko-Cantelli Convergence. The Annals of Mathematical Statistics, 40(1):40 – 50, 1969.DOI
  20. [23]Stefan Elbe and Gemma Buckland-Merrett. Data, disease and diplomacy: GISAID’s innovative contribution to global health. Global Challenges, 1(1):33–46, 2017.DOI
  21. [24]Cassidy Eastwood, Anna M. Ellison, Mario Gómez, and Facundo Mémoli. Homology groups of the curvature sets of S¹, 2023. Preprint: arXiv:2209.04674.arxiv.org/abs/2209.04674
  22. [25]Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3):707–738, 2015.arxiv.org/abs/1312.2128
  23. [26]Nicolas Fournier. Convergence of the empirical measure in expected Wasserstein distance: non-asymptotic explicit bounds in ℝᵈ. ESAIM: Probability and Statistics, 27:749–775, 2023.DOI
  24. [27]Russell D. Gray, David Bryant, and Simon J. Greenhill. On the shape and fabric of human history. Philosophical Transactions of the Royal Society B: Biological Sciences, 365(1559):3923–3933, 2010.DOI
  25. [28]Piotr Gwiazda, Alexey Kazarnikov, Anna Marciniak-Czochra, and Zuzanna Szymańska. Beyond Bayesian inference: the correlation integral likelihood framework and gradient flow methods for deterministic sampling. Bull. Math. Biol., 88:11, 2026.arxiv.org/abs/2512.03122
  26. [29]Mario Gómez and Facundo Mémoli. Curvature sets over persistence diagrams. Discrete Comput. Geom., 72(1):91–180, 2024.arxiv.org/abs/2103.04470
  27. [30]Mikhail Gromov. Hyperbolic groups. In Steve M. Gersten, editor, Essays in Group Theory, volume 8 of Mathematical Sciences Research Institute Publications, pages 75–263. Springer, New York, 1987.DOI
  28. [31]Mikhail Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston, 2007.DOI
  29. [32]J. M. Hammersley. The distribution of distance in a hypersphere. Ann. Math. Statist., 21(3):447–452, 1950.DOI
  30. [33]Richard W. Hamming. Error detecting and error correcting codes. Bell System Technical Journal, 29(2):147–160, 1950.DOI
  31. [34]Aaron L. Halpern and William J. Bruno. Evolutionary distances for protein-coding sequences: modeling site-specific residue frequencies. Molecular Biology and Evolution, 15(7):910–917, 1998.pubmed.ncbi.nlm.nih.gov/9656490
  32. [35]Juha Heinonen. Lectures on Analysis on Metric Spaces. Universitext. Springer-Verlag, New York, 2001.DOI
  33. [36]Barbara R. Holland, Katharina T. Huber, Andreas Dress, and Vincent Moulton. δ plots: a tool for analyzing phylogenetic distance data. Molecular Biology and Evolution, 19(12):2051–2059, 2002.
  34. [37]Richard R. Hudson and Norman L. Kaplan. Statistical properties of the number of recombination events in the history of a sample of DNA sequences. Genetics, 111(1):147–164, 1985.
  35. [38]Frank Harary and Geert Prins. The block-cutpoint-tree of a graph. Publ. Math. Debrecen, 13(1–4):103–107, 1966.
  36. [39]John Rolfe Isbell. Six theorems about injective metric spaces. Comment. Math. Helv., 39(1):65–76, 1964.DOI
  37. [40]Thomas H. Jukes and Charles R. Cantor. Evolution of protein molecules. In H. N. Munro, editor, Mammalian Protein Metabolism, volume 3, pages 21–132. Academic Press, New York, 1969.DOI
  38. [41]Martina Jørgensen and Urs Lang. A combinatorial higher-rank hyperbolicity condition. Comment. Math. Helv., 99(3):613–639, 2024.arxiv.org/abs/2206.08153
  39. [42]K. Katoh. MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Research, 30(14):3059–3066, 2002.
  40. [43]Urs Lang. Injective hulls of certain discrete metric spaces and groups. J. Topol. Anal., 5(3):297–331, 2013.
  41. [44]Michael Lesnick, Raúl Rabadan, and Daniel I. S. Rosenbloom. Quantifying genetic innovation: mathematical foundations for the topological study of reticulate evolution. SIAM Journal on Applied Algebra and Geometry, 4(1):141–184, 2020.arxiv.org/abs/1804.01398
  42. [45]Pertti Mattila. Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1995.DOI
  43. [46]Benoit Morel, Pierre Barbera, Lucas Czech, Ben Bettisworth, Lukas Hübner, Sarah Lutteropp, Dora Serdari, Evangelia-Georgia Kostaki, Ioannis Mamais, Alexey M. Kozlov, Pavlos Pavlidis, Dimitrios Paraskevis, and Alexandros Stamatakis. Phylogenetic analysis of SARS-CoV-2 data is difficult. Molecular Biology and Evolution, 38(5):1777–1791, 2021.DOI
  44. [47]Facundo Mémoli. Gromov–Wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics, 11(4):417–487, 2011.
  45. [49]Facundo Mémoli and Tom Needham. Distance distributions and inverse problems for metric measure spaces. Stud. Appl. Math., 149(4):943–1001, 2022.arxiv.org/abs/1810.09646
  46. [50]Facundo Mémoli, Osman Berat Okutan, and Qingsong Wang. Metric graph approximations of geodesic spaces, 2021. Preprint: arXiv:1809.05566v3.arxiv.org/abs/1809.05566
  47. [52]Masatoshi Nei and Wen-Hsiung Li. Mathematical model for studying genetic variation in terms of restriction endonucleases. Proceedings of the National Academy of Sciences, 76(10):5269–5273, 1979.pubmed.ncbi.nlm.nih.gov/291943
  48. [53]Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. Shape distributions. ACM Transactions on Graphics, 21(4):807–832, 2002.DOI
  49. [54]Alan R. Rogers and Henry Harpending. Population growth makes waves in the distribution of pairwise genetic differences. Molecular Biology and Evolution, 9(3):552–569, 1992.pubmed.ncbi.nlm.nih.gov/1316531
  50. [55]Brian D. Ripley. Spatial Statistics. Wiley Series in Probability and Statistics. Wiley, 1981.
  51. [56]James C. Robinson. Dimensions, Embeddings, and Attractors. Cambridge Tracts in Mathematics. Cambridge University Press, 2010.DOI
  52. [57]Montgomery Slatkin and Richard R. Hudson. Pairwise comparisons of mitochondrial DNA sequences in stable and exponentially growing populations. Genetics, 129(2):555–562, 1991.pubmed.ncbi.nlm.nih.gov/1743491
  53. [58]Peter Simmonds. Rampant C→U hypermutation in the genomes of SARS-CoV-2 and other coronaviruses: causes and consequences for their short- and long-term evolutionary trajectories. mSphere, 5(3):e00408–20, 2020.
  54. [59]Korbinian Strimmer and Arndt von Haeseler. Likelihood-mapping: a simple method to visualize phylogenetic content of a sequence alignment. Proceedings of the National Academy of Sciences, 94(13):6815–6819, 1997.pubmed.ncbi.nlm.nih.gov/9192648
  55. [60]Yatish Turakhia, Bryan Thornlow, Angie Hinrichs, Jakob McBroome, Nicolas Ayala, Cheng Ye, Kyle Smith, Nicola De Maio, David Haussler, Robert Lanfear, and Russell Corbett-Detig. Pandemic-scale phylogenomics reveals the SARS-CoV-2 recombination landscape. Nature, 609:994–997, 2022.DOI
  56. [61]Lucy van Dorp, Damien Richard, Cedric C. S. Tan, Liam P. Shaw, Mislav Acman, and François Balloux. No evidence for increased transmissibility from recurrent mutations in SARS-CoV-2. Nature Communications, 11:5986, 2020.DOI
  57. [62]A. M. Vershik. Random metric spaces and universality. Russian Math. Surveys, 59(2):259–295, 2004.
  58. [63]Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2009.
  59. [64]Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620–2648, 2019.arxiv.org/abs/1707.00087

Paper details

vlnc:W_asz8qj9e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents