Search Results

Documents authored by Svihla, Sean

Document
DOI: 10.4230/LIPIcs.AofA.2024.4
Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees

Authors: Sean Svihla and Manuel E. Lladser

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Consider a tree T = (V,E) with root ∘ and an edge length function 𝓁:E → ℝ_+. The phylogenetic covariance matrix of T is the matrix C with rows and columns indexed by L, the leaf set of T, with entries C(i,j): = ∑_{e ∈ [i∧ j,o]}𝓁(e), for each i,j ∈ L. Recent work [Gorman & Lladser 2023] has shown that the phylogenetic covariance matrix of a large but random binary tree T is significantly sparsified, with overwhelmingly high probability, under a change-of-basis to the so-called Haar-like wavelets of T. Notably, this finding enables manipulating the spectrum of covariance matrices of large binary trees without the necessity to store them in computer memory but instead performing two post-order traversals of the tree [Gorman & Lladser 2023]. Building on the methods of the aforesaid paper, this manuscript further advances their sparsification result to encompass the broader class of k-regular trees, for any given k ≥ 2. This extension is achieved by refining existing asymptotic formulas for the mean and variance of the internal path length of random k-regular trees, utilizing hypergeometric function properties and identities.
Cite as

Sean Svihla and Manuel E. Lladser. Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{svihla_et_al:LIPIcs.AofA.2024.4,
  author =	{Svihla, Sean and Lladser, Manuel E.},
  title =	{{Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.4},
  URN =		{urn:nbn:de:0030-drops-204399},
  doi =		{10.4230/LIPIcs.AofA.2024.4},
  annote =	{Keywords: cophenetic matrix, Haar-like wavelets, hierarchical data, hypergeometric functions, metagenomics, phylogenetic covariance matrix, sparsification, ultrametric matrix}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact