Essential Simplices in Persistent Homology and Subtle Admixture Detection

Saugata Basu, Filippo Utro, Laxmi ParidaWabi 2018 · DOI

TL;DR

This paper introduces "essential simplices," a novel mathematical concept derived from persistent homology, to pinpoint subtle admixture events in population genetics. By associating these simplices to specific topological features, the method offers a more interpretable and potentially more powerful way to reconstruct population histories than traditional barcode analysis.

What Problem Does This Paper Address?

Understanding the evolutionary history of populations, especially how they have admixed over time, is a fundamental challenge in genetics. While traditional phylogenetic trees represent the history of individuals within a population, the history of populations themselves can be more complex, often represented by directed acyclic graphs (DAGs). Admixture events, where different populations interbreed, leave a distinct imprint on the genetic signatures of individuals. Existing methods using persistent homology can detect the presence of admixture, but disentangling multiple admixture events and their relative timing, especially in complex scenarios, remains difficult. The paper aims to address this by providing a more refined tool to analyze the topological structure of genetic data, specifically to identify and characterize subtle admixture events.

Methods

The core contribution of this paper is the introduction of essential simplices. This concept builds upon persistent homology, a field that studies the "shape" of data by tracking topological features (like holes) across different scales.

Here's a breakdown of their approach:

  • Persistent Homology Basics: They start with a filtered simplicial complex, which is a way to represent data where features are added incrementally. Persistent homology tracks when topological features (homology classes) appear ("birth") and disappear ("death") as the filtration progresses, visualized as "barcodes."
  • The Ambiguity Problem: A key challenge in persistent homology is that a homology class can be represented by many different cycles (linear combinations of simplices). This ambiguity makes it hard to directly link specific topological features to individual data points or events.
  • Essential Simplices: The authors propose a mathematical definition for a unique, non-empty set of "essential simplices" associated with each bar in the persistence barcode. A simplex is considered essential if it must be part of any cycle representing that homology class. This resolves the ambiguity by providing a canonical representation.
  • Admissible Orderings and Filtrations: They utilize specific types of filtrations induced by "admissible orderings" of simplices. This ensures that the resulting persistent homology has certain desirable properties, particularly that each bar in the barcode corresponds to a unique homology class.
  • Rainfall-Like Plot (RFL): They introduce a novel visualization called the Rainfall-Like Plot (RFL). This plot is data-centric, meaning it's associated with individual samples (individuals in this case), unlike traditional barcodes which are structure-centric. The RFL plots the birth and death times of essential simplices for each individual, allowing for a visual clustering that can reveal admixture patterns.

Datasets

The authors used simulated population data generated by a tool called SimRA. They simulated various admixture scenarios, ranging from no admixture to three admixed populations, to test their method. They controlled parameters like mutation rate, recombination rate, and effective population size to create realistic genetic data.

Key Insights and Ideas

  • Resolving Homology Ambiguity: The concept of essential simplices provides a mathematically rigorous way to overcome the inherent ambiguity in representing homology classes, making topological analysis more concrete and interpretable.
  • Data-Centric Visualization: The RFL plot is a significant innovation, shifting the focus from the abstract structure of the homology to the role of individual data points. This makes it easier to see how individuals relate to topological features.
  • Clustering Reveals Admixture: The RFL plots show that individuals from admixed populations tend to cluster together, and these clusters correspond to specific bars in the persistence barcode. This suggests that the clustering of essential simplices directly reflects admixture events.
  • Timing and Number of Admixtures: The authors observed that the number and relative timing of admixture events can be inferred from the RFL plots, particularly by observing the "kinks" or transitions in the plots, and by the ordering of birth points on the RFL.

Key Results

The paper demonstrates through simulations that:

  • The clustering of bars in the persistence barcode, when visualized with essential simplices, captures admixture events in population history.
  • The RFL plots, by associating essential simplices to individuals, can further segregate individuals based on their contribution to these topological features, thereby revealing admixture patterns.
  • The number of admixing events and their relative timing can be deduced from the RFL plots in combination with the bar diagram. For instance, in Figure 4, the RFL plots clearly show distinct clusters corresponding to the number of admixed populations.

Limitations and Future Work

  • Empirical Observation: The paper notes that the ability of 1D bars to cluster and correspond to the number of admixed populations is an "empirical observation" that they are "currently continuing to probe." This suggests that while promising, the theoretical underpinnings for this specific observation might need further development.
  • Computational Complexity: While not explicitly detailed as a limitation, persistent homology computations can be computationally intensive, especially for large datasets. The efficiency of computing essential simplices for very large population genetic datasets would be a practical consideration.
  • Generalizability: The authors believe their notion of essential simplices is general enough for other applications beyond population genetics, hinting at future work in exploring these broader uses.
  • Refining Timing: While the RFL plot shows relative timing, precisely quantifying the time intervals of admixture events might require further refinement of the method or integration with other dating techniques.

Summary updated

BibTeX
@inproceedings{basu2018essential,
  author = {Saugata Basu and Filippo Utro and Laxmi Parida},
  title = {{Essential Simplices in Persistent Homology and Subtle Admixture Detection}},
  booktitle = {Wabi},
  year = {2018},
  doi = {10.4230/lipics.wabi.2018.14},
}
Figure