1 package jalview.analysis;
3 import jalview.api.analysis.ScoreModelI;
4 import jalview.api.analysis.SimilarityParamsI;
5 import jalview.datamodel.SequenceNode;
6 import jalview.viewmodel.AlignmentViewport;
9 * This class implements distance calculations used in constructing a Average
10 * Distance tree (also known as UPGMA)
12 public class AverageDistanceTree extends TreeBuilder
19 * @param scoreParameters
21 public AverageDistanceTree(AlignmentViewport av, ScoreModelI sm,
22 SimilarityParamsI scoreParameters)
24 super(av, sm, scoreParameters);
28 * Calculates and saves the distance between the combination of cluster(i) and
29 * cluster(j) and all other clusters. An average of the distances from
30 * cluster(i) and cluster(j) is calculated, weighted by the sizes of each
37 protected void findClusterDistance(int i, int j)
39 int noi = clusters.elementAt(i).cardinality();
40 int noj = clusters.elementAt(j).cardinality();
42 // New distances from cluster i to others
43 double[] newdist = new double[noseqs];
45 for (int l = 0; l < noseqs; l++)
47 if ((l != i) && (l != j))
49 newdist[l] = ((distances.getValue(i, l) * noi) + (distances
50 .getValue(j, l) * noj)) / (noi + noj);
58 for (int ii = 0; ii < noseqs; ii++)
60 distances.setValue(i, ii, newdist[ii]);
61 distances.setValue(ii, i, newdist[ii]);
69 protected double findMinDistance()
71 double min = Double.MAX_VALUE;
73 for (int i = 0; i < (noseqs - 1); i++)
75 for (int j = i + 1; j < noseqs; j++)
77 if (!done.get(i) && !done.get(j))
79 if (distances.getValue(i, j) < min)
84 min = distances.getValue(i, j);
96 protected void findNewDistances(SequenceNode nodei, SequenceNode nodej,
102 SequenceNode sni = nodei;
103 SequenceNode snj = nodej;
108 sni = (SequenceNode) sni.left();
114 snj = (SequenceNode) snj.left();
117 nodei.dist = ((dist / 2) - ih);
118 nodej.dist = ((dist / 2) - jh);