Microbiome analysis [1] by sequencing of ubiquitous genes, most commonly 16S rRNA, had become a standard, cost-effective way to characterize the composition of a microbial sample. Standard analysis tools facilitate quantifying the fraction of sequence reads from each bacterial species in a sample [2]. Interpretation of composition vectors across a collection of samples typically relies on dimensionality reduction followed by clustering in the lowerdimensionality space [3]. This allows identification of functionallymeaningful subsets of samples with characteristic microbiota. The Human Microbiome Project [4] and derivatives such as The Human Vaginal Microbiome Project [5] have collected and thus analyzed large numbers of samples towards elucidating the structure and composition of microbiota across physiological and pathological states.
Similar to variation in microbial genomes across different human individuals, variants along the nuclear genomes have been summarized by a small number of dimensions [6]. However, in contrast to analyses of microbiome samples, those of inherited genetic variation standardly assume and observe samples to be spread across a continuum in the reduced space, rather than be clustered [7]. Samples in between clusters are interpreted as originating from intermediate locales along a geographic cline [8], or as representing different levels of a mixture between clusterspecific populations.
In this paper, we formally tackle the problem of clustering while allowing elements to belong to two clusters. Specifically, we will describe in detail a model for clustering in R d . We construct model that generalizes k-means clustering by allowing data points to be assigned to a point in the space along the line between two assigned clusters [9]. Each cluster is still modeled as a Gaussian with uniform, spherical covariances, the key difference is the presence of a parameter u ∈ [0, 1] for each 2-way-assigned data point xi, which determines the proportional assignment of xi between its two cluster representatives. We first describe the 2-way model's inputs, parameters, and outputs. We will then give the objective function, an algorithmic description, and a series of performance metrics. Then, we will evaluate the performance on simulated data, describing benchmarks for optimal performance. Finally, we apply it to real data of 16S rDNA sequencing from 1500 mid-vaginal bacterial samples by the Vaginal Human Microbiome Project.
The model characterizes a mixture where points are each sampled either from a k-mixture of uniform, spherical gaussian distributions, or from pairwise weighted averages of these Gaussians.
Formally, we describe a generative model for a set X of data points
The model involves k ∈ Z + clusters. The j-th cluster is parametrized by its mean µ j ∈ R d . To draw x i the model first chooses a pair of cluster indices j, j along with a weighting u i ∈ [0, 1]. x i is drawn from a Gaussian distribution whose parameters are u i -weighted averages of two representative clusters. Specifically, x i ∼ N (x i ; μijj , Σ) such that μijj = u i µ j + (1u i )µ j and Σ ∈ R d×d is the given uniform, spherical covariance matrix.
The inference problem involves the inputs of data X and number of clusters k, seeking output of the generative model parameters, i.e. the vectors of assignments C = (c 1 , . . . , cn) and weights U = (u 1 , . . . , un).
Given input x 1 ...xn ∈ R d and cardinality k ∈ N, k-means traditionally provides us with the following objective:
where c 1 ...c j are the cluster representatives. The k-means objective can be generalized as the following: A common generalization of k-means is to permit each φ i to have s nonzero entries (in our case, we set s = 2). An algorithm for this generalized objective is simply to hold C fixed while performing sparse regression on Φ, then hold Φ fixed and use Ordinary Least Squares (OLS) to find C.
In our case, because we only allow points x i to lie in uniformly between two cluster representatives, the two non-zero entries in a given φ i are restricted to some u i ∈ [0, 1] and 1u i ∈ [0, 1]. Our problem is instead the following: c Oxford University Press 2017.
notice that the samples with abundant Sneathia1, P revotella2, and U nclassif ied types are predominantly contained in c31. c32 contains samples with a variety of abundant OTUs. Lactobacillus3, Lactobacillus4, P revotella1, Streptococcus1, Streptococcus2, and Bif odobacterium are abundant in samples that are predominantly contained in c34. Finally, almost no samples are in cluster pair c35, aside from a few Sneathia1 types. In this way, 2-way k-means also opens up a wealth of information on the relationships between samples. In particular, it now makes more sense to characterize the samples as being in 6 different clusters: c1, c2, c31, c34, c5. We also see that certain clusters have