# Analysis of Gut Microbiome Structure Based on GMPR+Spectrum
## 2 Materials and Methods
### Methods
#### 2.2.3 Spectrum Algorithm  
Spectrum [23] is a new spectral clustering method, its idea is to view the data analysis problem as an optimal partitioning problem of the graph, where all OTUs are viewed as vertices in the space, and the vertices are connected with edges with weights. The edges with weights can be regarded as the similarity in OTUs. The key to this algorithm is that the self-adjusting density-aware kernel is employed to construct the similarity matrix, with the advantage that the similarity between the nearest neighbors can be further enhanced, while it can reduce noise. Spectrum can find the optimal number of clusters (K) involving the distribution of feature vectors, regardless of Gaussian or non-Gaussian structure [23].  
The similarity matrix \(A^{*}\) is computed using the adaptive density-aware kernel in the Spectrum algorithm. Starting with \(A^{*}\), the Ng spectral clustering method is used in Spectrum. At the same time, the number of clusters is estimated using an eigenvalue heuristic. Finally, the eigenvector matrix is clustered using Gaussian mixture modeling (GMM) to obtain the final output, i.e., a delineation of the feature clusters represented by the OTUs.  
1. The adaptive density-aware kernel is first used in Spectrum algorithm to compute the similarity matrix between different OTUs. The adaptive density perception kernel is: \[A_{ij}=\exp\left(\frac{-d^{2}(s_{i}s_{j})}{\sigma^{i}\sigma^{j}\big{(}CNN (s_{i}s_{j})+1\big{)}}\right)\] (3) where \(d(s_{i},s_{j})\) represents the Euclidean distance between point \(s_{i}\) and \(s_{j}\), \(\sigma_{i}\) and \(\sigma_{j}\) are the local scaling parameter, \(CNN(s_{i},s_{j})\) is the number of points in the connection area of the \(\varepsilon\) neighborhood around the point \(s_{i}\) and \(s_{j}\), and the \(\varepsilon\)-neighborhood of the point represents the radius of the sphere around the point.
2. The diagonal matrix \(D\) is obtained from \(A^{*}\), the diagonal matrix where (\(i\),\(i\)) element is the \(i\)th row of the sum of \(A^{*}\), and the normalized Laplacian matrix \(L\) is constructed using \(D\). \[L=D^{\
icefrac{{-1}}{{2}}}A^{*}D^{\
icefrac{{-1}}{{2}}}\] (4)
3. Decompose eigenvalues of \(L\) and extract its eigenvectors \(X_{1}\), \(X_{2}\),... \(X_{N+1}\) and eigenvalues \(\lambda_{1}\), \(\lambda_{2}\),... \(\lambda_{N+1}\).  
Determine the difference in eigenvalues, start with the second eigenvalue, i.e., \(n=2\), and choose the optimal \(k\), the difference in eigenvalues is maximized and denoted by \(k^{*}\). \[k^{*}=\overset{\text{argmax}}{n}(\lambda_{n}-\lambda_{n+1})\] (5)
5. Obtain the largest eigenvectors \(K^{*}\) and then form the matrix (each eigenvector is arranged in columns to form \(n\) vectors in a \(k^{*}\)-dimensional space), i.e., \(X=[x_{1},x_{2},\ldots x_{k^{*}}]\) \(\in R_{N+k^{*}}\).
6. Form the matrix Y from X by renormalizing each of X's rows to have unit length. \[Y_{ij}=\frac{X_{ij}}{\left(\sum_{j}x_{ij}\right)^{1/2}}\] (6)
7. Finally, each row of \(Y\) is considered as an OTU feature \(s_{i}\), and finally all OTUs are clustered into \(k^{*}\) clusters using GMM. The obtained class labels are the class labels of the original OTUs.