Probabilistic Models for Single Cell Sequencing

Probabilistic Models for Single Cell Sequencing

This page showcases how the paper CopyMix: Mixture Model Based Single-Cell Clustering and Copy Number Profiling using Variational Inference builds of the paper Interactive analysis and assessment of single-cell copy-number variations to create an effective model for sequencing single cell data.

Principal Author: Katherine Breen

Abstract

Single cell sequencing has become a relevant area in cancer research over the last decade however modelling this data in a useful form is difficult. Clustering single cell sequences into smaller sub-populations of cells based on their mutations offers insight in cancer progression, metastasis, therapy resistance and more . Traditionally, to cluster these sequences, models have first identified mutations in cells then clustered them using hierarchical clustering . Newer probabilistic models identify mutations and cluster cells simultaneously . These models have outperformed the traditional cluster models in terms of computational efficiency and V-measure scores . This page showcases how a current probabilistic model, CopyMix, was built to overcome the limitations of a previous state-of-the-art clustering model. Gingko .

Builds on

This article applies Markov Chains and Variational Inference to create a probabilistic model.

Related Pages

There are no UBC wiki pages that reference this page.

Content

Single Cell Sequencing for Cancer Research

Understanding the genetic mutations that cause cancer are key to improving cancer treatments . When genes work properly, cells grow and divide to replace damaged or aging cells. When a gene becomes damaged, the gene can mutate and cause normal cells to divide and grow out of control, leading to cancer . Over the past decade, cell sequencing has improved researchers’ understanding of these mutations .

Cell sequencing is used to observe the genomes of a cell sample. In cancer research, a cell sample is typically a tumour sample . Tumours consist of several cell sub-populations, each with their own genetic properties . Clustering single cell data allows researchers to identify these sub-populations, an important step to understanding cancer progression, therapy resistance and more .

To identify these cell sub-populations, researchers identify the mutations contained in individual cells from a group of cells then cluster the individual cells based on their mutations . The types of mutations are typically referred to as copy numbers . Initially, models were built to complete these tasks sequentially, as in, identify the copy numbers in each single-cell first then cluster the cells . However, these sequential models fall short of best possible performance even if each task has optimal performance . Newer models look to complete these tasks simultaneously and have shown to outperform sequential models .

This article showcases how the newer simultaneous model, named CopyMix, builds off of the sequential model, named Ginkgo. Although these models have cancer based applications, this article will focus on the methods used to build these models and thus give very high-level explanations for the biological application. For further information on single-cell sequencing and cancer cells, additional links have been hyperlinked as well as added to the end of this article.

Gingko: A hierarchical clustering method for single cell sequencing

Overview

Gingko is an open source single-cell sequencing platform based on hierarchical clustering. Before clustering the single-cell data, this model performs a large amount of data processing where outliers are removed. The length of the sequence is also adjusted and accounted for .

Once the data is processed, the model maps the single cell data to the genome. From this mapped genome, the mutations in each sample are observed. Using the mapped genomes and mutation data, the data is then clustered using hierarchical clustering .

To perform clustering a distance matrix containing the distances between all cells is computed. The distance is determined using one of six possible distance metrics: Euclidean, maximum, Manhattan, Canberra, binary and Minkowski. The distance metric is selected by the user. With the distance matrix, Ginkgo then uses agglomerative clustering to group the cells into clusters representing different cell subpopulations . In agglomerative clustering, each sample starts as its own cluster. Each cluster is then merged step-by-step with its nearest cluster until there is only one cluster left. How many merges are made is a hyper-parameter that determines the number of resulting clusters. An example of this is shown in Figure 1. In Figure 1, there are three clusters created in the first step of the clustering. These three clusters are cell #1-#3, cell #4-5, and cell #6. Ginkgo offers four different agglomeration methods: single linkage, complete linkage, average linkage and ward linkage .

Figure 1: Simple example of clustering 6 cells

Figure 1 is a small scale example of Gingko. In a real application, there would be thousands of cells to cluster and the clusters would be determined by the types of mutations in the cells.

Limitations

Ginkgo has been successful at clustering single cell data however it does have limitations. Ginkgo’s initial data processing step removes a large amount of data due to outliers and noise corrections. In one example, this resulted in 80% of the sample cells being removed . Ginkgo also requires the user to determine many hyper-parameters such as bin size, distance metric and agglomerative clustering type . Furthermore, once the clustering is performed, the number of clusters must be decided based on the tree . While selecting hyper-parameters and tree depth gives flexibility, it can also be computationally expensive and time consuming. This takes away time from the goal of this research: analyzing the subpopulations of tumours.

Ginkgo is also limited by dataset size and computational run time. Gingko is offered as an online application and was not able to run when tested with a larger dataset of 891 cells . Ginkgo takes a few hours to cluster just 90 cells . Most single-cell datasets are much larger, containing up to thousands of cells, a size which Ginkgo would not be able to handle.

CopyMix: A probabilistic model for single cell sequencing

Overview

Given the limitations of Ginkgo, a probabilistic model based solution to clustering single-cell data, called CopyMix, was proposed. CopyMix requires less hyper parameter tuning and is able to handle larger datasets . CopyMix identifies mutations in cells and clusters cell sub-populations simultaneously using a mixture model with components corresponding to the different cell subpopulations .

The probabilistic framework of CopyMix is advantageous due to its transparency, uncertainty measurements and modeling flexibility. CopyMix models each cluster as a sequence of latent variables and assumes this sequence is governed by a Markov Chain . Markov Chains are effective models of human genomes because the next state depends only on the current state in the sequence. This is an effective way to model the human genome because the human genome is made up of a sequence of nucleic acids represented by the letters A, G, C, and T, this is shown in Figure 2 . For Markov Chains each state is the current position in the sequence. As a result, each sample of the single cell data is modelled as a sequence where the next part depends on the current part.

Figure 2: Simplified human genome example, taken from the National Human Genome Research Institute

CopyMix

CopyMix’s graphical model contains observable variables denoted by $Y$ (the single cell data), the latent copy number states which form a Markov chain denoted by $C$ (the different mutations), and the latent cell-specific cluster assignment variables denoted by $Z$ .

In a single cell dataset, the genomes of a single cell is read multiple times . In CopyMix, each genome considered is partitioned into $M$ equally-sized segments called bins. The number of reads aligned to bin $m$ for cell $n$ is given by $Y_{n}=Y_{n1},...,Y_{n_{M}}$ . $Y1,...,Y_{N}$ are assumed to be independent. The cluster assignment of a cell $n$ is given by the latent variable $Z_{N}$ and there are up to $K$ clusters. All $Z_{N}$ are independent following a categorical distribution with $P(Z_{N}=k)=\pi _{k}$ and $\sum _{k=1}^{K}\pi _{k}=1$. The distribution of $Y_{n}$ depends on the $k^{th}$ vector of the true hidden copy number states, defined as $C_{k}$ with each $C_{k}$ assumed to follow a discrete-time homogeneous Markov chain. Finally $\Psi ={A,\Theta ,\pi }$ is given as the set containing the unknown model parameters where $\pi$ are the priors over $Z_{n}$, $\Theta$ is the cell-specific rate, and $A_{k}$ are the priors over $C_{k}$ . Figure 3, taken from the original paper, is a graphical model of CopyMix .

Figure 3: Graphical model of CopyMix. The shaded nodes are observed variables, unshaded nodes are latent variables and squares are hyper parameters.

Variational inference is used to infer the values of the latent variables $C$ and $Z$ in addition to the unknown model parameters $\Psi$. Variational inference is used because it estimates posterior distributions, protects against overfitting and allows for the selection of optimal number of mixture components, which in this case is the number of cell subpopulations .

Building from Gingko to CopyMix

CopyMix was compared with Ginkgo to cluster the cell data of 891 cells as a benchmark for CopyMix's performance. In the test, Ginkgo removed 80% of the given cells during data processing while CopyMix was able to cluster cells without removing any . Additionally, Ginkgo does not suggest an optimal number of clusters while CopyMix does . The clustering performance measure V-measure score was use to compare the performance of the two models. A higher V-measure means better clustering performance. To achieve the the same V-measure score as CopyMix, Ginkgo required a shallow cutting of its cluster tree . When the threshold for cutting the hierarchical cluster tree was increased slightly, Ginkgo identified four clusters but only achieved a V-measure of 55% compared to CopyMix’s V-measure of 67% .

The probabilistic model CopyMix outperformed the hierarchical clustering model Ginkgo in model performance and run time, however, CopyMix’s model was built from the limitations of the Ginkgo model. Ginkgo was one of the first easily accessible single-cell clustering methods . Once it was published in 2015 its limitations came to light such as computational efficiency, performance and hyper-parameter selection . From these limitations came a proposed solution: a probabilistic model that would increase computational efficiency, performance and limit hyper-parameter selection.

To Add

• Cancer Overview: https://cancer.ca/en/cancer-information/what-is-cancer/how-cancer-starts-grows-and-spreads
• V-Measure Score: https://www.geeksforgeeks.org/ml-v-measure-for-evaluating-clustering-performance/