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