Minimal spanning tree

Formally speaking, a minimal spanning tree (MST) is the shortest way to indirectly interconnect all molecules in a set [119, 120]. It is calculated in the high-dimensional descriptor space and can be visualized as a branched tree (see Fig. 23b). 

The MST interprets all n compounds of the library as points in the high-dimensional space of descriptors. These points are connected by n-1 edges, so that exactly one path from each point to every other point is generated and the sum of all edge lengths is minimal. 

---

Fig. 30.9. Examples of trees in a graph (a) is the minimal spanning tree [18],...

The minimal spanning tree also operates on the distance matrix. Here, near by patterns are connected with lines in such a way that the sum of the connecting lines is minimal and no closed loops are constructed. Here too the information on distances is retained, but the mutual orientation of patterns is omitted. Both methods, hierarchical clustering and minimal spanning tree, aim for making clusters in the multi-dimensional space visible on a plane. 

Unsupervised learning methods - cluster analysis - display methods - nonlinear mapping (NLM) - minimal spanning tree (MST) - principal components analysis (PCA) Finding structures/similarities (groups, classes) in the data... 

In this passage we demonstrate that comparable results may also be obtained when other methods of unsupervised learning, e.g. the non-hierarchical cluster algorithm CLUPOT [COOMANS and MASSART, 1981] or the procedure of the computation of the minimal spanning tree [LEBART et al., 1984], which is similar to the cluster analysis, are applied to the environmental data shown above. 

Certainly it is possible to apply also other display methods for the visualization of such complex environmental data, as particulate emissions. TREIGER et al. [1993 1994] describe the study of different aerosol samples by nonlinear mapping of electron probe microanalysis data. Different interpretable groups of chemical elements which determine the composition of aerosol samples can be obtained. More recent work by WIENKE and HOPKE [1994] and WIENKE et al. [1994] discuss the combination of different chemometric techniques for better graphical representation of aerosol particle data. The authors use receptor modeling with a minimal spanning tree combined with a neural network. 

Purely numerical methods such as hierarchical clustering or the minimal spanning tree compute the similarity of molecules directly in the high-dimensional descriptor space. The results promise higher accuracy (no mapping errors), but their interpretation is less intuitive. 

Figs. 22 and 23 show the results of these calculations. The grouping does not depend mainly on the method used. Selective and nonselective COX inhibitors are well separated on the nonlinear map. Hierarchical clustering analyses form a single branch for the selective group of molecules, and also in the visualization of the minimal spanning tree compounds are lined up in the same way. 

Fig. 23 Classification of the NSAID dataset based on three-dimensional autocorrelation descriptors, a) Hierarchical clustering analysis (HCA). The dark gray cluster includes the COX-2-selective drugs, b) Visualization of the minimal spanning tree (MST). The longest connections are drawn as dotted lines in order to derive classes of compounds.

Fig. 4 Genetic relatedness between HEV strains from human and non-human sources and from various countries. Minimal spanning trees of 81 sequences of 148 nucleotides HEV RNA showing genetic distances between genotype three HEV strains from humans and animals, (a) Strains labelled by geographical origin, (b) Strains labelled by biological origin. The 13 recent Dutch cases are marked with ID numbers inside the coloured circles (adapted from Bergen et al. BMC Infectious Diseases 2008 8 61 doi 10.1186/1471-2334-8-61)...

Figure 2 Minimal spanning tree and MDS configurations in two and three dimensions for calculation of 23 properties of HC1 with 8 computational methods...

Minimal spanning tree Least sum-of-link path that connects all nodes in a graph with no cycles (closed circuits). 

We have four nodes, a, b, c, and d, and seek to build a minimal spanning tree given the edge weights ... 

Generally, useful techniques for finding clusters are "hierarchical clustering" (Chapter 7.2) and "minimal spanning tree" (Chapter 7.3). 

At the start of this method all pattern points are connected together. The mathematical requirement for this connection is a minimum total length of all line segments (Figure 44). Such a connection network is called a minimal spanning tree it may contain branches but must not contain circuits. 

FIGURE 44. Clustering by a minimal spanning tree. The tree is broken into clusters by cutting all segments that are longer than a predetermined value. 

Various methods are possible to break the minimal spanning tree into clusters C240, 4083. In one of the methods all line segments are cutted that are longer than a length supplied by the researcher. This method is particularly effective in the detection of outlying patterns. 

D. Wienke and P. K. Hopke, Ami. Chim. Acta, 291,1 (1994). Projection of Prim s Minimal Spanning Tree into a Kohonen Neural Network for Identification of Airborne Particle Sources by Their Multielement Trace Patterns. 

---