added help and documentation for annotation editing.
[jalview.git] / src / jalview / analysis / NJTree.java
1 /*\r
2 * Jalview - A Sequence Alignment Editor and Viewer\r
3 * Copyright (C) 2005 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
4 *\r
5 * This program is free software; you can redistribute it and/or\r
6 * modify it under the terms of the GNU General Public License\r
7 * as published by the Free Software Foundation; either version 2\r
8 * of the License, or (at your option) any later version.\r
9 *\r
10 * This program is distributed in the hope that it will be useful,\r
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
13 * GNU General Public License for more details.\r
14 *\r
15 * You should have received a copy of the GNU General Public License\r
16 * along with this program; if not, write to the Free Software\r
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
18 */\r
19 package jalview.analysis;\r
20 \r
21 import jalview.datamodel.*;\r
22 \r
23 import jalview.io.NewickFile;\r
24 \r
25 import jalview.schemes.ResidueProperties;\r
26 \r
27 import jalview.util.*;\r
28 \r
29 import java.util.*;\r
30 \r
31 \r
32 /**\r
33  * DOCUMENT ME!\r
34  *\r
35  * @author $author$\r
36  * @version $Revision$\r
37  */\r
38 public class NJTree\r
39 {\r
40     Vector cluster;\r
41     SequenceI[] sequence;\r
42     int[] done;\r
43     int noseqs;\r
44     int noClus;\r
45     float[][] distance;\r
46     int mini;\r
47     int minj;\r
48     float ri;\r
49     float rj;\r
50     Vector groups = new Vector();\r
51     SequenceNode maxdist;\r
52     SequenceNode top;\r
53     float maxDistValue;\r
54     float maxheight;\r
55     int ycount;\r
56     Vector node;\r
57     String type;\r
58     String pwtype;\r
59     Object found = null;\r
60     Object leaves = null;\r
61     int start;\r
62     int end;\r
63 \r
64     /**\r
65      * Creates a new NJTree object.\r
66      *\r
67      * @param node DOCUMENT ME!\r
68      */\r
69     public NJTree(SequenceNode node)\r
70     {\r
71         top = node;\r
72         maxheight = findHeight(top);\r
73     }\r
74 \r
75     /**\r
76      * Creates a new NJTree object.\r
77      *\r
78      * @param seqs DOCUMENT ME!\r
79      * @param treefile DOCUMENT ME!\r
80      */\r
81     public NJTree(SequenceI[] seqs, NewickFile treefile)\r
82     {\r
83         top = treefile.getTree();\r
84         maxheight = findHeight(top);\r
85 \r
86         SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);\r
87 \r
88         Vector leaves = new Vector();\r
89         findLeaves(top, leaves);\r
90 \r
91         int i = 0;\r
92         int namesleft = seqs.length;\r
93 \r
94         SequenceNode j;\r
95         SequenceI nam;\r
96         String realnam;\r
97 \r
98         while (i < leaves.size())\r
99         {\r
100             j = (SequenceNode) leaves.elementAt(i++);\r
101             realnam = j.getName();\r
102             nam = null;\r
103 \r
104             if (namesleft > -1)\r
105             {\r
106                 nam = algnIds.findIdMatch(realnam);\r
107             }\r
108 \r
109             if (nam != null)\r
110             {\r
111                 j.setElement(nam);\r
112                 namesleft--;\r
113             }\r
114             else\r
115             {\r
116                 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));\r
117                 j.setPlaceholder(true);\r
118             }\r
119         }\r
120     }\r
121 \r
122     /**\r
123      * Creates a new NJTree object.\r
124      *\r
125      * @param sequence DOCUMENT ME!\r
126      * @param start DOCUMENT ME!\r
127      * @param end DOCUMENT ME!\r
128      */\r
129     public NJTree(SequenceI[] sequence, int start, int end)\r
130     {\r
131         this(sequence, "NJ", "BL", start, end);\r
132     }\r
133 \r
134     /**\r
135      * Creates a new NJTree object.\r
136      *\r
137      * @param sequence DOCUMENT ME!\r
138      * @param type DOCUMENT ME!\r
139      * @param pwtype DOCUMENT ME!\r
140      * @param start DOCUMENT ME!\r
141      * @param end DOCUMENT ME!\r
142      */\r
143     public NJTree(SequenceI[] sequence, String type, String pwtype, int start,\r
144         int end)\r
145     {\r
146         this.sequence = sequence;\r
147         this.node = new Vector();\r
148         this.type = type;\r
149         this.pwtype = pwtype;\r
150         this.start = start;\r
151         this.end = end;\r
152 \r
153         if (!(type.equals("NJ")))\r
154         {\r
155             type = "AV";\r
156         }\r
157 \r
158         if (!(pwtype.equals("PID")))\r
159         {\r
160             type = "BL";\r
161         }\r
162 \r
163         int i = 0;\r
164 \r
165         done = new int[sequence.length];\r
166 \r
167         while ((i < sequence.length) && (sequence[i] != null))\r
168         {\r
169             done[i] = 0;\r
170             i++;\r
171         }\r
172 \r
173         noseqs = i++;\r
174 \r
175         distance = findDistances();\r
176 \r
177         makeLeaves();\r
178 \r
179         noClus = cluster.size();\r
180 \r
181         cluster();\r
182     }\r
183 \r
184     /**\r
185      * DOCUMENT ME!\r
186      *\r
187      * @return DOCUMENT ME!\r
188      */\r
189     public String toString()\r
190     {\r
191         jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());\r
192 \r
193         return fout.print(false, true); // distances only\r
194     }\r
195 \r
196     /**\r
197      *\r
198      * used when the alignment associated to a tree has changed.\r
199      *\r
200      * @param alignment Vector\r
201      */\r
202     public void UpdatePlaceHolders(Vector alignment)\r
203     {\r
204         Vector leaves = new Vector();\r
205         findLeaves(top, leaves);\r
206 \r
207         int sz = leaves.size();\r
208         SequenceIdMatcher seqmatcher = null;\r
209         int i = 0;\r
210 \r
211         while (i < sz)\r
212         {\r
213             SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
214 \r
215             if (alignment.contains(leaf.element()))\r
216             {\r
217                 leaf.setPlaceholder(false);\r
218             }\r
219             else\r
220             {\r
221                 if (seqmatcher == null)\r
222                 {\r
223                     // Only create this the first time we need it\r
224                     SequenceI[] seqs = new SequenceI[alignment.size()];\r
225 \r
226                     for (int j = 0; j < seqs.length; j++)\r
227                         seqs[j] = (SequenceI) alignment.elementAt(j);\r
228 \r
229                     seqmatcher = new SequenceIdMatcher(seqs);\r
230                 }\r
231 \r
232                 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());\r
233 \r
234                 if (nam != null)\r
235                 {\r
236                     leaf.setPlaceholder(false);\r
237                     leaf.setElement(nam);\r
238                 }\r
239                 else\r
240                 {\r
241                     leaf.setPlaceholder(true);\r
242                 }\r
243             }\r
244         }\r
245     }\r
246 \r
247     /**\r
248      * DOCUMENT ME!\r
249      */\r
250     public void cluster()\r
251     {\r
252         while (noClus > 2)\r
253         {\r
254             if (type.equals("NJ"))\r
255             {\r
256                 float mind = findMinNJDistance();\r
257             }\r
258             else\r
259             {\r
260                 float mind = findMinDistance();\r
261             }\r
262 \r
263             Cluster c = joinClusters(mini, minj);\r
264 \r
265             done[minj] = 1;\r
266 \r
267             cluster.setElementAt(null, minj);\r
268             cluster.setElementAt(c, mini);\r
269 \r
270             noClus--;\r
271         }\r
272 \r
273         boolean onefound = false;\r
274 \r
275         int one = -1;\r
276         int two = -1;\r
277 \r
278         for (int i = 0; i < noseqs; i++)\r
279         {\r
280             if (done[i] != 1)\r
281             {\r
282                 if (onefound == false)\r
283                 {\r
284                     two = i;\r
285                     onefound = true;\r
286                 }\r
287                 else\r
288                 {\r
289                     one = i;\r
290                 }\r
291             }\r
292         }\r
293 \r
294         Cluster c = joinClusters(one, two);\r
295         top = (SequenceNode) (node.elementAt(one));\r
296 \r
297         reCount(top);\r
298         findHeight(top);\r
299         findMaxDist(top);\r
300     }\r
301 \r
302     /**\r
303      * DOCUMENT ME!\r
304      *\r
305      * @param i DOCUMENT ME!\r
306      * @param j DOCUMENT ME!\r
307      *\r
308      * @return DOCUMENT ME!\r
309      */\r
310     public Cluster joinClusters(int i, int j)\r
311     {\r
312         float dist = distance[i][j];\r
313 \r
314         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
315         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
316 \r
317         int[] value = new int[noi + noj];\r
318 \r
319         for (int ii = 0; ii < noi; ii++)\r
320         {\r
321             value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];\r
322         }\r
323 \r
324         for (int ii = noi; ii < (noi + noj); ii++)\r
325         {\r
326             value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];\r
327         }\r
328 \r
329         Cluster c = new Cluster(value);\r
330 \r
331         ri = findr(i, j);\r
332         rj = findr(j, i);\r
333 \r
334         if (type.equals("NJ"))\r
335         {\r
336             findClusterNJDistance(i, j);\r
337         }\r
338         else\r
339         {\r
340             findClusterDistance(i, j);\r
341         }\r
342 \r
343         SequenceNode sn = new SequenceNode();\r
344 \r
345         sn.setLeft((SequenceNode) (node.elementAt(i)));\r
346         sn.setRight((SequenceNode) (node.elementAt(j)));\r
347 \r
348         SequenceNode tmpi = (SequenceNode) (node.elementAt(i));\r
349         SequenceNode tmpj = (SequenceNode) (node.elementAt(j));\r
350 \r
351         if (type.equals("NJ"))\r
352         {\r
353             findNewNJDistances(tmpi, tmpj, dist);\r
354         }\r
355         else\r
356         {\r
357             findNewDistances(tmpi, tmpj, dist);\r
358         }\r
359 \r
360         tmpi.setParent(sn);\r
361         tmpj.setParent(sn);\r
362 \r
363         node.setElementAt(sn, i);\r
364 \r
365         return c;\r
366     }\r
367 \r
368     /**\r
369      * DOCUMENT ME!\r
370      *\r
371      * @param tmpi DOCUMENT ME!\r
372      * @param tmpj DOCUMENT ME!\r
373      * @param dist DOCUMENT ME!\r
374      */\r
375     public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,\r
376         float dist)\r
377     {\r
378         float ih = 0;\r
379         float jh = 0;\r
380 \r
381         SequenceNode sni = tmpi;\r
382         SequenceNode snj = tmpj;\r
383 \r
384         tmpi.dist = ((dist + ri) - rj) / 2;\r
385         tmpj.dist = (dist - tmpi.dist);\r
386 \r
387         if (tmpi.dist < 0)\r
388         {\r
389             tmpi.dist = 0;\r
390         }\r
391 \r
392         if (tmpj.dist < 0)\r
393         {\r
394             tmpj.dist = 0;\r
395         }\r
396     }\r
397 \r
398     /**\r
399      * DOCUMENT ME!\r
400      *\r
401      * @param tmpi DOCUMENT ME!\r
402      * @param tmpj DOCUMENT ME!\r
403      * @param dist DOCUMENT ME!\r
404      */\r
405     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,\r
406         float dist)\r
407     {\r
408         float ih = 0;\r
409         float jh = 0;\r
410 \r
411         SequenceNode sni = tmpi;\r
412         SequenceNode snj = tmpj;\r
413 \r
414         while (sni != null)\r
415         {\r
416             ih = ih + sni.dist;\r
417             sni = (SequenceNode) sni.left();\r
418         }\r
419 \r
420         while (snj != null)\r
421         {\r
422             jh = jh + snj.dist;\r
423             snj = (SequenceNode) snj.left();\r
424         }\r
425 \r
426         tmpi.dist = ((dist / 2) - ih);\r
427         tmpj.dist = ((dist / 2) - jh);\r
428     }\r
429 \r
430     /**\r
431      * DOCUMENT ME!\r
432      *\r
433      * @param i DOCUMENT ME!\r
434      * @param j DOCUMENT ME!\r
435      */\r
436     public void findClusterDistance(int i, int j)\r
437     {\r
438         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
439         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
440 \r
441         // New distances from cluster to others\r
442         float[] newdist = new float[noseqs];\r
443 \r
444         for (int l = 0; l < noseqs; l++)\r
445         {\r
446             if ((l != i) && (l != j))\r
447             {\r
448                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +\r
449                     noj);\r
450             }\r
451             else\r
452             {\r
453                 newdist[l] = 0;\r
454             }\r
455         }\r
456 \r
457         for (int ii = 0; ii < noseqs; ii++)\r
458         {\r
459             distance[i][ii] = newdist[ii];\r
460             distance[ii][i] = newdist[ii];\r
461         }\r
462     }\r
463 \r
464     /**\r
465      * DOCUMENT ME!\r
466      *\r
467      * @param i DOCUMENT ME!\r
468      * @param j DOCUMENT ME!\r
469      */\r
470     public void findClusterNJDistance(int i, int j)\r
471     {\r
472         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
473         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
474 \r
475         // New distances from cluster to others\r
476         float[] newdist = new float[noseqs];\r
477 \r
478         for (int l = 0; l < noseqs; l++)\r
479         {\r
480             if ((l != i) && (l != j))\r
481             {\r
482                 newdist[l] = ((distance[i][l] + distance[j][l]) -\r
483                     distance[i][j]) / 2;\r
484             }\r
485             else\r
486             {\r
487                 newdist[l] = 0;\r
488             }\r
489         }\r
490 \r
491         for (int ii = 0; ii < noseqs; ii++)\r
492         {\r
493             distance[i][ii] = newdist[ii];\r
494             distance[ii][i] = newdist[ii];\r
495         }\r
496     }\r
497 \r
498     /**\r
499      * DOCUMENT ME!\r
500      *\r
501      * @param i DOCUMENT ME!\r
502      * @param j DOCUMENT ME!\r
503      *\r
504      * @return DOCUMENT ME!\r
505      */\r
506     public float findr(int i, int j)\r
507     {\r
508         float tmp = 1;\r
509 \r
510         for (int k = 0; k < noseqs; k++)\r
511         {\r
512             if ((k != i) && (k != j) && (done[k] != 1))\r
513             {\r
514                 tmp = tmp + distance[i][k];\r
515             }\r
516         }\r
517 \r
518         if (noClus > 2)\r
519         {\r
520             tmp = tmp / (noClus - 2);\r
521         }\r
522 \r
523         return tmp;\r
524     }\r
525 \r
526     /**\r
527      * DOCUMENT ME!\r
528      *\r
529      * @return DOCUMENT ME!\r
530      */\r
531     public float findMinNJDistance()\r
532     {\r
533         float min = 100000;\r
534 \r
535         for (int i = 0; i < (noseqs - 1); i++)\r
536         {\r
537             for (int j = i + 1; j < noseqs; j++)\r
538             {\r
539                 if ((done[i] != 1) && (done[j] != 1))\r
540                 {\r
541                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));\r
542 \r
543                     if (tmp < min)\r
544                     {\r
545                         mini = i;\r
546                         minj = j;\r
547 \r
548                         min = tmp;\r
549                     }\r
550                 }\r
551             }\r
552         }\r
553 \r
554         return min;\r
555     }\r
556 \r
557     /**\r
558      * DOCUMENT ME!\r
559      *\r
560      * @return DOCUMENT ME!\r
561      */\r
562     public float findMinDistance()\r
563     {\r
564         float min = 100000;\r
565 \r
566         for (int i = 0; i < (noseqs - 1); i++)\r
567         {\r
568             for (int j = i + 1; j < noseqs; j++)\r
569             {\r
570                 if ((done[i] != 1) && (done[j] != 1))\r
571                 {\r
572                     if (distance[i][j] < min)\r
573                     {\r
574                         mini = i;\r
575                         minj = j;\r
576 \r
577                         min = distance[i][j];\r
578                     }\r
579                 }\r
580             }\r
581         }\r
582 \r
583         return min;\r
584     }\r
585 \r
586     /**\r
587      * DOCUMENT ME!\r
588      *\r
589      * @return DOCUMENT ME!\r
590      */\r
591     public float[][] findDistances()\r
592     {\r
593         float[][] distance = new float[noseqs][noseqs];\r
594 \r
595         if (pwtype.equals("PID"))\r
596         {\r
597             for (int i = 0; i < (noseqs - 1); i++)\r
598             {\r
599                 for (int j = i; j < noseqs; j++)\r
600                 {\r
601                     if (j == i)\r
602                     {\r
603                         distance[i][i] = 0;\r
604                     }\r
605                     else\r
606                     {\r
607                         distance[i][j] = 100 -\r
608                             Comparison.PID(sequence[i], sequence[j], start, end);\r
609                         distance[j][i] = distance[i][j];\r
610                     }\r
611                 }\r
612             }\r
613         }\r
614         else if (pwtype.equals("BL"))\r
615         {\r
616             int maxscore = 0;\r
617 \r
618             for (int i = 0; i < (noseqs - 1); i++)\r
619             {\r
620                 for (int j = i; j < noseqs; j++)\r
621                 {\r
622                     int score = 0;\r
623 \r
624                     for (int k = start; k < end; k++)\r
625                     {\r
626                         try\r
627                         {\r
628                             score += ResidueProperties.getBLOSUM62(sequence[i].getSequence(\r
629                                     k, k + 1), sequence[j].getSequence(k, k +\r
630                                     1));\r
631                         }\r
632                         catch (Exception ex)\r
633                         {\r
634                             System.err.println("err creating BLOSUM62 tree");\r
635                             ex.printStackTrace();\r
636                         }\r
637                     }\r
638 \r
639                     distance[i][j] = (float) score;\r
640 \r
641                     if (score > maxscore)\r
642                     {\r
643                         maxscore = score;\r
644                     }\r
645                 }\r
646             }\r
647 \r
648             for (int i = 0; i < (noseqs - 1); i++)\r
649             {\r
650                 for (int j = i; j < noseqs; j++)\r
651                 {\r
652                     distance[i][j] = (float) maxscore - distance[i][j];\r
653                     distance[j][i] = distance[i][j];\r
654                 }\r
655             }\r
656         }\r
657         else if (pwtype.equals("SW"))\r
658         {\r
659             float max = -1;\r
660 \r
661             for (int i = 0; i < (noseqs - 1); i++)\r
662             {\r
663                 for (int j = i; j < noseqs; j++)\r
664                 {\r
665                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");\r
666                     as.calcScoreMatrix();\r
667                     as.traceAlignment();\r
668                     as.printAlignment();\r
669                     distance[i][j] = (float) as.maxscore;\r
670 \r
671                     if (max < distance[i][j])\r
672                     {\r
673                         max = distance[i][j];\r
674                     }\r
675                 }\r
676             }\r
677 \r
678             for (int i = 0; i < (noseqs - 1); i++)\r
679             {\r
680                 for (int j = i; j < noseqs; j++)\r
681                 {\r
682                     distance[i][j] = max - distance[i][j];\r
683                     distance[j][i] = distance[i][j];\r
684                 }\r
685             }\r
686         }\r
687 \r
688         return distance;\r
689     }\r
690 \r
691     /**\r
692      * DOCUMENT ME!\r
693      */\r
694     public void makeLeaves()\r
695     {\r
696         cluster = new Vector();\r
697 \r
698         for (int i = 0; i < noseqs; i++)\r
699         {\r
700             SequenceNode sn = new SequenceNode();\r
701 \r
702             sn.setElement(sequence[i]);\r
703             sn.setName(sequence[i].getName());\r
704             node.addElement(sn);\r
705 \r
706             int[] value = new int[1];\r
707             value[0] = i;\r
708 \r
709             Cluster c = new Cluster(value);\r
710             cluster.addElement(c);\r
711         }\r
712     }\r
713 \r
714     /**\r
715      * DOCUMENT ME!\r
716      *\r
717      * @param node DOCUMENT ME!\r
718      * @param leaves DOCUMENT ME!\r
719      *\r
720      * @return DOCUMENT ME!\r
721      */\r
722     public Vector findLeaves(SequenceNode node, Vector leaves)\r
723     {\r
724         if (node == null)\r
725         {\r
726             return leaves;\r
727         }\r
728 \r
729         if ((node.left() == null) && (node.right() == null))\r
730         {\r
731             leaves.addElement(node);\r
732 \r
733             return leaves;\r
734         }\r
735         else\r
736         {\r
737             findLeaves((SequenceNode) node.left(), leaves);\r
738             findLeaves((SequenceNode) node.right(), leaves);\r
739         }\r
740 \r
741         return leaves;\r
742     }\r
743 \r
744     /**\r
745      * DOCUMENT ME!\r
746      *\r
747      * @param node DOCUMENT ME!\r
748      * @param count DOCUMENT ME!\r
749      *\r
750      * @return DOCUMENT ME!\r
751      */\r
752     public Object findLeaf(SequenceNode node, int count)\r
753     {\r
754         found = _findLeaf(node, count);\r
755 \r
756         return found;\r
757     }\r
758 \r
759     /**\r
760      * DOCUMENT ME!\r
761      *\r
762      * @param node DOCUMENT ME!\r
763      * @param count DOCUMENT ME!\r
764      *\r
765      * @return DOCUMENT ME!\r
766      */\r
767     public Object _findLeaf(SequenceNode node, int count)\r
768     {\r
769         if (node == null)\r
770         {\r
771             return null;\r
772         }\r
773 \r
774         if (node.ycount == count)\r
775         {\r
776             found = node.element();\r
777 \r
778             return found;\r
779         }\r
780         else\r
781         {\r
782             _findLeaf((SequenceNode) node.left(), count);\r
783             _findLeaf((SequenceNode) node.right(), count);\r
784         }\r
785 \r
786         return found;\r
787     }\r
788 \r
789     /**\r
790      * printNode is mainly for debugging purposes.\r
791      *\r
792      * @param node SequenceNode\r
793      */\r
794     public void printNode(SequenceNode node)\r
795     {\r
796         if (node == null)\r
797         {\r
798             return;\r
799         }\r
800 \r
801         if ((node.left() == null) && (node.right() == null))\r
802         {\r
803             System.out.println("Leaf = " +\r
804                 ((SequenceI) node.element()).getName());\r
805             System.out.println("Dist " + ((SequenceNode) node).dist);\r
806             System.out.println("Boot " + node.getBootstrap());\r
807         }\r
808         else\r
809         {\r
810             System.out.println("Dist " + ((SequenceNode) node).dist);\r
811             printNode((SequenceNode) node.left());\r
812             printNode((SequenceNode) node.right());\r
813         }\r
814     }\r
815 \r
816     /**\r
817      * DOCUMENT ME!\r
818      *\r
819      * @param node DOCUMENT ME!\r
820      */\r
821     public void findMaxDist(SequenceNode node)\r
822     {\r
823         if (node == null)\r
824         {\r
825             return;\r
826         }\r
827 \r
828         if ((node.left() == null) && (node.right() == null))\r
829         {\r
830             float dist = ((SequenceNode) node).dist;\r
831 \r
832             if (dist > maxDistValue)\r
833             {\r
834                 maxdist = (SequenceNode) node;\r
835                 maxDistValue = dist;\r
836             }\r
837         }\r
838         else\r
839         {\r
840             findMaxDist((SequenceNode) node.left());\r
841             findMaxDist((SequenceNode) node.right());\r
842         }\r
843     }\r
844 \r
845     /**\r
846      * DOCUMENT ME!\r
847      *\r
848      * @return DOCUMENT ME!\r
849      */\r
850     public Vector getGroups()\r
851     {\r
852         return groups;\r
853     }\r
854 \r
855     /**\r
856      * DOCUMENT ME!\r
857      *\r
858      * @return DOCUMENT ME!\r
859      */\r
860     public float getMaxHeight()\r
861     {\r
862         return maxheight;\r
863     }\r
864 \r
865     /**\r
866      * DOCUMENT ME!\r
867      *\r
868      * @param node DOCUMENT ME!\r
869      * @param threshold DOCUMENT ME!\r
870      */\r
871     public void groupNodes(SequenceNode node, float threshold)\r
872     {\r
873         if (node == null)\r
874         {\r
875             return;\r
876         }\r
877 \r
878         if ((node.height / maxheight) > threshold)\r
879         {\r
880             groups.addElement(node);\r
881         }\r
882         else\r
883         {\r
884             groupNodes((SequenceNode) node.left(), threshold);\r
885             groupNodes((SequenceNode) node.right(), threshold);\r
886         }\r
887     }\r
888 \r
889     /**\r
890      * DOCUMENT ME!\r
891      *\r
892      * @param node DOCUMENT ME!\r
893      *\r
894      * @return DOCUMENT ME!\r
895      */\r
896     public float findHeight(SequenceNode node)\r
897     {\r
898         if (node == null)\r
899         {\r
900             return maxheight;\r
901         }\r
902 \r
903         if ((node.left() == null) && (node.right() == null))\r
904         {\r
905             node.height = ((SequenceNode) node.parent()).height + node.dist;\r
906 \r
907             if (node.height > maxheight)\r
908             {\r
909                 return node.height;\r
910             }\r
911             else\r
912             {\r
913                 return maxheight;\r
914             }\r
915         }\r
916         else\r
917         {\r
918             if (node.parent() != null)\r
919             {\r
920                 node.height = ((SequenceNode) node.parent()).height +\r
921                     node.dist;\r
922             }\r
923             else\r
924             {\r
925                 maxheight = 0;\r
926                 node.height = (float) 0.0;\r
927             }\r
928 \r
929             maxheight = findHeight((SequenceNode) (node.left()));\r
930             maxheight = findHeight((SequenceNode) (node.right()));\r
931         }\r
932 \r
933         return maxheight;\r
934     }\r
935 \r
936     /**\r
937      * DOCUMENT ME!\r
938      *\r
939      * @return DOCUMENT ME!\r
940      */\r
941     public SequenceNode reRoot()\r
942     {\r
943         if (maxdist != null)\r
944         {\r
945             ycount = 0;\r
946 \r
947             float tmpdist = maxdist.dist;\r
948 \r
949             // New top\r
950             SequenceNode sn = new SequenceNode();\r
951             sn.setParent(null);\r
952 \r
953             // New right hand of top\r
954             SequenceNode snr = (SequenceNode) maxdist.parent();\r
955             changeDirection(snr, maxdist);\r
956             System.out.println("Printing reversed tree");\r
957             printN(snr);\r
958             snr.dist = tmpdist / 2;\r
959             maxdist.dist = tmpdist / 2;\r
960 \r
961             snr.setParent(sn);\r
962             maxdist.setParent(sn);\r
963 \r
964             sn.setRight(snr);\r
965             sn.setLeft(maxdist);\r
966 \r
967             top = sn;\r
968 \r
969             ycount = 0;\r
970             reCount(top);\r
971             findHeight(top);\r
972         }\r
973 \r
974         return top;\r
975     }\r
976 \r
977     /**\r
978      * DOCUMENT ME!\r
979      *\r
980      * @param node DOCUMENT ME!\r
981      */\r
982     public static void printN(SequenceNode node)\r
983     {\r
984         if (node == null)\r
985         {\r
986             return;\r
987         }\r
988 \r
989         if ((node.left() != null) && (node.right() != null))\r
990         {\r
991             printN((SequenceNode) node.left());\r
992             printN((SequenceNode) node.right());\r
993         }\r
994         else\r
995         {\r
996             System.out.println(" name = " +\r
997                 ((SequenceI) node.element()).getName());\r
998         }\r
999 \r
1000         System.out.println(" dist = " + ((SequenceNode) node).dist + " " +\r
1001             ((SequenceNode) node).count + " " + ((SequenceNode) node).height);\r
1002     }\r
1003 \r
1004     /**\r
1005      * DOCUMENT ME!\r
1006      *\r
1007      * @param node DOCUMENT ME!\r
1008      */\r
1009     public void reCount(SequenceNode node)\r
1010     {\r
1011         ycount = 0;\r
1012         _reCount(node);\r
1013     }\r
1014 \r
1015     /**\r
1016      * DOCUMENT ME!\r
1017      *\r
1018      * @param node DOCUMENT ME!\r
1019      */\r
1020     public void _reCount(SequenceNode node)\r
1021     {\r
1022         if (node == null)\r
1023         {\r
1024             return;\r
1025         }\r
1026 \r
1027         if ((node.left() != null) && (node.right() != null))\r
1028         {\r
1029             _reCount((SequenceNode) node.left());\r
1030             _reCount((SequenceNode) node.right());\r
1031 \r
1032             SequenceNode l = (SequenceNode) node.left();\r
1033             SequenceNode r = (SequenceNode) node.right();\r
1034 \r
1035             ((SequenceNode) node).count = l.count + r.count;\r
1036             ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;\r
1037         }\r
1038         else\r
1039         {\r
1040             ((SequenceNode) node).count = 1;\r
1041             ((SequenceNode) node).ycount = ycount++;\r
1042         }\r
1043     }\r
1044 \r
1045     /**\r
1046      * DOCUMENT ME!\r
1047      *\r
1048      * @param node DOCUMENT ME!\r
1049      */\r
1050     public void swapNodes(SequenceNode node)\r
1051     {\r
1052         if (node == null)\r
1053         {\r
1054             return;\r
1055         }\r
1056 \r
1057         SequenceNode tmp = (SequenceNode) node.left();\r
1058 \r
1059         node.setLeft(node.right());\r
1060         node.setRight(tmp);\r
1061     }\r
1062 \r
1063     /**\r
1064      * DOCUMENT ME!\r
1065      *\r
1066      * @param node DOCUMENT ME!\r
1067      * @param dir DOCUMENT ME!\r
1068      */\r
1069     public void changeDirection(SequenceNode node, SequenceNode dir)\r
1070     {\r
1071         if (node == null)\r
1072         {\r
1073             return;\r
1074         }\r
1075 \r
1076         if (node.parent() != top)\r
1077         {\r
1078             changeDirection((SequenceNode) node.parent(), node);\r
1079 \r
1080             SequenceNode tmp = (SequenceNode) node.parent();\r
1081 \r
1082             if (dir == node.left())\r
1083             {\r
1084                 node.setParent(dir);\r
1085                 node.setLeft(tmp);\r
1086             }\r
1087             else if (dir == node.right())\r
1088             {\r
1089                 node.setParent(dir);\r
1090                 node.setRight(tmp);\r
1091             }\r
1092         }\r
1093         else\r
1094         {\r
1095             if (dir == node.left())\r
1096             {\r
1097                 node.setParent(node.left());\r
1098 \r
1099                 if (top.left() == node)\r
1100                 {\r
1101                     node.setRight(top.right());\r
1102                 }\r
1103                 else\r
1104                 {\r
1105                     node.setRight(top.left());\r
1106                 }\r
1107             }\r
1108             else\r
1109             {\r
1110                 node.setParent(node.right());\r
1111 \r
1112                 if (top.left() == node)\r
1113                 {\r
1114                     node.setLeft(top.right());\r
1115                 }\r
1116                 else\r
1117                 {\r
1118                     node.setLeft(top.left());\r
1119                 }\r
1120             }\r
1121         }\r
1122     }\r
1123 \r
1124     /**\r
1125      * DOCUMENT ME!\r
1126      *\r
1127      * @param node DOCUMENT ME!\r
1128      */\r
1129     public void setMaxDist(SequenceNode node)\r
1130     {\r
1131         this.maxdist = maxdist;\r
1132     }\r
1133 \r
1134     /**\r
1135      * DOCUMENT ME!\r
1136      *\r
1137      * @return DOCUMENT ME!\r
1138      */\r
1139     public SequenceNode getMaxDist()\r
1140     {\r
1141         return maxdist;\r
1142     }\r
1143 \r
1144     /**\r
1145      * DOCUMENT ME!\r
1146      *\r
1147      * @return DOCUMENT ME!\r
1148      */\r
1149     public SequenceNode getTopNode()\r
1150     {\r
1151         return top;\r
1152     }\r
1153 }\r
1154 \r
1155 \r
1156 /**\r
1157  * DOCUMENT ME!\r
1158  *\r
1159  * @author $author$\r
1160  * @version $Revision$\r
1161  */\r
1162 class Cluster\r
1163 {\r
1164     int[] value;\r
1165 \r
1166     /**\r
1167      * Creates a new Cluster object.\r
1168      *\r
1169      * @param value DOCUMENT ME!\r
1170      */\r
1171     public Cluster(int[] value)\r
1172     {\r
1173         this.value = value;\r
1174     }\r
1175 }\r