{'fraction_non_alphanumeric': 0.033970203956968814, 'fraction_numerical': 0.013642379611090372, 'mean_word_length': 4.697602474864656, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning a mixture of microbial networks using minorization–maximization

Abstract Motivation The interactions among the constituent members of a microbial community play a major role in determining the overall behavior of the community and the abundance levels of its members. These interactions can be modeled using a network whose nodes represent microbial taxa and edges represent pairwise interactions. A microbial network is typically constructed from a sample-taxa count matrix that is obtained by sequencing multiple biological samples and identifying taxa counts. From large-scale microbiome studies, it is evident that microbial community compositions and interactions are impacted by environmental and/or host factors. Thus, it is not unreasonable to expect that a sample-taxa matrix generated as part of a large study involving multiple environmental or clinical parameters can be associated with more than one microbial network. However, to our knowledge, microbial network inference methods proposed thus far assume that the sample-taxa matrix is associated with a single network. Results We present a mixture model framework to address the scenario when the sample-taxa matrix is associated with K microbial networks. This count matrix is modeled using a mixture of K Multivariate Poisson Log-Normal distributions and parameters are estimated using a maximum likelihood framework. Our parameter estimation algorithm is based on the minorization–maximization principle combined with gradient ascent and block updates. Synthetic datasets were generated to assess the performance of our approach on absolute count data, compositional data and normalized data. We also addressed the recovery of sparse networks based on an l1-penalty model. Availability and implementation MixMPLN is implemented in R and is freely available at https://github.com/sahatava/MixMPLN. Supplementary information Supplementary data are available at Bioinformatics online.


Introduction
Microbes are found almost everywhere on earth, including in environments deemed too extreme for other life forms, and they play critical roles in many biogeochemical processes (Falkowski et al., 2008;Whitman et al., 1998). Microbial communities are also found in association with higher life forms, including plants and animals; for instance, trillions of microbes live in or on the human body (almost as many human cells as there are in the body) (Sender et al., 2016) and ongoing research continues to reveal the important roles that many of these microbes play in human health (Huttenhower et al., 2012;Qin et al., 2010). Microbial communities are typically structured and composed of members of different species. The microbes in a community do not exist in isolation, but interact with each other and also compete for the available carbon and energy sources. These interactions, along with resource availability and environmental parameters (like temperature, pH and salinity) (Hibbing et al., 2010;Williamson and Yooseph, 2012), determine the taxonomic composition of the microbial community and the abundance levels of its constituents. Knowledge of these interactions is crucial for understanding the overall behavior of the microbial community, and can be used to elucidate the biological mechanisms underlying microbe-associated disease progression and microbemediated processes (like biofilm formation).
The study of microbial communities has been greatly enabled with the advent of high-throughput next-generation DNA sequencing technologies (Bentley, 2006;Margulies et al., 2005;Quail et al., 2012). The taxonomic composition of a microbial community can be obtained by sequencing the DNA extracted from a biological sample that has been collected from the environment of interest. This is achieved either using a targeted approach, involving the sequencing of a taxonomic marker gene [for instance, the 16S ribosomal RNA gene, which is found in all bacteria (Woese and Fox, 1977)] or using a whole-genome shotgun sequencing approach (Venter et al., 2004). Both approaches generate taxa counts that are compositional in nature, and that enable the estimation of the relative abundances of the constituent members of the community.
Microbial interactions can be modeled using a weighted graph (or network), where each node in the graph represents a taxon (or taxonomic group) and an (undirected) edge exists between two nodes if the corresponding taxa interact with, or influence, each other. The edge weight captures the strength of the interaction, with its sign reflecting whether the interaction is positive or negative. This framework can be used to model a variety of microbial interactions, including competition and co-operation. While we do not consider it here, a directed graph can also be used to represent interactions, where the edge direction indicates the direction of influence (or causality).
Microbial networks are typically constructed from sample-taxa count matrices. A sample-taxa count matrix is generated by sequencing multiple biological samples (n samples) collected from the environment of interest and identifying the counts of the observed taxa (d taxa) in each sample.
As we discuss briefly below, microbial networks can be constructed using a variety of different approaches. To our knowledge, all of these methods assume that the sample-taxa matrix is associated with a single underlying stochastic process (i.e. there is one underlying network topology and set of edge weights). However, this need not always be the case. In this paper, we consider an important extension to the network inference problem, whereby we develop a mixture modeling framework for inferring K microbial networks when the observed sample-taxa matrix is associated with K underlying distributions. We are motivated by large-scale humanassociated and other environmental microbial community projects that are now possible due to cost-effective sequencing. For instance, human gut microbiome studies now routinely analyze large cohorts of individuals and generate microbial community data from several hundreds (to even thousands) of samples. An important research question in this area involves the definition of a 'core' microbiome associated with a particular host phenotype (Huttenhower et al., 2012;Qin et al., 2010). It is well understood that the gut microbiome composition is greatly influenced by many factors including diet and age, and thus it is not unreasonable to expect the associated microbial network interactions to also be different when these factors vary (e.g. the gut microbial community interaction network in vegetarian hosts can be expected to be different compared to the network in non-vegetarian hosts). A similar situation also occurs in environmental studies where the microbial interactions are influenced greatly by the physical and chemical gradients of the environment. Often the collected metadata in these studies may not be comprehensive enough to discern these interactions in a supervised manner. Our proposed mixture framework offers a principled approach to identifying these multiple microbial interaction networks from a sample-taxa matrix.
Several methods have been proposed for constructing a single microbial network from an input sample-taxa matrix (Layeghifard et al., 2017). One approach involves using pairwise correlations (Pearson or Spearman) between taxa to define the edge weights in the graph. However, the computation of these correlation networks directly from the observed count data can be misleading because of the compositional nature of these data (Gloor et al., 2017). Furthermore, for a microbial network with d nodes, while there are d Ã ðd À 1Þ=2 edge weights that need to be determined, the number of available samples n is often not large enough, with the result that the system of equations to determine all pairs of correlations is under-determined. This later issue is typically handled by assuming that the network is sparse [i.e. the number of edges is O(d)]. Methods based on latent variable modeling have been proposed to infer correlation networks (Fang et al., 2015;Friedman and Alm, 2012). These methods use logratio transformations of the original count data (Aitchison, 1982) to deal with the compositional nature of these data and subsequently infer the correlation matrix (i.e. edge weights) under the assumption of sparsity. Microbial networks have also been constructed using a probabilistic graphical model framework (Jordan, 1999) that enables the modeling of conditional dependencies associated with the interactions. For instance, the assumption that the log-ratio transformed count data follow a Gaussian distribution, results in a Gaussian graphical model (GGM) framework. In this scenario, the graph structure represents the precision matrix (or inverse covariance matrix) of the underlying multivariate Gaussian distribution. This graph has the property that an edge exists between two nodes iff the corresponding entry in the precision matrix is non-zero. A zero entry in the precision matrix indicates conditional independence between the two corresponding random variables. When the graph is assumed to be sparse, the GGM inference problem can be solved using sparse precision matrix estimation algorithms (Friedman et al., 2008). This approach has been used to construct microbial networks from sample-taxa matrices (Kurtz et al., 2015).
An alternate approach to constructing a microbial network, and that which we adopt in this paper, is to model the vector of observed taxa counts (in samples) using a multivariate distribution and to infer the parameters of this distribution from the observed data using a maximum likelihood framework. Any candidate multivariate distribution for this approach will have to be flexible enough to capture the underlying covariance structure to model the network interactions (i.e. allow for both positive and negative covariances); this rules out distributions like the multinomial or the Dirichlet-Multinomial, which are popular choices for modeling microbial count data in certain situations (Holmes et al., 2012;La Rosa et al., 2012), but which cannot capture both types of interactions. The Multivariate Poisson Log-Normal (MPLN) distribution (Aitchison and Ho, 1989) can be used for modeling multivariate count data and its covariance structure can capture both positive and negative interactions. This distribution was used recently (Biswas et al., 2015) to model counts in a sample-taxa matrix and infer an underlying microbial network using an assumption of sparsity.
In this paper, we consider the following computational inference problem: for a sample-taxa matrix X (containing absolute counts of taxa) that is generated by a mixture model consisting of K MPLN component distributions, estimate the mixing coefficients and the distribution parameters of the K components. We note that the precision matrices of the K components define the K different microbial networks. We formulate this inference problem using a maximum likelihood framework, and estimate the various parameters of the constructed likelihood function directly using a numerical optimization method based on the minorization-maximization (MM) principle (Lange, 2016;Wu et al., 2010;Zhou and Lange, 2010). We extend this formulation based on an l 1 -penalty model and provide algorithms to infer K sparse networks. We evaluate the performance of our algorithms using both synthetic and real datasets. We also evaluate the performance of our method on compositional data obtained by subsampling from the true counts of the taxa. This evaluation models the real-world scenario, where the sample-taxa matrices that we have access to, contain only relative abundances of the observed taxa.

i24
S.Tavakoli and S.Yooseph Prior to describing our mixture modeling framework, we describe a single MPLN distribution. In our discussions, we denote matrices using upper-case letters, column vectors using bold letters (upper-or lower-case) and scalar values using normal lower-case letters.

The model
Single MPLN distribution: Consider an MPLN distribution with parameter set H ¼ ðl; RÞ, where l represents its d-dimensional mean vector and R represents its d Â d covariance matrix. Then, a d-dimensional count vector X ¼ ðx 1 ; :::; x d Þ T generated by this distribution has the following property: x j jk j $ Pðe kj Þ ðk 1 ; :: where PðcÞ denotes a Poisson distribution with mean c and N d ðl; RÞ denotes a d-dimensional multivariate normal distribution with mean l and covariance R. An MPLN distribution thus has two layers, with the observed counts being generated by a mixture of independent Poisson distributions whose (hidden) means follow a multivariate normal distribution. If we use k ¼ ðk 1 ; k 2 ; :::; k d Þ to denote the latent (or hidden) variable representing the Poisson means, then the probability density function pðXjHÞ of the MPLN distribution is given by Let X 1 ; X 2 ; :: . . . ; X n denote n independent samples drawn from an MPLN distribution, where each X i is a d-dimensional count vector. We use X ¼ ½X 1 X 2 :: . . . X n to denote the sample-taxa matrix generated from d taxa and n samples, and x ij to denote the count of the j-th taxon in X i . We can estimate the parameter set H of this MPLN distribution using a likelihood framework by considering the d-dimensional latent variables k 1 ; k 2 ; :: . . ., and k n associated with samples X 1 ; X 2 ; ::, and X n respectively; let matrix K ¼ ½k 1 k 2 :: . . . k n and k ij denote the j-th entry in k i . The log-likelihood function LðHjX; KÞ can be optimized using a simple iterative stepwise ascent (or conditional maximization) procedure to compute H and K. The estimated values of the parameters can be used to provide an approximation for pðXjHÞ as Q n i¼1 pðX i jk i ; HÞ, where pðX i jk i ; HÞ is defined as: An analogous approach based on optimizing the log-posterior using an iterative conditional modes algorithm has been proposed previously (Biswas et al., 2015).

Mixture of K MPLN distributions (MixMPLN):
In our framework, we consider a mixture model involving K MPLN distributions. Let p 1 ; :::; p K represent the mixing coefficients of the K components (where P K l¼1 p l ¼ 1), and let p l and H l denote the lth component distribution and its parameter set. A d-dimensional sample vector X generated from this mixture has the following distribution: p Xjp 1 ; :::; p K ; H 1 ; ::: For n independent samples X ¼ ½X 1 X 2 :: . . . X n , the probability distribution is given by p Xjp 1 ; :::; p K ; H 1 ; ::: The general log-likelihood function is thus Lðp 1 ; :::; p K ; K 1 ; :::; K K ; H 1 ; :::; where k il is the d-dimensional latent variable associated with X i in component l. We use a maximum log-likelihood framework to estimate the parameters of the MixMPLN model from the observed data X by optimizing the function Lðp 1 ; :::; p K ; K 1 ; :::; K K ; H 1 ; :::; H K jXÞ.

Optimizing the log-likelihood function using the MM principle
The MM principle is a general technique (Hunter and Lange, 2004;Lange, 2016) that has proven to be useful for tackling function optimization problems (MM stands for minorizationmaximization in maximization problems and for majorizationminimization in minimization problems). For our scenario, let hðhÞ denote a function to be maximized. The MM principle proposes to maximize the minorizer function gðhjh t Þ instead of maximizing hðhÞ directly; here, h t denotes a fixed value of the parameter h. The function gðhjh t Þ is said to be a minorizer of hðhÞ if: Therefore, the first step in our MM approach is to find a minorizer function which has the required property. For this, we use the following observation that follows from the concavity property of the log function (Lange, 2016;Zhou and Lange, 2010) for m nonnegative values b 1 ; b 2 ; :: . . . ; b m : Equation (6) can thus be lower-bounded based on this observation: where, weight w t il is defined as follows: We use the function on the right-hand side of Equation (9) as the minorizer function for our problem. Thus, we will define the new objective function (L) to be maximized as follows: Lðp 1 ; p 2 ; :::; p K ; K 1 ; :::; K K ; H 1 ; H 2 ; :::; Learning a mixture of microbial networks using MM i25

Steps of the MixMPLN optimization algorithm
We used a coordinate ascent approach in conjunction with a block update strategy to optimize L. We present the details of parameter initialization and subsequent iterative updates below.

Parameter initialization
The n samples X 1 X 2 :: . . . X n are partitioned into K clusters (components) using the K-means algorithm. Then, the samples assigned to a component are used to estimate the parameters of that component using the moments of an MPLN distribution (Aitchison and Ho, 1989), given by the equations below; here, r ij denotes the ij-th entry in R.

Parameter estimation in iteration ðt þ 1Þ
The portion of function L in Equation (11) that is dependent on the p i 's can be optimized.
L 1 ðp 1 ; p 2 ; :::; p l Þ ¼ X n i¼1 X K l¼1 w il t ðlogðp l ÞÞÞ: Since P l p l ¼ 1, we can optimize L 1 by introducing a Lagrange multiplier and identifying a stationary point of the subsequent Lagrangian (Bilmes et al., 1998). This yields where w t il is calculated using Equation (10). Considering the part of the L function that is dependent on K and H, we have the following term to maximize: L 2 K 1 ; :::; K K ; H 1 ; ::: Expanding p l using Equation (3), we have: L 2 ðK 1 ; :::; K K ; H 1 ; :::; where k ijl is the j-th entry in k il . We solve for the parameters separately using the partial derivation method. Calculation of the partial derivative of L 2 with respect to k ijl gives us: where ha; bi denotes the inner product of vectors a and b, and R À1 :jl denotes the j-th column of R À1 l . We use the Newton-Raphson method to estimate k tþ1 ijl from this equation, using values from iteration t for R À1 ; l; and k ij 0 l (where j 6 ¼ j 0 ). Partial derivation with respect to l l gives us: Thus, l l tþ1 can be estimated from w il t and k il t11 .
And finally, partial derivation with respect to R À1 l results in: We can solve this equation using matrix derivative rules to compute an estimate for the covariance matrix R l in iteration ðt þ 1Þ as:

Inferring sparse networks using an l 1 -penalty model
We extended the MixMPLN framework by incorporating an l 1norm penalty as follows: pðXjp 1 ; :::; p K ; H 1 ; :::; where kR À1 l k 1 is the l 1 -norm of the precision matrix of the l-th component, and q 1 ; :::; q K are tuning parameters that can be selected independently. This framework allows for the inference of sparse networks associated with the K components. For a fixed tuning parameter of q and a multivariate Gaussian distribution, the problem of selecting a precision matrix with the l 1 -norm penalty can be stated as (Friedman et al., 2008): argmax R À1 flogðdetðR À1 ÞÞ À traceðSR À1 Þ À qkR À1 k 1 g; where S denotes the empirical covariance matrix. In our implementation of the extended MixMPLN framework, we calculated the empirical covariance matrix for each component using Equation (20) in each iteration. We used the 'glasso' and 'huge' packages in R to solve the sparse precision matrix selection problem (Friedman et al., 2008;Zhao et al., 2012). We applied three different strategies using each of the two packages. In MixMPLN þ glasso(cross validation), we used cross validation to determine the value of q (i.e. we picked that q value which gave the best log-likelihood value among the subsamples). In MixMPLN þ glasso (fixed tuning parameter), we used q ¼ 2d 2 =ðNkR À1 init k 1 Þ, as proposed in Biswas et al. (2015). In this formulation, R À1 init is the estimated precision matrix after the initialization step of MixMPLN. In MixMPLN þ glasso(iterative tuning parameter), we used the same formulation to initialize the q value, but then updated it in each iteration based on the new estimated precision matrix in that iteration.
In MixMPLN þ huge(StARS), we used the stability approach to regularization selection (StARS) method (Liu et al., 2010). This method selects the coefficient which results in the most edge stability in the final graph) (Kurtz et al., 2015). The tuning parameter selection method in MixMPLN þ huge(fixed tuning parameter) and MixMPLN þ huge(fixed tuning parameter) was the same as the corresponding implementations using glasso.

Performance evaluation and datasets
Synthetic sample-taxa count matrices were generated in order to assess the performance of the various MixMPLN algorithms. We evaluated the convergence properties of the algorithms as a function of increasing sample sizes. Since, in practice, sample-taxa count matrices generated from biological samples are compositional in nature, we also evaluated the effect of sampling from the true (or absolute) counts, and the subsequent application of data normalization, on network recovery and convergence. In addition, we also evaluated the accuracy in recovering sparse networks. Finally, we applied our mixture model framework to analyze a real dataset.

Datasets
Synthetic data generation: Each sample-taxa count matrix X was produced by combining samples generated from K component MPLN distributions, where component l generated n l samples (d-length count vectors), and such that p l ¼ n l n and n ¼ R K l¼1 n l . For each component l, the d Â d covariance matrix of its MPLN distribution was derived from a randomly generated d Â d positive definite precision matrix containing a fixed number of zero entries (as given by the sparsity level sp which denotes the fraction matrix entries that are zero). The mean vector for each MPLN component was a random d-length vector. For a sample-taxa matrix X generated this way, it is assumed that each entry in the matrix is the true (or absolute) abundance of taxon j in sample i. We refer to X as the original count matrix. To simulate compositional count data and sequencing depth differences between the biological samples, we generated a sampled data matrix XS from X by first normalizing each entry in a sample (by dividing by sample size) and subsequently scaling that value by a sample-specific random number Y 2 ½5000; 10000 (to model sequencing depth for the biological sample). Finally, to study the effect of data normalization, we applied the trimmed mean of M-values (TMM) normalization procedure [from the 'edgeR' package (Robinson and Oshlack, 2010)] to XS to generate the TMM normalized data matrix TS.
Real data: We also applied our mixture modeling framework to a sample-taxa count matrix produced by a recent microbiome study (Yooseph et al., 2015) that explored connections between gut microbiome composition and the risk of Plasmodium falciparum infection. In this study, stool samples from a cohort composed of 195 Malian adults and children were collected and analyzed. The samples were assayed by sequencing the 16S ribosomal RNA gene to determine the bacterial communities they contained. This generated a sample-taxa count matrix with 195 samples and 221 bacterial genera which we analyzed in this paper.

Benchmarking criteria
Let A dÂd denote the true precision matrix and B dÂd an inferred (or predicted) precision matrix. For evaluating the performance of our algorithms on synthetic data, we used three different criteria to compare the inferred precision matrices with the original precision matrices that were used to generate the sample-taxa matrices. • Frobenius norm of the difference between the partial correlations of matrices A and B. Frobenius norm of a matrix M is defined . For a precision matrix C, its partial correlation matrix P is calculated as P½i; j ¼ ÀC½i; j= ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ffi C½i; i Ã C½j; j p . • Area under the ROC (AUC): this measure was used to assess the recovery of the edges of the microbial network (i.e. identification of the zero entries in the precision matrix). The AUC was calculated by applying varying thresholds to the original and estimated precision matrices to define zero and non-zero entries. As any non-zero entry in the estimated precision matrix represents an edge in the graph, the specificity and sensitivity of detecting an edge at different thresholds can be computed and used to plot the receiver-operating characteristic curve (ROC).
For the above measures, smaller values for relative difference and Frobenius norm indicate increased proximity to the ground truth. Values closer to 1 for the AUC plots indicate increased accuracy in reconstructing the network topology. When K > 1, we first matched the predicted precision matrix (of a component) to the nearest true precision matrix from the set of K true precision matrices. We used the Frobenius norm measure for this. After pairing the true and predicted matrices, we report their mean value statistics.

Results
We implemented the MixMPLN algorithms in R, and assessed their performance using the synthetic datasets. For our assessments, we  generated sample-taxa count matrices X (and their corresponding XS and TS matrices) for the following four sets of parameters: For each dataset, each component mixing coefficient was 1=K. In addition, five replicates were generated for each parameter combination. In total, 465 datasets were generated and analyzed. The datasets with sp ¼ 0.9 were used to assess the performance of the MixMPLN algorithms in recovering sparse networks.
First we evaluated the ability of the MixMPLN algorithm to recover the true precision matrices with increasing sample size n. For this, we used the original count data, the sampled data and the TMM normalized data. Figure 1 shows the benchmark results for the parameter combination of d ¼ 200; sp ¼ 0:7 and K ¼ 1, 2, 3; Supplementary Figures S1 and S2 show the corresponding results for d ¼ 30; sp ¼ 0:5; K ¼ 1; 2; 3 and for d ¼ 100; sp ¼ 0:7; K ¼ 1; 2; 3. The three benchmark criteria (relative difference, Frobenius norm and AUC) show that the entries in predicted precision matrices approach their true values as the sample size n increases. A strong convergence trend is seen using the original count data (blue curves/bar chart), with the AUC values approaching 0.97, 0.96 and 0.9 for K ¼ 1, 2, 3 respectively. The drop in performance with increasing K is not unexpected given the smaller fraction of data available per component to infer the component parameters. The figure also shows that the accuracy of recovery of the true precision matrices is not as high when using the sampled data (red curves/bar chart) and the TMM normalized data (orange curves/bar chart). In addition, from our analysis, it is not immediately evident that applying a TMM type data normalization is advantageous for the purpose of inferring the underlying covariance structure of the network.
We also evaluated the performance of MixMPLN and its l 1 -norm penalty variants in recovering sparse networks. Table 1 and Figure 2 show the performance of these methods for d ¼ 200, K ¼ 1, 2, 3 and sparsity level sp ¼ 0.9. Sample sizes of n ¼ 2d; 5d; 10d were used in these evaluations. As can be seen, the performance for the methods generally improve with increasing n, and the l 1 -norm penalty variants perform better than the unpenalized MixMPLN model on these data. The performances of the l 1 -norm penalty variants are generally quite comparable to each other [with MixMPLN þ huge(StARS) having a slightly lower performance compared to the others].
Since MixMPLN þ glass(cross validation) performs better than the other approaches for n ¼ 2d, we decided to apply this method to analyze the real dataset. We used the silhouette method from the 'factoextra' R package (Kassambara, 2017) to compute the optimal number of components from this sample-taxa matrix. Figure 3 shows the results of our analysis. We find that there is strong evidence for two underlying (and different) microbial networks (K ¼ 2 components) associated with this sample-taxa data. We assigned component membership to the samples based on their final weights w il [Equation (10)]. This resulted in Component 1 containing 158 samples and Component 2 containing 37 samples. The average age Fig. 3. Application of MixMPLN þ glasso with cross validation to a real dataset. Green and red edges represent positive and negative entries respectively in the estimated partial correlation matrices. (a) Graph of Component 1 which contains 158 samples; (b) graph of Component 2 which contains 37 samples. The threshold to select the edges is 0.3; (c) Selection of the optimal number of the components of the individuals in Component 1 was 9 years while that of individuals in Component 2 was 0.7 years. Our reconstructed networks are consistent with the observation that infants have a different gut microbiome composition compared to older children and adults (Yooseph et al., 2015). The constructed networks include edges involving bacterial groups like Bifidobacterium, Staphylococcus, Streptococcus and Escherichia-Shigella that are known to be key players in early gut microbiome development. Our method identifies both positive and negative interactions between pairs of taxa (red and green edges) for the chosen threshold of 0.3; Supplementary Figure S3 shows the graph structures for other selected threshold values. The biological significance of these interactions needs to be investigated further.