<jupyter_start><jupyter_text>**Source of the materials**: Biopython cookbook (adapted)Status: Draft Cluster analysis================Cluster analysis is the grouping of items into clusters based on thesimilarity of the items to each other. In bioinformatics, clustering iswidely used in gene expression data analysis to find groups of geneswith similar gene expression profiles. This may identify functionallyrelated genes, as well as suggest the function of presently unknowngenes.The Biopython module `Bio.Cluster` provides commonly used clusteringalgorithms and was designed with the application to gene expression datain mind. However, this module can also be used for cluster analysis ofother types of data. `Bio.Cluster` and the underlying C ClusteringLibrary is described by De Hoon *et al.* @dehoon2004.The following four clustering approaches are implemented in`Bio.Cluster`:-   Hierarchical clustering (pairwise centroid-, single-, complete-, and    average-linkage);-   $k$-means, $k$-medians, and $k$-medoids clustering;-   Self-Organizing Maps;-   Principal Component Analysis. Data representation {data-representation .unnumbered}The data to be clustered are represented by a $n \times m$ NumericalPython array `data`. Within the context of gene expression dataclustering, typically the rows correspond to different genes whereas thecolumns correspond to different experimental conditions. The clusteringalgorithms in `Bio.Cluster` can be applied both to rows (genes) and tocolumns (experiments). Missing values {missing-values .unnumbered}Often in microarray experiments, some of the data values are missing,which is indicated by an additional $n \times m$ Numerical Pythoninteger array `mask`. If `mask[i,j]==0`, then `data[i,j]` is missing andis ignored in the analysis. Random number generator {random-number-generator .unnumbered}The $k$-means/medians/medoids clustering algorithms and Self-OrganizingMaps (SOMs) include the use of a random number generator. The uniformrandom number generator in `Bio.Cluster` is based on the algorithm byL’Ecuyer @lecuyer1988, while random numbers following the binomialdistribution are generated using the BTPE algorithm by <NAME> @kachitvichyanukul1988. The random number generator isinitialized automatically during its first call. As this random numbergenerator uses a combination of two multiplicative linear congruentialgenerators, two (integer) seeds are needed for initialization, for whichwe use the system-supplied random number generator `rand` (in the Cstandard library). We initialize this generator by calling `srand` withthe epoch time in seconds, and use the first two random numbersgenerated by `rand` as seeds for the uniform random number generator in`Bio.Cluster`.Distance functions {sec:distancefunctions}------------------In order to cluster items into groups based on their similarity, weshould first define what exactly we mean by *similar*. `Bio.Cluster`provides eight distance functions, indicated by a single character, tomeasure similarity, or conversely, distance:-   `'e'`: Euclidean distance;-   `'b'`: City-block distance.-   `'c'`: Pearson correlation coefficient;-   `'a'`: Absolute value of the Pearson correlation coefficient;-   `'u'`: Uncentered Pearson correlation (equivalent to the cosine of    the angle between two data vectors);-   `'x'`: Absolute uncentered Pearson correlation;-   `'s'`: Spearman’s rank correlation;-   `'k'`: Kendall’s $\tau$.The first two are true distance functions that satisfy the triangleinequality:$$d\left(\underline{u},\underline{v}\right) \leq d\left(\underline{u},\underline{w}\right) + d\left(\underline{w},\underline{v}\right) \textrm{ for all } \underline{u}, \underline{v}, \underline{w},$$and are therefore refered to as *metrics*. In everyday language, thismeans that the shortest distance between two points is a straight line.The remaining six distance measures are related to the correlationcoefficient, where the distance $d$ is defined in terms of thecorrelation $r$ by $d=1-r$. Note that these distance functions are*semi-metrics* that do not satisfy the triangle inequality. For example,for $$\underline{u}=\left(1,0,-1\right);$$$$\underline{v}=\left(1,1,0\right);$$$$\underline{w}=\left(0,1,1\right);$$ we find a Pearson distance$d\left(\underline{u},\underline{w}\right) = 1.8660$, while$d\left(\underline{u},\underline{v}\right)+d\left(\underline{v},\underline{w}\right) = 1.6340$. Euclidean distance {euclidean-distance .unnumbered}In `Bio.Cluster`, we define the Euclidean distance as$$d = {1 \over n} \sum_{i=1}^{n} \left(x_i-y_i\right)^{2}.$$ Only thoseterms are included in the summation for which both $x_i$ and $y_i$ arepresent, and the denominator $n$ is chosen accordingly. As theexpression data $x_i$ and $y_i$ are subtracted directly from each other,we should make sure that the expression data are properly normalizedwhen using the Euclidean distance. City-block distance {city-block-distance .unnumbered}The city-block distance, alternatively known as the Manhattan distance,is related to the Euclidean distance. Whereas the Euclidean distancecorresponds to the length of the shortest path between two points, thecity-block distance is the sum of distances along each dimension. Asgene expression data tend to have missing values, in `Bio.Cluster` wedefine the city-block distance as the sum of distances divided by thenumber of dimensions:$$d = {1 \over n} \sum_{i=1}^n \left|x_i-y_i\right|.$$ This is equal tothe distance you would have to walk between two points in a city, whereyou have to walk along city blocks. As for the Euclidean distance, theexpression data are subtracted directly from each other, and we shouldtherefore make sure that they are properly normalized. The Pearson correlation coefficient {the-pearson-correlation-coefficient .unnumbered}The Pearson correlation coefficient is defined as$$r = \frac{1}{n} \sum_{i=1}^n \left( \frac{x_i -\bar{x}}{\sigma_x} \right) \left(\frac{y_i -\bar{y}}{\sigma_y} \right),$$in which $\bar{x}, \bar{y}$ are the sample mean of $x$ and $y$respectively, and $\sigma_x, \sigma_y$ are the sample standard deviationof $x$ and $y$. The Pearson correlation coefficient is a measure for howwell a straight line can be fitted to a scatterplot of $x$ and $y$. Ifall the points in the scatterplot lie on a straight line, the Pearsoncorrelation coefficient is either +1 or -1, depending on whether theslope of line is positive or negative. If the Pearson correlationcoefficient is equal to zero, there is no correlation between $x$ and$y$.The *Pearson distance* is then defined as$$d_{\textrm{P}} \equiv 1 - r.$$ As the Pearson correlation coefficientlies between -1 and 1, the Pearson distance lies between 0 and 2. Absolute Pearson correlation {absolute-pearson-correlation .unnumbered}By taking the absolute value of the Pearson correlation, we find anumber between 0 and 1. If the absolute value is 1, all the points inthe scatter plot lie on a straight line with either a positive or anegative slope. If the absolute value is equal to zero, there is nocorrelation between $x$ and $y$.The corresponding distance is defined as$$d_{\textrm A} \equiv 1 - \left|r\right|,$$ where $r$ is the Pearsoncorrelation coefficient. As the absolute value of the Pearsoncorrelation coefficient lies between 0 and 1, the corresponding distancelies between 0 and 1 as well.In the context of gene expression experiments, the absolute correlationis equal to 1 if the gene expression profiles of two genes are eitherexactly the same or exactly opposite. The absolute correlationcoefficient should therefore be used with care. Uncentered correlation (cosine of the angle) {uncentered-correlation-cosine-of-the-angle .unnumbered}In some cases, it may be preferable to use the *uncentered correlation*instead of the regular Pearson correlation coefficient. The uncenteredcorrelation is defined as$$r_{\textrm U} = \frac{1}{n} \sum_{i=1}^{n} \left(\frac{x_i}{\sigma_x^{(0)}} \right) \left(\frac{y_i}{\sigma_y^{(0)}} \right),$$where $$\begin{aligned}\sigma_x^{(0)} & = & \sqrt{{\frac{1}{n}} \sum_{i=1}^{n}x_i^2}; \nonumber \\\sigma_y^{(0)} & = & \sqrt{{\frac{1}{n}} \sum_{i=1}^{n}y_i^2}. \nonumber\end{aligned}$$This is the same expression as for the regular Pearson correlationcoefficient, except that the sample means $\bar{x}, \bar{y}$ are setequal to zero. The uncentered correlation may be appropriate if there isa zero reference state. For instance, in the case of gene expressiondata given in terms of log-ratios, a log-ratio equal to zero correspondsto the green and red signal being equal, which means that theexperimental manipulation did not affect the gene expression.The distance corresponding to the uncentered correlation coefficient isdefined as $$d_{\mbox{U}} \equiv 1 - r_{\mbox{U}},$$ where$r_{\mbox{U}}$ is the uncentered correlation. As the uncenteredcorrelation coefficient lies between -1 and 1, the correspondingdistance lies between 0 and 2.The uncentered correlation is equal to the cosine of the angle of thetwo data vectors in $n$-dimensional space, and is often referred to assuch. Absolute uncentered correlation {absolute-uncentered-correlation .unnumbered}As for the regular Pearson correlation, we can define a distance measureusing the absolute value of the uncentered correlation:$$d_{\mbox{AU}} \equiv 1 - \left|r_{\mbox{U}}\right|,$$ where$r_{\mbox{U}}$ is the uncentered correlation coefficient. As theabsolute value of the uncentered correlation coefficient lies between 0and 1, the corresponding distance lies between 0 and 1 as well.Geometrically, the absolute value of the uncentered correlation is equalto the cosine between the supporting lines of the two data vectors(i.e., the angle without taking the direction of the vectors intoconsideration). Spearman rank correlation {spearman-rank-correlation .unnumbered}The Spearman rank correlation is an example of a non-parametricsimilarity measure, and tends to be more robust against outliers thanthe Pearson correlation.To calculate the Spearman rank correlation, we replace each data valueby their rank if we would order the data in each vector by their value.We then calculate the Pearson correlation between the two rank vectorsinstead of the data vectors.As in the case of the Pearson correlation, we can define a distancemeasure corresponding to the Spearman rank correlation as$$d_{\mbox{S}} \equiv 1 - r_{\mbox{S}},$$ where $r_{\mbox{S}}$ is theSpearman rank correlation. Kendall’s $\tau$ {kendalls-tau .unnumbered}Kendall’s $\tau$ is another example of a non-parametric similaritymeasure. It is similar to the Spearman rank correlation, but instead ofthe ranks themselves only the relative ranks are used to calculate$\tau$ (see Snedecor & Cochran @snedecor1989).We can define a distance measure corresponding to Kendall’s $\tau$ as$$d_{\mbox{K}} \equiv 1 - \tau.$$ As Kendall’s $\tau$ is always between-1 and 1, the corresponding distance will be between 0 and 2. Weighting {weighting .unnumbered}For most of the distance functions available in `Bio.Cluster`, a weightvector can be applied. The weight vector contains weights for the itemsin the data vector. If the weight for item $i$ is $w_i$, then that itemis treated as if it occurred $w_i$ times in the data. The weight do nothave to be integers. For the Spearman rank correlation and Kendall’s$\tau$, weights do not have a well-defined meaning and are therefore notimplemented. Calculating the distance matrix {subsec:distancematrix .unnumbered}The distance matrix is a square matrix with all pairwise distancesbetween the items in `data`, and can be calculated by the function`distancematrix` in the `Bio.Cluster` module:<jupyter_code>from Bio.Cluster import distancematrix
matrix = distancematrix(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data` (required)\    Array containing the data for the items.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `weight` (default: `None`)\    The weights to be used when calculating distances. If    `weight==None`, then equal weights are assumed.-   `transpose` (default: `0`)\    Determines if the distances between the rows of `data` are to be    calculated (`transpose==0`), or between the columns of `data`    (`transpose==1`).-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).To save memory, the distance matrix is returned as a list of 1D arrays.The number of columns in each row is equal to the row number. Hence, thefirst row has zero elements. An example of the return value is ```[array([]), array([1.]), array([7., 3.]), array([4., 2., 6.])]``` This corresponds to the distance matrix $$\left(\begin{array}{cccc}0 & 1 & 7 & 4  \\1 & 0 & 3 & 2  \\7 & 3 & 0 & 6  \\4 & 2 & 6 & 0\end{array}\right).$$Calculating cluster properties------------------------------ Calculating the cluster centroids {subsec:clustercentroids .unnumbered}The centroid of a cluster can be defined either as the mean or as themedian of each dimension over all cluster items. The function`clustercentroids` in `Bio.Cluster` can be used to calculate either:<jupyter_code>from Bio.Cluster import clustercentroids
cdata, cmask = clustercentroids(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data` (required)\    Array containing the data for the items.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `clusterid` (default: `None`)\    Vector of integers showing to which cluster each item belongs. If    `clusterid` is `None`, then all items are assumed to belong to the    same cluster.-   `method` (default: `'a'`)\    Specifies whether the arithmetic mean (`method=='a'`) or the median    (`method=='m'`) is used to calculate the cluster center.-   `transpose` (default: `0`)\    Determines if the centroids of the rows of `data` are to be    calculated (`transpose==0`), or the centroids of the columns of    `data` (`transpose==1`).This function returns the tuple `(cdata, cmask)`. The centroid data arestored in the 2D Numerical Python array `cdata`, with missing dataindicated by the 2D Numerical Python integer array `cmask`. Thedimensions of these arrays are$\left(\textrm{number of clusters}, \textrm{number of columns}\right)$if `transpose` is `0`, or$\left(\textrm{number of rows}, \textrm{number of clusters}\right)$ if`transpose` is `1`. Each row (if `transpose` is `0`) or column (if`transpose` is `1`) contains the averaged data corresponding to thecentroid of each cluster. Calculating the distance between clusters {calculating-the-distance-between-clusters .unnumbered}Given a distance function between *items*, we can define the distancebetween two *clusters* in several ways. The distance between thearithmetic means of the two clusters is used in pairwisecentroid-linkage clustering and in $k$-means clustering. In $k$-medoidsclustering, the distance between the medians of the two clusters is usedinstead. The shortest pairwise distance between items of the twoclusters is used in pairwise single-linkage clustering, while thelongest pairwise distance is used in pairwise maximum-linkageclustering. In pairwise average-linkage clustering, the distance betweentwo clusters is defined as the average over the pairwise distances.To calculate the distance between two clusters, use<jupyter_code>from Bio.Cluster import clusterdistance
distance = clusterdistance(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data` (required)\    Array containing the data for the items.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `weight` (default: `None`)\    The weights to be used when calculating distances. If    `weight==None`, then equal weights are assumed.-   `index1` (default: `0`)\    A list containing the indices of the items belonging to the    first cluster. A cluster containing only one item $i$ can be    represented either as a list `[i]`, or as an integer `i`.-   `index2` (default: `0`)\    A list containing the indices of the items belonging to the    second cluster. A cluster containing only one items $i$ can be    represented either as a list `[i]`, or as an integer `i`.-   `method` (default: `'a'`)\    Specifies how the distance between clusters is defined:    -   `'a'`: Distance between the two cluster centroids (arithmetic        mean);    -   `'m'`: Distance between the two cluster centroids (median);    -   `'s'`: Shortest pairwise distance between items in the two        clusters;    -   `'x'`: Longest pairwise distance between items in the two        clusters;    -   `'v'`: Average over the pairwise distances between items in the        two clusters.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).-   `transpose` (default: `0`)\    If `transpose==0`, calculate the distance between the rows of    `data`. If `transpose==1`, calculate the distance between the    columns of `data`.Partitioning algorithms-----------------------Partitioning algorithms divide items into $k$ clusters such that the sumof distances over the items to their cluster centers is minimal. Thenumber of clusters $k$ is specified by the user. Three partitioningalgorithms are available in `Bio.Cluster`:-   $k$-means clustering-   $k$-medians clustering-   $k$-medoids clusteringThese algorithms differ in how the cluster center is defined. In$k$-means clustering, the cluster center is defined as the mean datavector averaged over all items in the cluster. Instead of the mean, in$k$-medians clustering the median is calculated for each dimension inthe data vector. Finally, in $k$-medoids clustering the cluster centeris defined as the item which has the smallest sum of distances to theother items in the cluster. This clustering algorithm is suitable forcases in which the distance matrix is known but the original data matrixis not available, for example when clustering proteins based on theirstructural similarity.The expectation-maximization (EM) algorithm is used to find thispartitioning into $k$ groups. In the initialization of the EM algorithm,we randomly assign items to clusters. To ensure that no empty clustersare produced, we use the binomial distribution to randomly choose thenumber of items in each cluster to be one or more. We then randomlypermute the cluster assignments to items such that each item has anequal probability to be in any cluster. Each cluster is thus guaranteedto contain at least one item.We then iterate:-   Calculate the centroid of each cluster, defined as either the mean,    the median, or the medoid of the cluster;-   Calculate the distances of each item to the cluster centers;-   For each item, determine which cluster centroid is closest;-   Reassign each item to its closest cluster, or stop the iteration if    no further item reassignments take place.To avoid clusters becoming empty during the iteration, in $k$-means and$k$-medians clustering the algorithm keeps track of the number of itemsin each cluster, and prohibits the last remaining item in a cluster frombeing reassigned to a different cluster. For $k$-medoids clustering,such a check is not needed, as the item that functions as the clustercentroid has a zero distance to itself, and will therefore never becloser to a different cluster.As the initial assignment of items to clusters is done randomly, usuallya different clustering solution is found each time the EM algorithm isexecuted. To find the optimal clustering solution, the $k$-meansalgorithm is repeated many times, each time starting from a differentinitial random clustering. The sum of distances of the items to theircluster center is saved for each run, and the solution with the smallestvalue of this sum will be returned as the overall clustering solution.How often the EM algorithm should be run depends on the number of itemsbeing clustered. As a rule of thumb, we can consider how often theoptimal solution was found; this number is returned by the partitioningalgorithms as implemented in this library. If the optimal solution wasfound many times, it is unlikely that better solutions exist than theone that was found. However, if the optimal solution was found onlyonce, there may well be other solutions with a smaller within-clustersum of distances. If the number of items is large (more than severalhundreds), it may be difficult to find the globally optimal solution.The EM algorithm terminates when no further reassignments take place. Wenoticed that for some sets of initial cluster assignments, the EMalgorithm fails to converge due to the same clustering solutionreappearing periodically after a small number of iteration steps. Wetherefore check for the occurrence of such periodic solutions during theiteration. After a given number of iteration steps, the currentclustering result is saved as a reference. By comparing the clusteringresult after each subsequent iteration step to the reference state, wecan determine if a previously encountered clustering result is found. Insuch a case, the iteration is halted. If after a given number ofiterations the reference state has not yet been encountered, the currentclustering solution is saved to be used as the new reference state.Initially, ten iteration steps are executed before resaving thereference state. This number of iteration steps is doubled each time, toensure that periodic behavior with longer periods can also be detected. $k$-means and $k$-medians {k-means-and-k-medians .unnumbered}The $k$-means and $k$-medians algorithms are implemented as the function`kcluster` in `Bio.Cluster`:<jupyter_code>from Bio.Cluster import kcluster
clusterid, error, nfound = kcluster(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data` (required)\    Array containing the data for the items.-   `nclusters` (default: `2`)\    The number of clusters $k$.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `weight` (default: `None`)\    The weights to be used when calculating distances. If    `weight==None`, then equal weights are assumed.-   `transpose` (default: `0`)\    Determines if rows (`transpose` is `0`) or columns (`transpose` is    `1`) are to be clustered.-   `npass` (default: `1`)\    The number of times the $k$-means/-medians clustering algorithm is    performed, each time with a different (random) initial condition. If    `initialid` is given, the value of `npass` is ignored and the    clustering algorithm is run only once, as it behaves    deterministically in that case.-   `method` (default: `a`)\    describes how the center of a cluster is found:    -   `method=='a'`: arithmetic mean ($k$-means clustering);    -   `method=='m'`: median ($k$-medians clustering).    For other values of `method`, the arithmetic mean is used.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]). Whereas all eight distance measures    are accepted by `kcluster`, from a theoretical viewpoint it is best    to use the Euclidean distance for the $k$-means algorithm, and the    city-block distance for $k$-medians.-   `initialid` (default: `None`)\    Specifies the initial clustering to be used for the EM algorithm. If    `initialid==None`, then a different random initial clustering is    used for each of the `npass` runs of the EM algorithm. If    `initialid` is not `None`, then it should be equal to a 1D array    containing the cluster number (between `0` and `nclusters-1`) for    each item. Each cluster should contain at least one item. With the    initial clustering specified, the EM algorithm is deterministic.This function returns a tuple `(clusterid, error, nfound)`, where`clusterid` is an integer array containing the number of the cluster towhich each row or cluster was assigned, `error` is the within-clustersum of distances for the optimal clustering solution, and `nfound` isthe number of times this optimal solution was found. $k$-medoids clustering {k-medoids-clustering .unnumbered}The `kmedoids` routine performs $k$-medoids clustering on a given set ofitems, using the distance matrix and the number of clusters passed bythe user:<jupyter_code>from Bio.Cluster import kmedoids
clusterid, error, nfound = kmedoids(distance)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined: , nclusters=2, npass=1,initialid=None)|-   `distance` (required)\    The matrix containing the distances between the items; this matrix    can be specified in three ways:    -   as a 2D Numerical Python array (in which only the left-lower        part of the array will be accessed): ```distance = array([[0.0, 1.1, 2.3],                          [1.1, 0.0, 4.5],                          [2.3, 4.5, 0.0]])```     -   as a 1D Numerical Python array containing consecutively the        distances in the left-lower part of the distance matrix: ```distance = array([1.1, 2.3, 4.5])```     -   as a list containing the rows of the left-lower part of the        distance matrix: ```distance = [array([]|,                    array([1.1]),                    array([2.3, 4.5])                   ]```     These three expressions correspond to the same distance matrix.-   `nclusters` (default: `2`)\    The number of clusters $k$.-   `npass` (default: `1`)\    The number of times the $k$-medoids clustering algorithm is    performed, each time with a different (random) initial condition. If    `initialid` is given, the value of `npass` is ignored, as the    clustering algorithm behaves deterministically in that case.-   `initialid` (default: `None`)\    Specifies the initial clustering to be used for the EM algorithm. If    `initialid==None`, then a different random initial clustering is    used for each of the `npass` runs of the EM algorithm. If    `initialid` is not `None`, then it should be equal to a 1D array    containing the cluster number (between `0` and `nclusters-1`) for    each item. Each cluster should contain at least one item. With the    initial clustering specified, the EM algorithm is deterministic.This function returns a tuple `(clusterid, error, nfound)`, where`clusterid` is an array containing the number of the cluster to whicheach item was assigned, `error` is the within-cluster sum of distancesfor the optimal $k$-medoids clustering solution, and `nfound` is thenumber of times the optimal solution was found. Note that the clusternumber in `clusterid` is defined as the item number of the itemrepresenting the cluster centroid.Hierarchical clustering-----------------------Hierarchical clustering methods are inherently different from the$k$-means clustering method. In hierarchical clustering, the similarityin the expression profile between genes or experimental conditions arerepresented in the form of a tree structure. This tree structure can beshown graphically by programs such as Treeview and Java Treeview, whichhas contributed to the popularity of hierarchical clustering in theanalysis of gene expression data.The first step in hierarchical clustering is to calculate the distancematrix, specifying all the distances between the items to be clustered.Next, we create a node by joining the two closest items. Subsequentnodes are created by pairwise joining of items or nodes based on thedistance between them, until all items belong to the same node. A treestructure can then be created by retracing which items and nodes weremerged. Unlike the EM algorithm, which is used in $k$-means clustering,the complete process of hierarchical clustering is deterministic.Several flavors of hierarchical clustering exist, which differ in howthe distance between subnodes is defined in terms of their members. In`Bio.Cluster`, pairwise single, maximum, average, and centroid linkageare available.-   In pairwise single-linkage clustering, the distance between two    nodes is defined as the shortest distance among the pairwise    distances between the members of the two nodes.-   In pairwise maximum-linkage clustering, alternatively known as    pairwise complete-linkage clustering, the distance between two nodes    is defined as the longest distance among the pairwise distances    between the members of the two nodes.-   In pairwise average-linkage clustering, the distance between two    nodes is defined as the average over all pairwise distances between    the items of the two nodes.-   In pairwise centroid-linkage clustering, the distance between two    nodes is defined as the distance between their centroids. The    centroids are calculated by taking the mean over all the items in    a cluster. As the distance from each newly formed node to existing    nodes and items need to be calculated at each step, the computing    time of pairwise centroid-linkage clustering may be significantly    longer than for the other hierarchical clustering methods. Another    peculiarity is that (for a distance measure based on the Pearson    correlation), the distances do not necessarily increase when going    up in the clustering tree, and may even decrease. This is caused by    an inconsistency between the centroid calculation and the distance    calculation when using the Pearson correlation: Whereas the Pearson    correlation effectively normalizes the data for the distance    calculation, no such normalization occurs for the    centroid calculation.For pairwise single-, complete-, and average-linkage clustering, thedistance between two nodes can be found directly from the distancesbetween the individual items. Therefore, the clustering algorithm doesnot need access to the original gene expression data, once the distancematrix is known. For pairwise centroid-linkage clustering, however, thecentroids of newly formed subnodes can only be calculated from theoriginal data and not from the distance matrix.The implementation of pairwise single-linkage hierarchical clustering isbased on the SLINK algorithm (<NAME>, 1973), which is much faster andmore memory-efficient than a straightforward implementation of pairwisesingle-linkage clustering. The clustering result produced by thisalgorithm is identical to the clustering solution found by theconventional single-linkage algorithm. The single-linkage hierarchicalclustering algorithm implemented in this library can be used to clusterlarge gene expression data sets, for which conventional hierarchicalclustering algorithms fail due to excessive memory requirements andrunning time. Representing a hierarchical clustering solution {representing-a-hierarchical-clustering-solution .unnumbered}The result of hierarchical clustering consists of a tree of nodes, inwhich each node joins two items or subnodes. Usually, we are not onlyinterested in which items or subnodes are joined at each node, but alsoin their similarity (or distance) as they are joined. To store one nodein the hierarchical clustering tree, we make use of the class `Node`,which defined in `Bio.Cluster`. An instance of `Node` has threeattributes:-   `left`-   `right`-   `distance`Here, `left` and `right` are integers referring to the two items orsubnodes that are joined at this node, and `distance` is the distancebetween them. The items being clustered are numbered from 0 to$\left(\textrm{number of items} - 1\right)$, while clusters are numberedfrom -1 to $-\left(\textrm{number of items}-1\right)$. Note that thenumber of nodes is one less than the number of items.To create a new `Node` object, we need to specify `left` and `right`;`distance` is optional.<jupyter_code>from Bio.Cluster import Node
Node(2, 3)
Node(2, 3, 0.91)<jupyter_output><empty_output><jupyter_text>The attributes `left`, `right`, and `distance` of an existing `Node`object can be modified directly:<jupyter_code>node = Node(4, 5)
node.left = 6
node.right = 2
node.distance = 0.73
node<jupyter_output><empty_output><jupyter_text>An error is raised if `left` and `right` are not integers, or if`distance` cannot be converted to a floating-point value.The Python class `Tree` represents a full hierarchical clusteringsolution. A `Tree` object can be created from a list of `Node` objects:<jupyter_code>from Bio.Cluster import Node, Tree
nodes = [Node(1, 2, 0.2), Node(0, 3, 0.5), Node(-2, 4, 0.6), Node(-1, -3, 0.9)]
tree = Tree(nodes)
print(tree)<jupyter_output>(1, 2): 0.2
(0, 3): 0.5
(-2, 4): 0.6
(-1, -3): 0.9<jupyter_text>The `Tree` initializer checks if the list of nodes is a validhierarchical clustering result:<jupyter_code>nodes = [Node(1, 2, 0.2), Node(0, 2, 0.5)]
try:
    Tree(nodes)
    raise Exception("Should not arrive here")
except ValueError:
    print("This tree is problematic")<jupyter_output>This tree is problematic<jupyter_text>Individual nodes in a `Tree` object can be accessed using squarebrackets:<jupyter_code>nodes = [Node(1, 2, 0.2), Node(0, -1, 0.5)]
tree = Tree(nodes)
tree[0]
tree[1]
tree[-1]<jupyter_output><empty_output><jupyter_text>As a `Tree` object is read-only, we cannot change individual nodes in a`Tree` object. However, we can convert the tree to a list of nodes,modify this list, and create a new tree from this list:<jupyter_code>tree = Tree([Node(1, 2, 0.1), Node(0, -1, 0.5), Node(-2, 3, 0.9)])
print(tree)
nodes = tree[:]
nodes[0] = Node(0, 1, 0.2)
nodes[1].left = 2
tree = Tree(nodes)
print(tree)<jupyter_output><empty_output><jupyter_text>This guarantees that any `Tree` object is always well-formed.To display a hierarchical clustering solution with visualizationprograms such as Java Treeview, it is better to scale all node distancessuch that they are between zero and one. This can be accomplished bycalling the `scale` method on an existing `Tree` object:<jupyter_code>tree.scale()<jupyter_output><empty_output><jupyter_text>This method takes no arguments, and returns `None`.After hierarchical clustering, the items can be grouped into $k$clusters based on the tree structure stored in the `Tree` object bycutting the tree:<jupyter_code>clusterid = tree.cut(nclusters=1)<jupyter_output><empty_output><jupyter_text>where `nclusters` (defaulting to `1`) is the desired number of clusters$k$. This method ignores the top $k-1$ linking events in the treestructure, resulting in $k$ separated clusters of items. The number ofclusters $k$ should be positive, and less than or equal to the number ofitems. This method returns an array `clusterid` containing the number ofthe cluster to which each item is assigned. Performing hierarchical clustering {performing-hierarchical-clustering .unnumbered}To perform hierarchical clustering, use the `treecluster` function in`Bio.Cluster`.<jupyter_code>from Bio.Cluster import treecluster
tree = treecluster(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data`\    Array containing the data for the items.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `weight` (default: `None`)\    The weights to be used when calculating distances. If    `weight==None`, then equal weights are assumed.-   `transpose` (default: `0`)\    Determines if rows (`transpose==0`) or columns (`transpose==1`) are    to be clustered.-   `method` (default: `'m'`)\    defines the linkage method to be used:    -   `method=='s'`: pairwise single-linkage clustering    -   `method=='m'`: pairwise maximum- (or complete-) linkage        clustering    -   `method=='c'`: pairwise centroid-linkage clustering    -   `method=='a'`: pairwise average-linkage clustering-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).To apply hierarchical clustering on a precalculated distance matrix,specify the `distancematrix` argument when calling `treecluster`function instead of the `data` argument:<jupyter_code>from Bio.Cluster import treecluster
tree = treecluster(distancematrix=distance)<jupyter_output><empty_output><jupyter_text>In this case, the following arguments are defined:-   `distancematrix`\    The distance matrix, which can be specified in three ways:    -   as a 2D Numerical Python array (in which only the left-lower        part of the array will be accessed): ```distance = array([[0.0, 1.1, 2.3],                          [1.1, 0.0, 4.5],                          [2.3, 4.5, 0.0]])```     -   as a 1D Numerical Python array containing consecutively the        distances in the left-lower part of the distance matrix: ```distance = array([1.1, 2.3, 4.5])```     -   as a list containing the rows of the left-lower part of the        distance matrix: ```distance = [array([]),                    array([1.1]),                    array([2.3, 4.5])```     These three expressions correspond to the same distance matrix. As    `treecluster` may shuffle the values in the distance matrix as part    of the clustering algorithm, be sure to save this array in a    different variable before calling `treecluster` if you need    it later.-   `method`\    The linkage method to be used:    -   `method=='s'`: pairwise single-linkage clustering    -   `method=='m'`: pairwise maximum- (or complete-) linkage        clustering    -   `method=='a'`: pairwise average-linkage clustering    While pairwise single-, maximum-, and average-linkage clustering can    be calculated from the distance matrix alone, pairwise    centroid-linkage cannot.When calling `treecluster`, either `data` or `distancematrix` should be`None`.This function returns a `Tree` object. This object contains$\left(\textrm{number of items} - 1\right)$ nodes, where the number ofitems is the number of rows if rows were clustered, or the number ofcolumns if columns were clustered. Each node describes a pairwiselinking event, where the node attributes `left` and `right` each containthe number of one item or subnode, and `distance` the distance betweenthem. Items are numbered from 0 to$\left(\textrm{number of items} - 1\right)$, while clusters are numbered-1 to $-\left(\textrm{number of items}-1\right)$.Self-Organizing Maps--------------------Self-Organizing Maps (SOMs) were invented by Kohonen to describe neuralnetworks (see for instance Kohonen, 1997 @kohonen1997). Tamayo (1999)first applied Self-Organizing Maps to gene expression data @tamayo1999.SOMs organize items into clusters that are situated in some topology.Usually a rectangular topology is chosen. The clusters generated by SOMsare such that neighboring clusters in the topology are more similar toeach other than clusters far from each other in the topology.The first step to calculate a SOM is to randomly assign a data vector toeach cluster in the topology. If rows are being clustered, then thenumber of elements in each data vector is equal to the number ofcolumns.An SOM is then generated by taking rows one at a time, and finding whichcluster in the topology has the closest data vector. The data vector ofthat cluster, as well as those of the neighboring clusters, are adjustedusing the data vector of the row under consideration. The adjustment isgiven by$$\Delta \underline{x}_{\textrm{cell}} = \tau \cdot \left(\underline{x}_{\textrm{row}} - \underline{x}_{\textrm{cell}} \right).$$The parameter $\tau$ is a parameter that decreases at each iterationstep. We have used a simple linear function of the iteration step:$$\tau = \tau_{\textrm{init}} \cdot \left(1 - {i \over n}\right),$$$\tau_{\textrm{init}}$ is the initial value of $\tau$ as specified bythe user, $i$ is the number of the current iteration step, and $n$ isthe total number of iteration steps to be performed. While changes aremade rapidly in the beginning of the iteration, at the end of iterationonly small changes are made.All clusters within a radius $R$ are adjusted to the gene underconsideration. This radius decreases as the calculation progresses as$$R = R_{\textrm{max}} \cdot \left(1 - {i \over n}\right),$$ in whichthe maximum radius is defined as$$R_{\textrm{max}} = \sqrt{N_x^2 + N_y^2},$$ where$\left(N_x, N_y\right)$ are the dimensions of the rectangle defining thetopology.The function `somcluster` implements the complete algorithm to calculatea Self-Organizing Map on a rectangular grid. First it initializes therandom number generator. The node data are then initialized using therandom number generator. The order in which genes or microarrays areused to modify the SOM is also randomized. The total number ofiterations in the SOM algorithm is specified by the user.To run `somcluster`, use<jupyter_code>from Bio.Cluster import somcluster
clusterid, celldata = somcluster(data)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `data` (required)\    Array containing the data for the items.-   `mask` (default: `None`)\    Array of integers showing which data are missing. If `mask[i,j]==0`,    then `data[i,j]` is missing. If `mask==None`, then all data    are present.-   `weight` (default: `None`)\    contains the weights to be used when calculating distances. If    `weight==None`, then equal weights are assumed.-   `transpose` (default: `0`)\    Determines if rows (`transpose` is `0`) or columns (`transpose` is    `1`) are to be clustered.-   `nxgrid, nygrid` (default: `2, 1`)\    The number of cells horizontally and vertically in the rectangular    grid on which the Self-Organizing Map is calculated.-   `inittau` (default: `0.02`)\    The initial value for the parameter $\tau$ that is used in the    SOM algorithm. The default value for `inittau` is 0.02, which was    used in Michael Eisen’s Cluster/TreeView program.-   `niter` (default: `1`)\    The number of iterations to be performed.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).This function returns the tuple `(clusterid, celldata)`:-   `clusterid`:\    An array with two columns, where the number of rows is equal to the    number of items that were clustered. Each row contains the $x$ and    $y$ coordinates of the cell in the rectangular SOM grid to which the    item was assigned.-   `celldata`:\    An array with dimensions    $\left(\verb|nxgrid|, \verb|nygrid|, \textrm{number of columns}\right)$    if rows are being clustered, or    $\left(\verb|nxgrid|, \verb|nygrid|, \textrm{number of rows}\right)$    if columns are being clustered. Each element `[ix][iy]` of this    array is a 1D vector containing the gene expression data for the    centroid of the cluster in the grid cell with coordinates    `[ix][iy]`.Principal Component Analysis----------------------------Principal Component Analysis (PCA) is a widely used technique foranalyzing multivariate data. A practical example of applying PrincipalComponent Analysis to gene expression data is presented by Yeung andRuzzo (2001) @yeung2001.In essence, PCA is a coordinate transformation in which each row in thedata matrix is written as a linear sum over basis vectors calledprincipal components, which are ordered and chosen such that eachmaximally explains the remaining variance in the data vectors. Forexample, an $n \times 3$ data matrix can be represented as anellipsoidal cloud of $n$ points in three dimensional space. The firstprincipal component is the longest axis of the ellipsoid, the secondprincipal component the second longest axis of the ellipsoid, and thethird principal component is the shortest axis. Each row in the datamatrix can be reconstructed as a suitable linear combination of theprincipal components. However, in order to reduce the dimensionality ofthe data, usually only the most important principal components areretained. The remaining variance present in the data is then regarded asunexplained variance.The principal components can be found by calculating the eigenvectors ofthe covariance matrix of the data. The corresponding eigenvaluesdetermine how much of the variance present in the data is explained byeach principal component.Before applying principal component analysis, typically the mean issubtracted from each column in the data matrix. In the example above,this effectively centers the ellipsoidal cloud around its centroid in 3Dspace, with the principal components describing the variation of pointsin the ellipsoidal cloud with respect to their centroid.The function `pca` below first uses the singular value decomposition tocalculate the eigenvalues and eigenvectors of the data matrix. Thesingular value decomposition is implemented as a translation in C of theAlgol procedure `svd` @golub1971, which uses Householderbidiagonalization and a variant of the QR algorithm. The principalcomponents, the coordinates of each data vector along the principalcomponents, and the eigenvalues corresponding to the principalcomponents are then evaluated and returned in decreasing order of themagnitude of the eigenvalue. If data centering is desired, the meanshould be subtracted from each column in the data matrix before callingthe `pca` routine.To apply Principal Component Analysis to a rectangular matrix `data`,use<jupyter_code>from Bio.Cluster import pca
columnmean, coordinates, components, eigenvalues = pca(data)<jupyter_output><empty_output><jupyter_text>This function returns a tuple`columnmean, coordinates, components, eigenvalues`:-   `columnmean`\    Array containing the mean over each column in `data`.-   `coordinates`\    The coordinates of each row in `data` with respect to the    principal components.-   `components`\    The principal components.-   `eigenvalues`\    The eigenvalues corresponding to each of the principal components.The original matrix `data` can be recreated by calculating`columnmean +  dot(coordinates, components)`.Handling Cluster/TreeView-type files------------------------------------Cluster/TreeView are GUI-based codes for clustering gene expressiondata. They were originally written by [MichaelEisen](http://rana.lbl.gov) while at Stanford University. `Bio.Cluster`contains functions for reading and writing data files that correspond tothe format specified for Cluster/TreeView. In particular, by saving aclustering result in that format, TreeView can be used to visualize theclustering results. We recommend using <NAME>’sJava TreeView program,which can display hierarchical as well as $k$-means clustering results.An object of the class `Record` contains all information stored in aCluster/TreeView-type data file. To store the information contained inthe data file in a `Record` object, we first open the file and then readit:<jupyter_code>from Bio import Cluster
handle = open("mydatafile.txt")
record = Cluster.read(handle)
handle.close()<jupyter_output><empty_output><jupyter_text>This two-step process gives you some flexibility in the source of thedata. For example, you can use<jupyter_code>import gzip # Python standard library
handle = gzip.open("mydatafile.txt.gz")<jupyter_output><empty_output><jupyter_text>to open a gzipped file, or<jupyter_code>import urllib # Python standard library
handle = urllib.urlopen("http://somewhere.org/mydatafile.txt")<jupyter_output><empty_output><jupyter_text>to open a file stored on the Internet before calling `read`.The `read` command reads the tab-delimited text file `mydatafile.txt`containing gene expression data in the format specified for MichaelEisen’s Cluster/TreeView program. For a description of this file format,see the manual to Cluster/TreeView. It is available at [Michael Eisen’slab website](http://rana.lbl.gov/manuals/ClusterTreeView.pdf) and at[ourwebsite](http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/cluster3.pdf).A `Record` object has the following attributes:-   `data`\    The data array containing the gene expression data. Genes are stored    row-wise, while microarrays are stored column-wise.-   `mask`\    This array shows which elements in the `data` array, if any,    are missing. If `mask[i,j]==0`, then `data[i,j]` is missing. If no    data were found to be missing, `mask` is set to `None`.-   `geneid`\    This is a list containing a unique description for each gene (i.e.,    ORF numbers).-   `genename`\    This is a list containing a description for each gene (i.e.,    gene name). If not present in the data file, `genename` is set to    `None`.-   `gweight`\    The weights that are to be used to calculate the distance in    expression profile between genes. If not present in the data file,    `gweight` is set to `None`.-   `gorder`\    The preferred order in which genes should be stored in an    output file. If not present in the data file, `gorder` is set to    `None`.-   `expid`\    This is a list containing a description of each microarray, e.g.    experimental condition.-   `eweight`\    The weights that are to be used to calculate the distance in    expression profile between microarrays. If not present in the data    file, `eweight` is set to `None`.-   `eorder`\    The preferred order in which microarrays should be stored in an    output file. If not present in the data file, `eorder` is set to    `None`.-   `uniqid`\    The string that was used instead of UNIQID in the data file.After loading a `Record` object, each of these attributes can beaccessed and modified directly. For example, the data can belog-transformed by taking the logarithm of `record.data`. Calculating the distance matrix {calculating-the-distance-matrix .unnumbered}To calculate the distance matrix between the items stored in the record,use<jupyter_code>matrix = record.distancematrix()<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `transpose` (default: `0`)\    Determines if the distances between the rows of `data` are to be    calculated (`transpose==0`), or between the columns of `data`    (`transpose==1`).-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).This function returns the distance matrix as a list of rows, where thenumber of columns of each row is equal to the row number (see section\[subsec:distancematrix\]). Calculating the cluster centroids {calculating-the-cluster-centroids .unnumbered}To calculate the centroids of clusters of items stored in the record,use<jupyter_code>cdata, cmask = record.clustercentroids()<jupyter_output><empty_output><jupyter_text>-   `clusterid` (default: `None`)\    Vector of integers showing to which cluster each item belongs. If    `clusterid` is not given, then all items are assumed to belong to    the same cluster.-   `method` (default: `'a'`)\    Specifies whether the arithmetic mean (`method=='a'`) or the median    (`method=='m'`) is used to calculate the cluster center.-   `transpose` (default: `0`)\    Determines if the centroids of the rows of `data` are to be    calculated (`transpose==0`), or the centroids of the columns of    `data` (`transpose==1`).This function returns the tuple `cdata, cmask`; see section\[subsec:clustercentroids\] for a description. Calculating the distance between clusters {calculating-the-distance-between-clusters-1 .unnumbered}To calculate the distance between clusters of items stored in therecord, use<jupyter_code>distance = record.clusterdistance()<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `index1` (default: `0`)\    A list containing the indices of the items belonging to the    first cluster. A cluster containing only one item $i$ can be    represented either as a list `[i]`, or as an integer `i`.-   `index2` (default: `0`)\    A list containing the indices of the items belonging to the    second cluster. A cluster containing only one item $i$ can be    represented either as a list `[i]`, or as an integer `i`.-   `method` (default: `'a'`)\    Specifies how the distance between clusters is defined:    -   `'a'`: Distance between the two cluster centroids (arithmetic        mean);    -   `'m'`: Distance between the two cluster centroids (median);    -   `'s'`: Shortest pairwise distance between items in the two        clusters;    -   `'x'`: Longest pairwise distance between items in the two        clusters;    -   `'v'`: Average over the pairwise distances between items in the        two clusters.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).-   `transpose` (default: `0`)\    If `transpose==0`, calculate the distance between the rows of    `data`. If `transpose==1`, calculate the distance between the    columns of `data`. Performing hierarchical clustering {performing-hierarchical-clustering-1 .unnumbered}To perform hierarchical clustering on the items stored in the record,use<jupyter_code>tree = record.treecluster()<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `transpose` (default: `0`)\    Determines if rows (`transpose==0`) or columns (`transpose==1`) are    to be clustered.-   `method` (default: `'m'`)\    defines the linkage method to be used:    -   `method=='s'`: pairwise single-linkage clustering    -   `method=='m'`: pairwise maximum- (or complete-) linkage        clustering    -   `method=='c'`: pairwise centroid-linkage clustering    -   `method=='a'`: pairwise average-linkage clustering-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).-   `transpose`\    Determines if genes or microarrays are being clustered. If    `transpose==0`, genes (rows) are being clustered. If `transpose==1`,    microarrays (columns) are clustered.This function returns a `Tree` object. This object contains$\left(\textrm{number of items} - 1\right)$ nodes, where the number ofitems is the number of rows if rows were clustered, or the number ofcolumns if columns were clustered. Each node describes a pairwiselinking event, where the node attributes `left` and `right` each containthe number of one item or subnode, and `distance` the distance betweenthem. Items are numbered from 0 to$\left(\textrm{number of items} - 1\right)$, while clusters are numbered-1 to $-\left(\textrm{number of items}-1\right)$. Performing $k$-means or $k$-medians clustering {performing-k-means-or-k-medians-clustering .unnumbered}To perform $k$-means or $k$-medians clustering on the items stored inthe record, use<jupyter_code>clusterid, error, nfound = record.kcluster()<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `nclusters` (default: `2`)\    The number of clusters $k$.-   `transpose` (default: `0`)\    Determines if rows (`transpose` is `0`) or columns (`transpose` is    `1`) are to be clustered.-   `npass` (default: `1`)\    The number of times the $k$-means/-medians clustering algorithm is    performed, each time with a different (random) initial condition. If    `initialid` is given, the value of `npass` is ignored and the    clustering algorithm is run only once, as it behaves    deterministically in that case.-   `method` (default: `a`)\    describes how the center of a cluster is found:    -   `method=='a'`: arithmetic mean ($k$-means clustering);    -   `method=='m'`: median ($k$-medians clustering).    For other values of `method`, the arithmetic mean is used.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).This function returns a tuple `(clusterid, error, nfound)`, where`clusterid` is an integer array containing the number of the cluster towhich each row or cluster was assigned, `error` is the within-clustersum of distances for the optimal clustering solution, and `nfound` isthe number of times this optimal solution was found. Calculating a Self-Organizing Map {calculating-a-self-organizing-map .unnumbered}To calculate a Self-Organizing Map of the items stored in the record,use<jupyter_code>clusterid, celldata = record.somcluster()<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `transpose` (default: `0`)\    Determines if rows (`transpose` is `0`) or columns (`transpose` is    `1`) are to be clustered.-   `nxgrid, nygrid` (default: `2, 1`)\    The number of cells horizontally and vertically in the rectangular    grid on which the Self-Organizing Map is calculated.-   `inittau` (default: `0.02`)\    The initial value for the parameter $\tau$ that is used in the    SOM algorithm. The default value for `inittau` is 0.02, which was    used in <NAME>’s Cluster/TreeView program.-   `niter` (default: `1`)\    The number of iterations to be performed.-   `dist` (default: `'e'`, Euclidean distance)\    Defines the distance function to be used    (see \[sec:distancefunctions\]).This function returns the tuple `(clusterid, celldata)`:-   `clusterid`:\    An array with two columns, where the number of rows is equal to the    number of items that were clustered. Each row contains the $x$ and    $y$ coordinates of the cell in the rectangular SOM grid to which the    item was assigned.-   `celldata`:\    An array with dimensions    $\left(\verb|nxgrid|, \verb|nygrid|, \textrm{number of columns}\right)$    if rows are being clustered, or    $\left(\verb|nxgrid|, \verb|nygrid|, \textrm{number of rows}\right)$    if columns are being clustered. Each element `[ix][iy]` of this    array is a 1D vector containing the gene expression data for the    centroid of the cluster in the grid cell with coordinates    `[ix][iy]`. Saving the clustering result {saving-the-clustering-result .unnumbered}To save the clustering result, use<jupyter_code>record.save(jobname, geneclusters, expclusters)<jupyter_output><empty_output><jupyter_text>where the following arguments are defined:-   `jobname`\    The string `jobname` is used as the base name for names of the files    that are to be saved.-   `geneclusters`\    This argument describes the gene (row-wise) clustering result. In    case of $k$-means clustering, this is a 1D array containing the    number of the cluster each gene belongs to. It can be calculated    using `kcluster`. In case of hierarchical clustering, `geneclusters`    is a `Tree` object.-   `expclusters`\    This argument describes the (column-wise) clustering result for the    experimental conditions. In case of $k$-means clustering, this is a    1D array containing the number of the cluster each experimental    condition belongs to. It can be calculated using `kcluster`. In case    of hierarchical clustering, `expclusters` is a `Tree` object.This method writes the text file `jobname.cdt`, `jobname.gtr`,`jobname.atr`, `jobname*.kgg`, and/or `jobname*.kag` for subsequentreading by the Java TreeView program. If `geneclusters` and`expclusters` are both `None`, this method only writes the text file`jobname.cdt`; this file can subsequently be read into a new `Record`object.Example calculation-------------------This is an example of a hierarchical clustering calculation, usingsingle linkage clustering for genes and maximum linkage clustering forexperimental conditions. As the Euclidean distance is being used forgene clustering, it is necessary to scale the node distances `genetree`such that they are all between zero and one. This is needed for the JavaTreeView code to display the tree diagram correctly. To cluster theexperimental conditions, the uncentered correlation is being used. Noscaling is needed in this case, as the distances in `exptree` arealready between zero and two. The example data `cyano.txt` can be foundin the `data` subdirectory.<jupyter_code>from Bio import Cluster
handle = open("cyano.txt")
record = Cluster.read(handle)
handle.close()
genetree = record.treecluster(method='s')
genetree.scale()
exptree = record.treecluster(dist='u', transpose=1)
record.save("cyano_result", genetree, exptree)<jupyter_output><empty_output><jupyter_text>This will create the files `cyano_result.cdt`, `cyano_result.gtr`, and`cyano_result.atr`.Similarly, we can save a $k$-means clustering solution:<jupyter_code>from Bio import Cluster
handle = open("cyano.txt")
record = Cluster.read(handle)
handle.close()
(geneclusters, error, ifound) = record.kcluster(nclusters=5, npass=1000)
(expclusters, error, ifound) = record.kcluster(nclusters=2, npass=100, transpose=1)
record.save("cyano_result", geneclusters, expclusters)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08608498322699468, 'fraction_numerical': 0.006955863974215615, 'mean_word_length': 4.581734740706747, 'pattern_counts': {'":': 0, '<': 119, '<?xml version=': 0, '>': 119, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '492839', 'license': 'MIT', 'n_tokens_mistral': 16438, 'n_tokens_neox': 15210, 'n_words': 7723, 'path': 'notebooks/15 - Cluster Analysis.ipynb', 'repo_name': 'projetinho-bioinfo/biopython-notebook', 'size': '60853'}