2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
7 * Jalview is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation, either version 3
10 * of the License, or (at your option) any later version.
12 * Jalview is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty
14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19 * The Jalview Authors are detailed in the 'AUTHORS' file.
21 package jalview.analysis;
23 import java.util.BitSet;
24 import java.util.Vector;
26 import jalview.datamodel.AlignmentAnnotation;
27 import jalview.datamodel.BinaryNode;
28 import jalview.datamodel.ContactListI;
29 import jalview.datamodel.ContactMatrixI;
30 import jalview.math.Matrix;
31 import jalview.viewmodel.AlignmentViewport;
34 * This class implements distance calculations used in constructing a Average
35 * Distance tree (also known as UPGMA)
37 public class AverageDistanceEngine extends TreeEngine
41 AlignmentAnnotation aa;
43 * compute cosine distance matrix for a given contact matrix and create a UPGMA tree
46 public AverageDistanceEngine(AlignmentViewport av, AlignmentAnnotation aa, ContactMatrixI cm)
51 node = new Vector<BinaryNode>();
52 clusters = new Vector<BitSet>();
53 distances = new Matrix(new double[cm.getWidth()][cm.getWidth()]);
56 for (int i=0;i<cm.getWidth();i++)
58 // init the tree engine node for this column
59 BinaryNode cnode = new BinaryNode();
60 cnode.setElement(Integer.valueOf(i));
62 node.addElement(cnode);
63 BitSet bs = new BitSet();
65 clusters.addElement(bs);
67 // compute distance matrix element
68 ContactListI ith=cm.getContactList(i);
71 ContactListI jth = cm.getContactList(j);
73 for (int indx=0;indx<cm.getHeight();indx++)
75 prd+=ith.getContactAt(indx)*jth.getContactAt(indx);
77 distances.setValue(i, j, prd);
78 distances.setValue(j, i, prd);
82 noClus = clusters.size();
87 * Calculates and saves the distance between the combination of cluster(i) and
88 * cluster(j) and all other clusters. An average of the distances from
89 * cluster(i) and cluster(j) is calculated, weighted by the sizes of each
96 protected void findClusterDistance(int i, int j)
98 int noi = clusters.elementAt(i).cardinality();
99 int noj = clusters.elementAt(j).cardinality();
101 // New distances from cluster i to others
102 double[] newdist = new double[noseqs];
104 for (int l = 0; l < noseqs; l++)
106 if ((l != i) && (l != j))
108 newdist[l] = ((distances.getValue(i, l) * noi)
109 + (distances.getValue(j, l) * noj)) / (noi + noj);
117 for (int ii = 0; ii < noseqs; ii++)
119 distances.setValue(i, ii, newdist[ii]);
120 distances.setValue(ii, i, newdist[ii]);
128 protected double findMinDistance()
130 double min = Double.MAX_VALUE;
132 for (int i = 0; i < (noseqs - 1); i++)
134 for (int j = i + 1; j < noseqs; j++)
136 if (!done.get(i) && !done.get(j))
138 if (distances.getValue(i, j) < min)
143 min = distances.getValue(i, j);
155 protected void findNewDistances(BinaryNode nodei, BinaryNode nodej,
161 BinaryNode sni = nodei;
162 BinaryNode snj = nodej;
167 sni = (BinaryNode) sni.left();
173 snj = (BinaryNode) snj.left();
176 nodei.dist = ((dist / 2) - ih);
177 nodej.dist = ((dist / 2) - jh);