Bioinformatics Unit   -   CNIO
Cluster Server
 
Help

-- DEMO VERSION --

Cluster Methods

    Several method are available here. All of them are sequential, agglomerative, hierarchic, nonoverlapping clustering methods.

    First, they calculate the distance matrix. After that, they join the mutually most similar (least dissimilar) pair and recalculate the distance matrix but with the new cluster instead of the joined pair and repeat these steps until only one cluster remains (the root of the tree).

    The diference among these methods are the rules to calculate the distance between the new cluster and the remaining items and clusters.

  1. Single and Complete Linkage Clustering

    1. Single linkage

      2. The distance of any item to the new cluster (a, b) is the smallest of the distances between that item and either a or b.

      The distance of any extant cluster to the new cluster is the smallest of the distances between items of each cluster.

    2. Complete linkage

      3. The distance of any item to the new cluster (a, b) is the largest of the distances between that item and either a or b.

      The distance of any extant cluster to the new cluster is the largest of the distances between items of each cluster.

  2. Average Linkage Clustering

    3. The distance of any item to the new cluster (a, b) is the average of the distances between that item and either a or b.

    The distance of any extant cluster to the new cluster is the average of the distances between items of each cluster.

    1. Arithmetic Average

      2. These algorithms compute the average similarity of a candidate cluster to an extant cluster.

      1. UPGMA

        2. The UPGMA algorithm weights each item in the candidate cluster equally, regardless of its structural subdivision.

      2. WPGMA

        3. The WPGMA differs from UPGMA by weighting the member most recently admitted to a cluster equal with all previous members.

    2. Centroid

      3. These methods compute the centroid of the items that join to from clusters.

      1. UPGMC

        2. The UPGMC algorithm weights each item in the candidate cluster equally, regardless of its structural subdivision.

      2. WPGMC

        3. The WPGMC differs from UPGMC by weighting the member most recently admitted to a cluster equal with all previous members.



See   Sneath and Sokal (1973) "Numerical Taxonomy" Freeman, San Francisco   for more details.
Use of this program is logged Send comments to the webmaster. Last rev. March 22nd, 2001