Readline instead of bit by bit
[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     CigarArray 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, CigarArray 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                   CigarArray 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             this.seqData = new CigarArray(seqs);\r
188             this.seqData.addOperation(CigarArray.M, end-start+1);\r
189         }\r
190 \r
191         if (!(type.equals("NJ")))\r
192         {\r
193             type = "AV";\r
194         }\r
195 \r
196         if (!(pwtype.equals("PID")))\r
197         {\r
198             type = "BL";\r
199         }\r
200 \r
201         int i = 0;\r
202 \r
203         done = new int[sequence.length];\r
204 \r
205         while ((i < sequence.length) && (sequence[i] != null))\r
206         {\r
207             done[i] = 0;\r
208             i++;\r
209         }\r
210 \r
211         noseqs = i++;\r
212 \r
213         distance = findDistances(this.seqData.getSequenceStrings(Comparison.GapChars.charAt(0)));\r
214 \r
215         makeLeaves();\r
216 \r
217         noClus = cluster.size();\r
218 \r
219         cluster();\r
220     }\r
221 \r
222     /**\r
223      * DOCUMENT ME!\r
224      *\r
225      * @return DOCUMENT ME!\r
226      */\r
227     public String toString()\r
228     {\r
229         jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());\r
230 \r
231         return fout.print(false, true); // distances only\r
232     }\r
233 \r
234     /**\r
235      *\r
236      * used when the alignment associated to a tree has changed.\r
237      *\r
238      * @param alignment Vector\r
239      */\r
240     public void UpdatePlaceHolders(Vector alignment)\r
241     {\r
242         Vector leaves = new Vector();\r
243         findLeaves(top, leaves);\r
244 \r
245         int sz = leaves.size();\r
246         SequenceIdMatcher seqmatcher = null;\r
247         int i = 0;\r
248 \r
249         while (i < sz)\r
250         {\r
251             SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
252 \r
253             if (alignment.contains(leaf.element()))\r
254             {\r
255                 leaf.setPlaceholder(false);\r
256             }\r
257             else\r
258             {\r
259                 if (seqmatcher == null)\r
260                 {\r
261                     // Only create this the first time we need it\r
262                     SequenceI[] seqs = new SequenceI[alignment.size()];\r
263 \r
264                     for (int j = 0; j < seqs.length; j++)\r
265                         seqs[j] = (SequenceI) alignment.elementAt(j);\r
266 \r
267                     seqmatcher = new SequenceIdMatcher(seqs);\r
268                 }\r
269 \r
270                 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());\r
271 \r
272                 if (nam != null)\r
273                 {\r
274                     leaf.setPlaceholder(false);\r
275                     leaf.setElement(nam);\r
276                 }\r
277                 else\r
278                 {\r
279                     leaf.setPlaceholder(true);\r
280                 }\r
281             }\r
282         }\r
283     }\r
284 \r
285     /**\r
286      * DOCUMENT ME!\r
287      */\r
288     public void cluster()\r
289     {\r
290         while (noClus > 2)\r
291         {\r
292             if (type.equals("NJ"))\r
293             {\r
294                 findMinNJDistance();\r
295             }\r
296             else\r
297             {\r
298                 findMinDistance();\r
299             }\r
300 \r
301             Cluster c = joinClusters(mini, minj);\r
302 \r
303             done[minj] = 1;\r
304 \r
305             cluster.setElementAt(null, minj);\r
306             cluster.setElementAt(c, mini);\r
307 \r
308             noClus--;\r
309         }\r
310 \r
311         boolean onefound = false;\r
312 \r
313         int one = -1;\r
314         int two = -1;\r
315 \r
316         for (int i = 0; i < noseqs; i++)\r
317         {\r
318             if (done[i] != 1)\r
319             {\r
320                 if (onefound == false)\r
321                 {\r
322                     two = i;\r
323                     onefound = true;\r
324                 }\r
325                 else\r
326                 {\r
327                     one = i;\r
328                 }\r
329             }\r
330         }\r
331 \r
332         joinClusters(one, two);\r
333         top = (SequenceNode) (node.elementAt(one));\r
334 \r
335         reCount(top);\r
336         findHeight(top);\r
337         findMaxDist(top);\r
338     }\r
339 \r
340     /**\r
341      * DOCUMENT ME!\r
342      *\r
343      * @param i DOCUMENT ME!\r
344      * @param j DOCUMENT ME!\r
345      *\r
346      * @return DOCUMENT ME!\r
347      */\r
348     public Cluster joinClusters(int i, int j)\r
349     {\r
350         float dist = distance[i][j];\r
351 \r
352         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
353         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
354 \r
355         int[] value = new int[noi + noj];\r
356 \r
357         for (int ii = 0; ii < noi; ii++)\r
358         {\r
359             value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];\r
360         }\r
361 \r
362         for (int ii = noi; ii < (noi + noj); ii++)\r
363         {\r
364             value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];\r
365         }\r
366 \r
367         Cluster c = new Cluster(value);\r
368 \r
369         ri = findr(i, j);\r
370         rj = findr(j, i);\r
371 \r
372         if (type.equals("NJ"))\r
373         {\r
374             findClusterNJDistance(i, j);\r
375         }\r
376         else\r
377         {\r
378             findClusterDistance(i, j);\r
379         }\r
380 \r
381         SequenceNode sn = new SequenceNode();\r
382 \r
383         sn.setLeft((SequenceNode) (node.elementAt(i)));\r
384         sn.setRight((SequenceNode) (node.elementAt(j)));\r
385 \r
386         SequenceNode tmpi = (SequenceNode) (node.elementAt(i));\r
387         SequenceNode tmpj = (SequenceNode) (node.elementAt(j));\r
388 \r
389         if (type.equals("NJ"))\r
390         {\r
391             findNewNJDistances(tmpi, tmpj, dist);\r
392         }\r
393         else\r
394         {\r
395             findNewDistances(tmpi, tmpj, dist);\r
396         }\r
397 \r
398         tmpi.setParent(sn);\r
399         tmpj.setParent(sn);\r
400 \r
401         node.setElementAt(sn, i);\r
402 \r
403         return c;\r
404     }\r
405 \r
406     /**\r
407      * DOCUMENT ME!\r
408      *\r
409      * @param tmpi DOCUMENT ME!\r
410      * @param tmpj DOCUMENT ME!\r
411      * @param dist DOCUMENT ME!\r
412      */\r
413     public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,\r
414         float dist)\r
415     {\r
416 \r
417         tmpi.dist = ((dist + ri) - rj) / 2;\r
418         tmpj.dist = (dist - tmpi.dist);\r
419 \r
420         if (tmpi.dist < 0)\r
421         {\r
422             tmpi.dist = 0;\r
423         }\r
424 \r
425         if (tmpj.dist < 0)\r
426         {\r
427             tmpj.dist = 0;\r
428         }\r
429     }\r
430 \r
431     /**\r
432      * DOCUMENT ME!\r
433      *\r
434      * @param tmpi DOCUMENT ME!\r
435      * @param tmpj DOCUMENT ME!\r
436      * @param dist DOCUMENT ME!\r
437      */\r
438     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,\r
439         float dist)\r
440     {\r
441         float ih = 0;\r
442         float jh = 0;\r
443 \r
444         SequenceNode sni = tmpi;\r
445         SequenceNode snj = tmpj;\r
446 \r
447         while (sni != null)\r
448         {\r
449             ih = ih + sni.dist;\r
450             sni = (SequenceNode) sni.left();\r
451         }\r
452 \r
453         while (snj != null)\r
454         {\r
455             jh = jh + snj.dist;\r
456             snj = (SequenceNode) snj.left();\r
457         }\r
458 \r
459         tmpi.dist = ((dist / 2) - ih);\r
460         tmpj.dist = ((dist / 2) - jh);\r
461     }\r
462 \r
463     /**\r
464      * DOCUMENT ME!\r
465      *\r
466      * @param i DOCUMENT ME!\r
467      * @param j DOCUMENT ME!\r
468      */\r
469     public void findClusterDistance(int i, int j)\r
470     {\r
471         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
472         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
473 \r
474         // New distances from cluster to others\r
475         float[] newdist = new float[noseqs];\r
476 \r
477         for (int l = 0; l < noseqs; l++)\r
478         {\r
479             if ((l != i) && (l != j))\r
480             {\r
481                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +\r
482                     noj);\r
483             }\r
484             else\r
485             {\r
486                 newdist[l] = 0;\r
487             }\r
488         }\r
489 \r
490         for (int ii = 0; ii < noseqs; ii++)\r
491         {\r
492             distance[i][ii] = newdist[ii];\r
493             distance[ii][i] = newdist[ii];\r
494         }\r
495     }\r
496 \r
497     /**\r
498      * DOCUMENT ME!\r
499      *\r
500      * @param i DOCUMENT ME!\r
501      * @param j DOCUMENT ME!\r
502      */\r
503     public void findClusterNJDistance(int i, int j)\r
504     {\r
505 \r
506         // New distances from cluster to others\r
507         float[] newdist = new float[noseqs];\r
508 \r
509         for (int l = 0; l < noseqs; l++)\r
510         {\r
511             if ((l != i) && (l != j))\r
512             {\r
513                 newdist[l] = ((distance[i][l] + distance[j][l]) -\r
514                     distance[i][j]) / 2;\r
515             }\r
516             else\r
517             {\r
518                 newdist[l] = 0;\r
519             }\r
520         }\r
521 \r
522         for (int ii = 0; ii < noseqs; ii++)\r
523         {\r
524             distance[i][ii] = newdist[ii];\r
525             distance[ii][i] = newdist[ii];\r
526         }\r
527     }\r
528 \r
529     /**\r
530      * DOCUMENT ME!\r
531      *\r
532      * @param i DOCUMENT ME!\r
533      * @param j DOCUMENT ME!\r
534      *\r
535      * @return DOCUMENT ME!\r
536      */\r
537     public float findr(int i, int j)\r
538     {\r
539         float tmp = 1;\r
540 \r
541         for (int k = 0; k < noseqs; k++)\r
542         {\r
543             if ((k != i) && (k != j) && (done[k] != 1))\r
544             {\r
545                 tmp = tmp + distance[i][k];\r
546             }\r
547         }\r
548 \r
549         if (noClus > 2)\r
550         {\r
551             tmp = tmp / (noClus - 2);\r
552         }\r
553 \r
554         return tmp;\r
555     }\r
556 \r
557     /**\r
558      * DOCUMENT ME!\r
559      *\r
560      * @return DOCUMENT ME!\r
561      */\r
562     public float findMinNJDistance()\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                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));\r
573 \r
574                     if (tmp < min)\r
575                     {\r
576                         mini = i;\r
577                         minj = j;\r
578 \r
579                         min = tmp;\r
580                     }\r
581                 }\r
582             }\r
583         }\r
584 \r
585         return min;\r
586     }\r
587 \r
588     /**\r
589      * DOCUMENT ME!\r
590      *\r
591      * @return DOCUMENT ME!\r
592      */\r
593     public float findMinDistance()\r
594     {\r
595         float min = 100000;\r
596 \r
597         for (int i = 0; i < (noseqs - 1); i++)\r
598         {\r
599             for (int j = i + 1; j < noseqs; j++)\r
600             {\r
601                 if ((done[i] != 1) && (done[j] != 1))\r
602                 {\r
603                     if (distance[i][j] < min)\r
604                     {\r
605                         mini = i;\r
606                         minj = j;\r
607 \r
608                         min = distance[i][j];\r
609                     }\r
610                 }\r
611             }\r
612         }\r
613 \r
614         return min;\r
615     }\r
616 \r
617     /**\r
618      * DOCUMENT ME!\r
619      *\r
620      * @return DOCUMENT ME!\r
621      */\r
622     public float[][] findDistances(String[] sequenceString)\r
623     {\r
624         float[][] distance = new float[noseqs][noseqs];\r
625 \r
626         if (pwtype.equals("PID"))\r
627         {\r
628             for (int i = 0; i < (noseqs - 1); i++)\r
629             {\r
630                 for (int j = i; j < noseqs; j++)\r
631                 {\r
632                     if (j == i)\r
633                     {\r
634                         distance[i][i] = 0;\r
635                     }\r
636                     else\r
637                     {\r
638                         distance[i][j] = 100 -\r
639                              Comparison.PID(sequenceString[i], sequenceString[j]);\r
640 \r
641                         distance[j][i] = distance[i][j];\r
642                     }\r
643                 }\r
644             }\r
645         }\r
646         else if (pwtype.equals("BL"))\r
647         {\r
648             int maxscore = 0;\r
649             int end = sequenceString[0].length();\r
650             for (int i = 0; i < (noseqs - 1); i++)\r
651             {\r
652                 for (int j = i; j < noseqs; j++)\r
653                 {\r
654                     int score = 0;\r
655 \r
656                     for (int k = 0; k < end; k++)\r
657                     {\r
658                         try\r
659                         {\r
660                             score += ResidueProperties.getBLOSUM62(\r
661                               sequenceString[i].substring(k, k + 1),\r
662                               sequenceString[j].substring(k, k + 1));\r
663                         }\r
664                         catch (Exception ex)\r
665                         {\r
666                             System.err.println("err creating BLOSUM62 tree");\r
667                             ex.printStackTrace();\r
668                         }\r
669                     }\r
670 \r
671                     distance[i][j] = (float) score;\r
672 \r
673                     if (score > maxscore)\r
674                     {\r
675                         maxscore = score;\r
676                     }\r
677                 }\r
678             }\r
679 \r
680             for (int i = 0; i < (noseqs - 1); i++)\r
681             {\r
682                 for (int j = i; j < noseqs; j++)\r
683                 {\r
684                     distance[i][j] = (float) maxscore - distance[i][j];\r
685                     distance[j][i] = distance[i][j];\r
686                 }\r
687             }\r
688         }\r
689       /*  else if (pwtype.equals("SW"))\r
690         {\r
691             float max = -1;\r
692 \r
693             for (int i = 0; i < (noseqs - 1); i++)\r
694             {\r
695                 for (int j = i; j < noseqs; j++)\r
696                 {\r
697                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");\r
698                     as.calcScoreMatrix();\r
699                     as.traceAlignment();\r
700                     as.printAlignment(System.out);\r
701                     distance[i][j] = (float) as.maxscore;\r
702 \r
703                     if (max < distance[i][j])\r
704                     {\r
705                         max = distance[i][j];\r
706                     }\r
707                 }\r
708             }\r
709 \r
710             for (int i = 0; i < (noseqs - 1); i++)\r
711             {\r
712                 for (int j = i; j < noseqs; j++)\r
713                 {\r
714                     distance[i][j] = max - distance[i][j];\r
715                     distance[j][i] = distance[i][j];\r
716                 }\r
717             }\r
718         }/*/\r
719 \r
720         return distance;\r
721     }\r
722 \r
723     /**\r
724      * DOCUMENT ME!\r
725      */\r
726     public void makeLeaves()\r
727     {\r
728         cluster = new Vector();\r
729 \r
730         for (int i = 0; i < noseqs; i++)\r
731         {\r
732             SequenceNode sn = new SequenceNode();\r
733 \r
734             sn.setElement(sequence[i]);\r
735             sn.setName(sequence[i].getName());\r
736             node.addElement(sn);\r
737 \r
738             int[] value = new int[1];\r
739             value[0] = i;\r
740 \r
741             Cluster c = new Cluster(value);\r
742             cluster.addElement(c);\r
743         }\r
744     }\r
745 \r
746     /**\r
747      * DOCUMENT ME!\r
748      *\r
749      * @param node DOCUMENT ME!\r
750      * @param leaves DOCUMENT ME!\r
751      *\r
752      * @return DOCUMENT ME!\r
753      */\r
754     public Vector findLeaves(SequenceNode node, Vector leaves)\r
755     {\r
756         if (node == null)\r
757         {\r
758             return leaves;\r
759         }\r
760 \r
761         if ((node.left() == null) && (node.right() == null))\r
762         {\r
763             leaves.addElement(node);\r
764 \r
765             return leaves;\r
766         }\r
767         else\r
768         {\r
769             findLeaves((SequenceNode) node.left(), leaves);\r
770             findLeaves((SequenceNode) node.right(), leaves);\r
771         }\r
772 \r
773         return leaves;\r
774     }\r
775 \r
776     /**\r
777      * DOCUMENT ME!\r
778      *\r
779      * @param node DOCUMENT ME!\r
780      * @param count DOCUMENT ME!\r
781      *\r
782      * @return DOCUMENT ME!\r
783      */\r
784     public Object findLeaf(SequenceNode node, int count)\r
785     {\r
786         found = _findLeaf(node, count);\r
787 \r
788         return found;\r
789     }\r
790 \r
791     /**\r
792      * DOCUMENT ME!\r
793      *\r
794      * @param node DOCUMENT ME!\r
795      * @param count DOCUMENT ME!\r
796      *\r
797      * @return DOCUMENT ME!\r
798      */\r
799     public Object _findLeaf(SequenceNode node, int count)\r
800     {\r
801         if (node == null)\r
802         {\r
803             return null;\r
804         }\r
805 \r
806         if (node.ycount == count)\r
807         {\r
808             found = node.element();\r
809 \r
810             return found;\r
811         }\r
812         else\r
813         {\r
814             _findLeaf((SequenceNode) node.left(), count);\r
815             _findLeaf((SequenceNode) node.right(), count);\r
816         }\r
817 \r
818         return found;\r
819     }\r
820 \r
821     /**\r
822      * printNode is mainly for debugging purposes.\r
823      *\r
824      * @param node SequenceNode\r
825      */\r
826     public void printNode(SequenceNode node)\r
827     {\r
828         if (node == null)\r
829         {\r
830             return;\r
831         }\r
832 \r
833         if ((node.left() == null) && (node.right() == null))\r
834         {\r
835             System.out.println("Leaf = " +\r
836                 ((SequenceI) node.element()).getName());\r
837             System.out.println("Dist " + ((SequenceNode) node).dist);\r
838             System.out.println("Boot " + node.getBootstrap());\r
839         }\r
840         else\r
841         {\r
842             System.out.println("Dist " + ((SequenceNode) node).dist);\r
843             printNode((SequenceNode) node.left());\r
844             printNode((SequenceNode) node.right());\r
845         }\r
846     }\r
847 \r
848     /**\r
849      * DOCUMENT ME!\r
850      *\r
851      * @param node DOCUMENT ME!\r
852      */\r
853     public void findMaxDist(SequenceNode node)\r
854     {\r
855         if (node == null)\r
856         {\r
857             return;\r
858         }\r
859 \r
860         if ((node.left() == null) && (node.right() == null))\r
861         {\r
862             float dist = ((SequenceNode) node).dist;\r
863 \r
864             if (dist > maxDistValue)\r
865             {\r
866                 maxdist = (SequenceNode) node;\r
867                 maxDistValue = dist;\r
868             }\r
869         }\r
870         else\r
871         {\r
872             findMaxDist((SequenceNode) node.left());\r
873             findMaxDist((SequenceNode) node.right());\r
874         }\r
875     }\r
876 \r
877     /**\r
878      * DOCUMENT ME!\r
879      *\r
880      * @return DOCUMENT ME!\r
881      */\r
882     public Vector getGroups()\r
883     {\r
884         return groups;\r
885     }\r
886 \r
887     /**\r
888      * DOCUMENT ME!\r
889      *\r
890      * @return DOCUMENT ME!\r
891      */\r
892     public float getMaxHeight()\r
893     {\r
894         return maxheight;\r
895     }\r
896 \r
897     /**\r
898      * DOCUMENT ME!\r
899      *\r
900      * @param node DOCUMENT ME!\r
901      * @param threshold DOCUMENT ME!\r
902      */\r
903     public void groupNodes(SequenceNode node, float threshold)\r
904     {\r
905         if (node == null)\r
906         {\r
907             return;\r
908         }\r
909 \r
910         if ((node.height / maxheight) > threshold)\r
911         {\r
912             groups.addElement(node);\r
913         }\r
914         else\r
915         {\r
916             groupNodes((SequenceNode) node.left(), threshold);\r
917             groupNodes((SequenceNode) node.right(), threshold);\r
918         }\r
919     }\r
920 \r
921     /**\r
922      * DOCUMENT ME!\r
923      *\r
924      * @param node DOCUMENT ME!\r
925      *\r
926      * @return DOCUMENT ME!\r
927      */\r
928     public float findHeight(SequenceNode node)\r
929     {\r
930         if (node == null)\r
931         {\r
932             return maxheight;\r
933         }\r
934 \r
935         if ((node.left() == null) && (node.right() == null))\r
936         {\r
937             node.height = ((SequenceNode) node.parent()).height + node.dist;\r
938 \r
939             if (node.height > maxheight)\r
940             {\r
941                 return node.height;\r
942             }\r
943             else\r
944             {\r
945                 return maxheight;\r
946             }\r
947         }\r
948         else\r
949         {\r
950             if (node.parent() != null)\r
951             {\r
952                 node.height = ((SequenceNode) node.parent()).height +\r
953                     node.dist;\r
954             }\r
955             else\r
956             {\r
957                 maxheight = 0;\r
958                 node.height = (float) 0.0;\r
959             }\r
960 \r
961             maxheight = findHeight((SequenceNode) (node.left()));\r
962             maxheight = findHeight((SequenceNode) (node.right()));\r
963         }\r
964 \r
965         return maxheight;\r
966     }\r
967 \r
968     /**\r
969      * DOCUMENT ME!\r
970      *\r
971      * @return DOCUMENT ME!\r
972      */\r
973     public SequenceNode reRoot()\r
974     {\r
975         if (maxdist != null)\r
976         {\r
977             ycount = 0;\r
978 \r
979             float tmpdist = maxdist.dist;\r
980 \r
981             // New top\r
982             SequenceNode sn = new SequenceNode();\r
983             sn.setParent(null);\r
984 \r
985             // New right hand of top\r
986             SequenceNode snr = (SequenceNode) maxdist.parent();\r
987             changeDirection(snr, maxdist);\r
988             System.out.println("Printing reversed tree");\r
989             printN(snr);\r
990             snr.dist = tmpdist / 2;\r
991             maxdist.dist = tmpdist / 2;\r
992 \r
993             snr.setParent(sn);\r
994             maxdist.setParent(sn);\r
995 \r
996             sn.setRight(snr);\r
997             sn.setLeft(maxdist);\r
998 \r
999             top = sn;\r
1000 \r
1001             ycount = 0;\r
1002             reCount(top);\r
1003             findHeight(top);\r
1004         }\r
1005 \r
1006         return top;\r
1007     }\r
1008     /**\r
1009      *\r
1010      * @return true if original sequence data can be recovered\r
1011      */\r
1012     public boolean hasOriginalSequenceData() {\r
1013       return seqData!=null;\r
1014     }\r
1015     /**\r
1016      * Returns original alignment data used for calculation - or null where\r
1017      * not available.\r
1018      *\r
1019      * @return null or cut'n'pasteable alignment\r
1020      */\r
1021     public String printOriginalSequenceData()\r
1022     {\r
1023       if (seqData==null)\r
1024         return null;\r
1025 //      return seqData.getSequenceString(Comparison.GapChars[0]);\r
1026       StringBuffer sb = new StringBuffer();\r
1027       String[] seqdatas = seqData.getSequenceStrings(Comparison.GapChars.charAt(0));\r
1028       for(int i=0; i<seqdatas.length; i++)\r
1029       {\r
1030         sb.append(new jalview.util.Format("%-" + 15 + "s").form(\r
1031             sequence[i].getName()));\r
1032         sb.append(" "+seqdatas[i]+"\n");\r
1033       }\r
1034       return sb.toString();\r
1035     }\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