Chromatic Alpha Complexes

Theory and Applications

Abhinav Natarajan, Thomas Chaplin, Adam Brown, and Maria Jose Jiminez Rodriguez

Motivation from Spatial Biology

Data from patients: tissue slices of adenoma and carcinoma tissue.

Each sample is a record of the positions of different cell types within a tissue slice.

Primarily dealing with epithelial and immune cells.

Our aim: to quantify spatial interactions that correspond with clinical outcomes, and aid in qualitative analysis of tumour-immune microenvironment.

Spatial relationships

How can we quantify spatial relationships in data? Example 1: how do we detect the blue cycle surrounding the orange points? Example 2: How do we quantify that this cycle makes essential use of both orange and blue points?

Funtoriality of Persistent Homology

At each scale there is an inclusion of the blue points into the whole point cloud. At each scale there is an inclusion of the blue points into the whole point cloud. This induces an inclusion of filtrations... This induces an inclusion of filtrations... ... which induces a map on persistent homology. We should expect to see a persistent cycle for the blue points that lies in the kernel of the induced map on persistent homology. If we include orange into orange+blue, we should see a persistent cycle in the cokernel.

More generally, we can study the invariants of these induced maps to quantify the spatial relationships in our data.

Computational challenges

The Čech and Vietoris-Rips filtrations can be huge.

For very large datasets, we run into a wall with computational cost (especially memory).

Alpha complexes

Filtration on a Delaunay triangulation that is much sparser than the Čech filtration … but not functorial with respect to inclusion of subsets of points.

Chromatic alpha complexes

(S. C. di Montesano et. al., 2022).

Given $X \subset \mathbb{R}^d$ and a colouring $\chi :X \to \{ 0, \ldots, s\}$,
the chromatic alpha complex is a filtered geometric simplicial complex $\mathcal{A}_{\bullet}(X, \chi)$.

For $I \subset \{0, \ldots, s\}$, denote $X_I := \chi^{-1}(I)$. Then:

  1. For $I \subset J \subset \{0, \ldots, s\}$, the inclusion $X_I \subset X_J$ induces an inclusion $\mathcal{A}_{\bullet}(X_I, \chi) \hookrightarrow \mathcal{A}_{\bullet}(X_J, \chi)$. We have functoriality with respect to some inclusions of subsets. Chromatic alpha complexes interpolate between the Čech and alpha complexes (both of which are special cases).
  1. There is a filtration-preserving inclusion $\mathcal{A}_{\bullet}(X, \chi) \hookrightarrow \check{C}_{\bullet}(X)$ that is a filtered homotopy equivalence $\implies \mathcal{A}_{\bullet}(X, \chi)$ recovers spatial information.
  2. (Ranita Biswas et. al. 2022) Chromatic alpha complexes have $O(n^{\lceil\frac{d}{2}\rceil})$ cells for random colourings $\implies$ practical in low-dimensions. If $d=2$ then they have at most $O(s^2n)$ cells.

Computing maps of persistence modules

Given a map of persistence modules $f_{\bullet} : A_{\bullet} \to B_{\bullet}$, in general there is no nice algebraic description of $f$ unless $A$ and $B$ have fewer than 4 time steps, or no nested bars (E. Jacquard, 2016).

Algorithms are available to compute $\ker(f), \operatorname{coker}(f)$, and $\operatorname{im}(f)$ (Cohen-Steiner et. al., 2009).

If $f:A \to B$ is induced by some inclusion of complexes $K \hookrightarrow L$, then we can also compute $H_*(L, K)$.

Six packs

Upshot: for each inclusion of subsets of points $\implies$ obtain 6 persistence diagrams in each homological dimension.

Example 1

Example 2

Current pipeline

  • Find the most common cell-type pairs among all the samples
  • Discard samples that do not have at least 3 of these cell-type pairs in them
  • Compute the kernel, domain, and codomain diagrams in degrees 0 and 1
  • Persistent statistics
  • Scaling + PCA
  • Classification (neural nets, random forests) into adenoma/carcinoma
  • Achieve around 82% accuracy, baseline is 65%

Software

Soon to be released software for computational pipeline, including visualisation and statistics.

References

Y. Reani and O. Bobrowski, "A Coupled Alpha Complex" (2021). DOI: 10.48550/arXiv.2105.08113

R. Biswas, S. C. di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian et. al. “On the size of chromatic Delaunay mosaics” (2022). DOI: 10.48550/arXiv.2212.03121

S. C. di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian. “Persistent Homology of Chromatic Alpha Complexes” (2022). DOI: 10.48550/arXiv.2212.03128

D. Cohen-Steiner, H. Edelsbrunner, J. Harer, D. Morozov, “Persistent homology for kernels, images, and cokernels” (2009) in “Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms”, Society for Industrial and Applied Mathematics.

E. Jacquard, V. Nanda, U. Tillmann, “The Space of Barcode Bases for Persistence Modules” (2023) J Appl. and Comput. Topology., 7(1) pp. 1-30.

U. Bauer, H. Edelsbrunner, “The Morse theory of Čech and Delaunay complexes” (2016) Trans. Amer. Math. Soc., 369(5) pp. 3741-3762.

Thank you!