Class |
Line # |
Actions |
|||
---|---|---|---|---|---|
TreeEngine | 30 | 71 | 26 |
1 | /* | |
2 | * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) | |
3 | * Copyright (C) $$Year-Rel$$ The Jalview Authors | |
4 | * | |
5 | * This file is part of Jalview. | |
6 | * | |
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. | |
11 | * | |
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. | |
16 | * | |
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. | |
20 | */ | |
21 | package jalview.analysis; | |
22 | ||
23 | import java.util.BitSet; | |
24 | import java.util.Vector; | |
25 | ||
26 | import jalview.datamodel.BinaryNode; | |
27 | import jalview.datamodel.SequenceNode; | |
28 | import jalview.math.MatrixI; | |
29 | ||
30 | public abstract class TreeEngine | |
31 | { | |
32 | ||
33 | protected Vector<BitSet> clusters; | |
34 | ||
35 | protected BitSet done; | |
36 | ||
37 | protected int noseqs; | |
38 | ||
39 | protected int noClus; | |
40 | ||
41 | protected MatrixI distances; | |
42 | ||
43 | protected double ri; | |
44 | ||
45 | protected double rj; | |
46 | ||
47 | protected Vector<BinaryNode> node; | |
48 | ||
49 | BinaryNode maxdist; | |
50 | ||
51 | double maxDistValue; | |
52 | ||
53 | protected int mini; | |
54 | ||
55 | protected int minj; | |
56 | ||
57 | protected BinaryNode top; | |
58 | ||
59 | protected int ycount; | |
60 | ||
61 | double maxheight; | |
62 | ||
63 | /** | |
64 | * Calculates and returns r, whatever that is | |
65 | * | |
66 | * @param i | |
67 | * @param j | |
68 | * | |
69 | * @return | |
70 | */ | |
71 | 144 | protected double findr(int i, int j) |
72 | { | |
73 | 144 | double tmp = 1; |
74 | ||
75 | 7248 | for (int k = 0; k < noseqs; k++) |
76 | { | |
77 | 7104 | if ((k != i) && (k != j) && (!done.get(k))) |
78 | { | |
79 | 3408 | tmp = tmp + distances.getValue(i, k); |
80 | } | |
81 | } | |
82 | ||
83 | 144 | if (noClus > 2) |
84 | { | |
85 | 138 | tmp = tmp / (noClus - 2); |
86 | } | |
87 | ||
88 | 144 | return tmp; |
89 | } | |
90 | ||
91 | /** | |
92 | * Merges cluster(j) to cluster(i) and recalculates cluster and node distances | |
93 | * | |
94 | * @param i | |
95 | * @param j | |
96 | */ | |
97 | 72 | protected void joinClusters(final int i, final int j) |
98 | { | |
99 | 72 | double dist = distances.getValue(i, j); |
100 | ||
101 | 72 | ri = findr(i, j); |
102 | 72 | rj = findr(j, i); |
103 | ||
104 | 72 | findClusterDistance(i, j); |
105 | ||
106 | 72 | BinaryNode sn = new BinaryNode(); |
107 | ||
108 | 72 | sn.setLeft((node.elementAt(i))); |
109 | 72 | sn.setRight((node.elementAt(j))); |
110 | ||
111 | 72 | BinaryNode tmpi = (node.elementAt(i)); |
112 | 72 | BinaryNode tmpj = (node.elementAt(j)); |
113 | ||
114 | 72 | findNewDistances(tmpi, tmpj, dist); |
115 | ||
116 | 72 | tmpi.setParent(sn); |
117 | 72 | tmpj.setParent(sn); |
118 | ||
119 | 72 | node.setElementAt(sn, i); |
120 | ||
121 | /* | |
122 | * move the members of cluster(j) to cluster(i) | |
123 | * and mark cluster j as out of the game | |
124 | */ | |
125 | 72 | clusters.get(i).or(clusters.get(j)); |
126 | 72 | clusters.get(j).clear(); |
127 | 72 | done.set(j); |
128 | } | |
129 | ||
130 | protected abstract void findNewDistances(BinaryNode nodei, | |
131 | BinaryNode nodej, double previousDistance); | |
132 | ||
133 | /** | |
134 | * Calculates and saves the distance between the combination of cluster(i) and | |
135 | * cluster(j) and all other clusters. The form of the calculation depends on | |
136 | * the tree clustering method being used. | |
137 | * | |
138 | * @param i | |
139 | * @param j | |
140 | */ | |
141 | protected abstract void findClusterDistance(int i, int j); | |
142 | ||
143 | /** | |
144 | * Finds the node, at or below the given node, with the maximum distance, and | |
145 | * saves the node and the distance value | |
146 | * | |
147 | * @param nd | |
148 | */ | |
149 | 147 | protected void findMaxDist(BinaryNode nd) |
150 | { | |
151 | 147 | if (nd == null) |
152 | { | |
153 | 0 | return; |
154 | } | |
155 | ||
156 | 147 | if ((nd.left() == null) && (nd.right() == null)) |
157 | { | |
158 | 75 | double dist = nd.dist; |
159 | ||
160 | 75 | if (dist > maxDistValue) |
161 | { | |
162 | 12 | maxdist = nd; |
163 | 12 | maxDistValue = dist; |
164 | } | |
165 | } | |
166 | else | |
167 | { | |
168 | 72 | findMaxDist((BinaryNode) nd.left()); |
169 | 72 | findMaxDist((BinaryNode) nd.right()); |
170 | } | |
171 | } | |
172 | ||
173 | /** | |
174 | * Form clusters by grouping sub-clusters, starting from one sequence per | |
175 | * cluster, and finishing when only two clusters remain | |
176 | */ | |
177 | 3 | protected void cluster() |
178 | { | |
179 | 72 | while (noClus > 2) |
180 | { | |
181 | 69 | findMinDistance(); |
182 | ||
183 | 69 | joinClusters(mini, minj); |
184 | ||
185 | 69 | noClus--; |
186 | } | |
187 | ||
188 | 3 | int rightChild = done.nextClearBit(0); |
189 | 3 | int leftChild = done.nextClearBit(rightChild + 1); |
190 | ||
191 | 3 | joinClusters(leftChild, rightChild); |
192 | 3 | top = (node.elementAt(leftChild)); |
193 | ||
194 | 3 | reCount(top); |
195 | 3 | findHeight(top); |
196 | 3 | findMaxDist(top); |
197 | } | |
198 | ||
199 | /** | |
200 | * Returns the minimum distance between two clusters, and also sets the | |
201 | * indices of the clusters in fields mini and minj | |
202 | * | |
203 | * @return | |
204 | */ | |
205 | protected abstract double findMinDistance(); | |
206 | ||
207 | /** | |
208 | * DOCUMENT ME! | |
209 | * | |
210 | * @param nd | |
211 | * DOCUMENT ME! | |
212 | */ | |
213 | 147 | protected void _reCount(BinaryNode nd) |
214 | { | |
215 | // if (_lycount<_lylimit) | |
216 | // { | |
217 | // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than | |
218 | // number of | |
219 | // nodes."); | |
220 | // } | |
221 | 147 | if (nd == null) |
222 | { | |
223 | 0 | return; |
224 | } | |
225 | // _lycount++; | |
226 | ||
227 | 147 | if ((nd.left() != null) && (nd.right() != null)) |
228 | { | |
229 | ||
230 | 72 | _reCount(nd.left()); |
231 | 72 | _reCount((BinaryNode) nd.right()); |
232 | ||
233 | 72 | BinaryNode l = nd.left(); |
234 | 72 | BinaryNode r = nd.right(); |
235 | ||
236 | 72 | nd.count = l.count + r.count; |
237 | 72 | nd.ycount = (l.ycount + r.ycount) / 2; |
238 | } | |
239 | else | |
240 | { | |
241 | 75 | nd.count = 1; |
242 | 75 | nd.ycount = ycount++; |
243 | } | |
244 | // _lycount--; | |
245 | } | |
246 | ||
247 | /** | |
248 | * DOCUMENT ME! | |
249 | * | |
250 | * @param nd | |
251 | * DOCUMENT ME! | |
252 | * | |
253 | * @return DOCUMENT ME! | |
254 | */ | |
255 | 0 | double findHeight(BinaryNode nd) |
256 | { | |
257 | 0 | if (nd == null) |
258 | { | |
259 | 0 | return maxheight; |
260 | } | |
261 | ||
262 | 0 | if ((nd.left() == null) && (nd.right() == null)) |
263 | { | |
264 | 0 | nd.height = ((BinaryNode) nd.parent()).height + nd.dist; |
265 | ||
266 | 0 | if (nd.height > maxheight) |
267 | { | |
268 | 0 | return nd.height; |
269 | } | |
270 | else | |
271 | { | |
272 | 0 | return maxheight; |
273 | } | |
274 | } | |
275 | else | |
276 | { | |
277 | 0 | if (nd.parent() != null) |
278 | { | |
279 | 0 | nd.height = ((BinaryNode) nd.parent()).height + nd.dist; |
280 | } | |
281 | else | |
282 | { | |
283 | 0 | maxheight = 0; |
284 | 0 | nd.height = (float) 0.0; |
285 | } | |
286 | ||
287 | 0 | maxheight = findHeight((BinaryNode) (nd.left())); |
288 | 0 | maxheight = findHeight((BinaryNode) (nd.right())); |
289 | } | |
290 | ||
291 | 0 | return maxheight; |
292 | } | |
293 | ||
294 | /** | |
295 | * DOCUMENT ME! | |
296 | * | |
297 | * @param nd | |
298 | * DOCUMENT ME! | |
299 | */ | |
300 | 3 | void reCount(BinaryNode nd) |
301 | { | |
302 | 3 | ycount = 0; |
303 | // _lycount = 0; | |
304 | // _lylimit = this.node.size(); | |
305 | 3 | _reCount(nd); |
306 | } | |
307 | ||
308 | /** | |
309 | * DOCUMENT ME! | |
310 | * | |
311 | * @return DOCUMENT ME! | |
312 | */ | |
313 | 9 | public BinaryNode getTopNode() |
314 | { | |
315 | 9 | return top; |
316 | } | |
317 | ||
318 | } |