SPOTCLUST

Home     Publications      People      Contact us

Probabilistic Framework. Multivariate Bernoulli Mixture Model

We perform unsupervised classification (clustering) of spoligotyping patterns. Clustering (please do not confuse with finding clusters of two isolates with matching genotypes) is a process of grouping the objects in the data by some similarity measure. "Unsupervised" means that we assume no prior knowledge on what family each spoligotype belongs to. All we start with is our data, a collection of spoligotypes.

The clustering methods can be divided into two major categories: discriminative (distance-based methods) and generative (model-based) methods.

Distance-based methods require a metric of pairwise distance between data points. This distance measure is often difficult to define, especially when the data are complex, for example, biological sequences. Model-based clustering techniques, such as mixture models, have the advantages that they do not require the distance metric.

The model-based approach is the most appropriate for spoligotypes, because the distance measure between spoligotypes has not been determined yet. We cannot precisely determine how far is, say, M. tuberculosis Beijing from M. bovis, given their spoligotyping patterns. The belief is that spoligotypes develop by the deletion of spacers, but it is not clear in what order and how many spacers can be lost simultaneously; therefore, the distance can be probabilistically assessed as a probability of a "child" spoligotype having been evolved from a "parent" spoligotype by mostly losing but not gaining spacers.

We assume that a multivariate Bernoulli mixture model (MBMM) generates the data and that there is a one-to-one correspondence between mixture model components and spoligotype families. Each model component satisfies the Naïve Bayes assumption. Naïve Bayes assumption allows treating all the features (in our case, a feature is a presence/absence of a spacer - 1 or 0) as independent of each other given the class.

Bernoulli distribution has only one parameter, p, the probability of success (spacer in our case) in a trial with two possible outcomes. The probability of the absence of a spacer is (1-p). Thus each position in a spoligotype can be modeled as a Bernoulli distribution. There are 43 positions; therefore, multivariate Bernoulli distribution (naturally, with 43 parameters, each of which is a probability of a spacer) is used. Finally, we know that there are families within the spoligotyping data; therefore, some number of different multivariate Bernoulli distributions, each corresponding to a family, should model the data. Thus we have a mixture of components each corresponding to a distribution.

Now let us formalize our probabilistic framework.

Let $X = \{{\bf x}_1,\cdots,{\bf x}_{n}\}$ be a set of spoligotypes that we want to classify. Each spoligotype is a binary 43-dimensional vector: ${\bf x} = \{x_1,\cdots,x_{43}\}$. Let $C$ be a mixture model, which consists of $k$ components: $C = \{c_1,\cdots,c_k\}$. Each mixture component $c_j \in C$ is described by parameters $\theta_j$, that are mixing weight of the component, $P(c_j)$, and 43 Bernoulli distributions. The mixing weights satisfy the constrains:

$$\sum_{j=1}^{k}P(c_j) = 1 P(c_j) \geq 0.$$ (1)

The probability of a spoligotype ${\bf x}$ being generated by $C$ is

$$P({\bf x})= \sum_{j=1}^{k}P(c_j)P({\bf x}\vert c_j, \theta_j).$$ (2)

Thus, to generate a spoligotype, first a mixture component is chosen with a probability $P(c_j)$, then its parameters are used to produce a spoligotype sequence. Let us denote each spacer of ${\bf x}$ as $S_{d}$ (either 0 or 1). Then each mixture component $c_j$ has $43$ parameters $p_{jd}$, where $p_jd$ is a probability of a spacer being present and $(1-p_{jd})$ is a probability of a spacer being absent at a position $d$ of ${\bf x}$. The probability of a spoligotype ${\bf x}$ given component $c_j$ is:

$$P({\bf x}\vert c_j, \theta_j)= \prod_{d=1}^{43}S_{d}P(p_{jd}\vert c_j,\theta_j) + (1 - S_{d})(1 - P(p_{jd}\vert c_j,\theta_j)).$$ (3)

Given the Naïve Bayes assumption, the probability that component $c_j$ has generated spoligotype ${\bf x}$ is given as follows:

$$P(c_j\vert{\bf x})= \frac{P(c_j)\prod_{d=1}^{43}p_{jd}^{S_{id}}(1... ...{\sum_{l = 1}^{k} P(c_l)\prod_{d=1}^{43} p_{ld}^{S_{id}}(1-p_{ld})^{1-S_{id}} }$$ (4)

for $i \in \{ 1,\cdots, n\}$, $j \in \{ 1,\cdots, k\}$.

The parameters for finite mixture models are often estimated by the maximum likelihood (ML) approach. Expectation-maximization (EM) is the most commonly used algorithm for finding a local maximum of the likelihood of the observed data.