This document discusses hierarchical clustering techniques for analyzing PFGE fingerprinting data. It provides the following key points:
- Dendograms can have multiple valid interpretations and may not accurately reflect relationships between clusters. Alternative clustering methods like single and complete linkage may provide different views.
- UPGMA averages similarities between clusters which can obscure relationships; other methods consider maximum/minimum similarities.
- Degenerate solutions are common with discrete PFGE data and different analyses may produce different dendrograms.
- Visual inspection and validation are needed to properly interpret any dendrogram. Large datasets can provide more robust clusterings.
This document discusses hierarchical clustering techniques for analyzing PFGE fingerprinting data. It provides the following key points:
- Dendograms can have multiple valid interpretations and may not accurately reflect relationships between clusters. Alternative clustering methods like single and complete linkage may provide different views.
- UPGMA averages similarities between clusters which can obscure relationships; other methods consider maximum/minimum similarities.
- Degenerate solutions are common with discrete PFGE data and different analyses may produce different dendrograms.
- Visual inspection and validation are needed to properly interpret any dendrogram. Large datasets can provide more robust clusterings.
This document discusses hierarchical clustering techniques for analyzing PFGE fingerprinting data. It provides the following key points:
- Dendograms can have multiple valid interpretations and may not accurately reflect relationships between clusters. Alternative clustering methods like single and complete linkage may provide different views.
- UPGMA averages similarities between clusters which can obscure relationships; other methods consider maximum/minimum similarities.
- Degenerate solutions are common with discrete PFGE data and different analyses may produce different dendrograms.
- Visual inspection and validation are needed to properly interpret any dendrogram. Large datasets can provide more robust clusterings.
This document discusses hierarchical clustering techniques for analyzing PFGE fingerprinting data. It provides the following key points:
- Dendograms can have multiple valid interpretations and may not accurately reflect relationships between clusters. Alternative clustering methods like single and complete linkage may provide different views.
- UPGMA averages similarities between clusters which can obscure relationships; other methods consider maximum/minimum similarities.
- Degenerate solutions are common with discrete PFGE data and different analyses may produce different dendrograms.
- Visual inspection and validation are needed to properly interpret any dendrogram. Large datasets can provide more robust clusterings.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 28
Dendrograms & PFGE analysis
Paul Vauterin Applied Maths BVBA
Outline of this talk: Simple explanation of mainstream hierarchical clustering (UPGMA) Interesting alternatives to UPGMA How to interpret a dendrogram? Problem of degenerate (equivalent) solutions
Bottom line: - be careful in interpreting dendrograms! - Consider alternatives to UPGMA (i. e. single & complete linkage)
Relevance of cluster analysis
Cluster Analysis is the mathematical study of methods for recognizing natural groups within a set of entities Simply a tool that groups together related entities, based on the observed similarities between them Used as a data exploration/mining tool in virtually every field (psychology, economy, finance, astronomy, ...) Applicable to virtually any type of data. Only a similarity matrix is needed Applicable to large data sets (>10 000 entities) Easy to interpret (simple & intuitive mathematical principle) weak points easier to anticipate
UPGMA algorithm Crucial step: determine similarities between two groups
UPGMA: average of all similarities
UPGMA algorithm Crucial step: determine similarities between two groups
Single linkage: highest similarity (best case scenario)
UPGMA algorithm Crucial step: determine similarities between two groups
Complete linkage: lowest similarity (worst case scenario) ... Other alternative schemes have been developed ...
How to interpret a dendrogram?
UPGMA tree:
A B C
What does this tell you? A & B are more close to each other than to C? Not necesarily true!
Fundamental problem: potential alternative solutions Equally valid Hidden Might give another view = not restricted to UPGMA or PFGE, but a major problem for most methods that summarise the original data
Degenerate dendrogram solutions
A simple example: PFGE, 3 organisms (A, B, C) Bands A B C Similarities:
A B C
A 100 50 50
B 100 0
100
UPGMA rule: Join highest similarities First A+B First A+C
How to solve this? Detect and visualise in a special way
A B C
A C B
A C B
Happens very often with discrete data with few degrees of freedom (bands on PFGE, but also MLST, MLVA, Spa typing, ...)
Degenerate dendrogram solutions
Degenerate dendrogram solutions
PFGE + band matching: even worse! A B C
A B C
A 100 100 0
B 100 100
100
A=B and B=C
A=C
Compromises the concept of a cluster of identical fingerprints Relaxed view: each member is identical to at least one other in the cluster Strict view: each member is identical to all other members of the cluster
Single linkage Single linkage Complete linkage Complete linkage
ALLWAYS human inspection needed anyway!
Case Study 6 5 4 3 2 1 0 # of different bands
PFGE fingerprints (Dis)similarity: # of different bands Complete linkage clustering Result= groups with members that have no more than n bands different with any other member = Good starting point for pattern naming
Case Study 6 5 4 3 2 1 0 # of different bands
PFGE fingerprints (Dis)similarity: # of different bands Single linkage clustering Result= groups with members that have no more than n bands different with some other members = Good starting point for finding clusters of related patterns
How to interpret a dendrogram?
Dendrogram: ... Suppose unique solution What does this tell you? ... Still not necessarily anything! Garbage In Garbage Out ...
A B C
A cluster algorithm will always produce a tree
Need for methods to address the reliability of a dendrogram Phylogenetics: standard tool = Felsensteins boostrap Not (well) suited to most typing data sets PFGE MLST VNTR
How to interpret a dendrogram?
Back to less sophisticated methods E. g. error flags on cluster levels Principle: each branch is an average representative of a variety of similarities -> show standard deviation
Visual inspection Cross-validation Large data sets are your friends!
Recipe 1: finding seed groups for pattern naming
Make sure you have Make sure you have a temporary field a temporary field
Install the plugin Install the plugin Dendrogram tools Dendrogram tools
Recipe 1: finding seed groups for pattern naming
Select Complete Linkage Select Complete Linkage and Different bands and Different bands
Recipe 1: finding seed groups for pattern naming
Use Fill field with Use Fill field with cluster number cluster number
Recipe 1: finding seed groups for pattern naming
Use 100% similarity Use 100% similarity Specify minimum Specify minimum group size group size Chose destination field Chose destination field Will overwrite any content!
Recipe 1: finding seed groups for pattern naming
Results Results
Resulting groups are Resulting groups are guaranteed to consist of guaranteed to consist of all identical fingerprints all identical fingerprints and have at least 5 and have at least 5 members members
Warning: numbering is not persistent: other data set might give different values
Recipe 2: find largest clusters in data set
Select Single Linkage Select Single Linkage and Different bands and Different bands
Recipe 2: find largest clusters in data set
Use 100% similarity Use 100% similarity (or 99% for 1 band difference) (or 99% for 1 band difference) Specify minimum Specify minimum group size group size Chose destination field Chose destination field
Recipe 2: find largest clusters in data set
Use Chart & Statistics tool Use Chart & Statistics tool
Add Temp field Add Temp field
Recipe 2: find largest clusters in data set
Use sort by frequency Use sort by frequency
Recipe 2: find largest clusters in data set
Fingerprints not associated Fingerprints not associated with any (large) cluster with any (large) cluster
Clusters ranked by size Clusters ranked by size use CTRL+click to select entries use CTRL+click to select entries
(Lecture Notes in Computer Science 5692 _ Information Systems and Applications, Incl. Internet_Web, And HCI) Edith Elkind (Auth.), Tommaso Di Noia, Francesco Buccafurri (Eds.)-E-Commerce and Web Techn
(Lecture Notes in Computer Science 5692 _ Information Systems and Applications, Incl. Internet_Web, And HCI) Edith Elkind (Auth.), Tommaso Di Noia, Francesco Buccafurri (Eds.)-E-Commerce and Web Techn
