formatting
[jalview.git] / src / jalview / analysis / NJTree.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.7)
3  * Copyright (C) 2011 J Procter, AM Waterhouse, J Engelhardt, LM Lui, G Barton, M Clamp, S Searle
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
10  * 
11  * Jalview is distributed in the hope that it will be useful, but 
12  * WITHOUT ANY WARRANTY; without even the implied warranty 
13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
14  * PURPOSE.  See the GNU General Public License for more details.
15  * 
16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 package jalview.analysis;
19
20 import java.util.*;
21
22 import jalview.datamodel.*;
23 import jalview.io.*;
24 import jalview.schemes.*;
25 import jalview.util.*;
26
27 /**
28  * DOCUMENT ME!
29  * 
30  * @author $author$
31  * @version $Revision$
32  */
33 public class NJTree
34 {
35   Vector cluster;
36
37   SequenceI[] sequence;
38
39   // SequenceData is a string representation of what the user
40   // sees. The display may contain hidden columns.
41   public AlignmentView seqData = null;
42
43   int[] done;
44
45   int noseqs;
46
47   int noClus;
48
49   float[][] distance;
50
51   int mini;
52
53   int minj;
54
55   float ri;
56
57   float rj;
58
59   Vector groups = new Vector();
60
61   SequenceNode maxdist;
62
63   SequenceNode top;
64
65   float maxDistValue;
66
67   float maxheight;
68
69   int ycount;
70
71   Vector node;
72
73   String type;
74
75   String pwtype;
76
77   Object found = null;
78
79   Object leaves = null;
80
81   boolean hasDistances = true; // normal case for jalview trees
82
83   boolean hasBootstrap = false; // normal case for jalview trees
84
85   private boolean hasRootDistance = true;
86
87   /**
88    * Create a new NJTree object with leaves associated with sequences in seqs,
89    * and original alignment data represented by Cigar strings.
90    * 
91    * @param seqs
92    *          SequenceI[]
93    * @param odata
94    *          Cigar[]
95    * @param treefile
96    *          NewickFile
97    */
98   public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
99   {
100     this(seqs, treefile);
101     if (odata != null)
102     {
103       seqData = odata;
104     }
105     /*
106      * sequenceString = new String[odata.length]; char gapChar =
107      * jalview.util.Comparison.GapChars.charAt(0); for (int i = 0; i <
108      * odata.length; i++) { SequenceI oseq_aligned = odata[i].getSeq(gapChar);
109      * sequenceString[i] = oseq_aligned.getSequence(); }
110      */
111   }
112
113   /**
114    * Creates a new NJTree object from a tree from an external source
115    * 
116    * @param seqs
117    *          SequenceI which should be associated with leafs of treefile
118    * @param treefile
119    *          A parsed tree
120    */
121   public NJTree(SequenceI[] seqs, NewickFile treefile)
122   {
123     this.sequence = seqs;
124     top = treefile.getTree();
125
126     /**
127      * There is no dependent alignment to be recovered from an imported tree.
128      * 
129      * if (sequenceString == null) { sequenceString = new String[seqs.length];
130      * for (int i = 0; i < seqs.length; i++) { sequenceString[i] =
131      * seqs[i].getSequence(); } }
132      */
133
134     hasDistances = treefile.HasDistances();
135     hasBootstrap = treefile.HasBootstrap();
136     hasRootDistance = treefile.HasRootDistance();
137
138     maxheight = findHeight(top);
139
140     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
141
142     Vector leaves = new Vector();
143     findLeaves(top, leaves);
144
145     int i = 0;
146     int namesleft = seqs.length;
147
148     SequenceNode j;
149     SequenceI nam;
150     String realnam;
151     Vector one2many = new Vector();
152     int countOne2Many = 0;
153     while (i < leaves.size())
154     {
155       j = (SequenceNode) leaves.elementAt(i++);
156       realnam = j.getName();
157       nam = null;
158
159       if (namesleft > -1)
160       {
161         nam = algnIds.findIdMatch(realnam);
162       }
163
164       if (nam != null)
165       {
166         j.setElement(nam);
167         if (one2many.contains(nam))
168         {
169           countOne2Many++;
170           // if (jalview.bin.Cache.log.isDebugEnabled())
171           // jalview.bin.Cache.log.debug("One 2 many relationship for
172           // "+nam.getName());
173         }
174         else
175         {
176           one2many.addElement(nam);
177           namesleft--;
178         }
179       }
180       else
181       {
182         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
183         j.setPlaceholder(true);
184       }
185     }
186     // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
187     // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
188     // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
189     // more leaves.");
190     // }
191     // one2many.clear();
192   }
193
194   /**
195    * Creates a new NJTree object.
196    * 
197    * @param sequence
198    *          DOCUMENT ME!
199    * @param type
200    *          DOCUMENT ME!
201    * @param pwtype
202    *          DOCUMENT ME!
203    * @param start
204    *          DOCUMENT ME!
205    * @param end
206    *          DOCUMENT ME!
207    */
208   public NJTree(SequenceI[] sequence, AlignmentView seqData, String type,
209           String pwtype, int start, int end)
210   {
211     this.sequence = sequence;
212     this.node = new Vector();
213     this.type = type;
214     this.pwtype = pwtype;
215     if (seqData != null)
216     {
217       this.seqData = seqData;
218     }
219     else
220     {
221       SeqCigar[] seqs = new SeqCigar[sequence.length];
222       for (int i = 0; i < sequence.length; i++)
223       {
224         seqs[i] = new SeqCigar(sequence[i], start, end);
225       }
226       CigarArray sdata = new CigarArray(seqs);
227       sdata.addOperation(CigarArray.M, end - start + 1);
228       this.seqData = new AlignmentView(sdata, start);
229     }
230     // System.err.println("Made seqData");// dbg
231     if (!(type.equals("NJ")))
232     {
233       type = "AV";
234     }
235
236     if (!(pwtype.equals("PID")))
237     {
238       if (ResidueProperties.getScoreMatrix(pwtype) == null)
239       {
240         pwtype = "BLOSUM62";
241       }
242     }
243
244     int i = 0;
245
246     done = new int[sequence.length];
247
248     while ((i < sequence.length) && (sequence[i] != null))
249     {
250       done[i] = 0;
251       i++;
252     }
253
254     noseqs = i++;
255
256     distance = findDistances(this.seqData
257             .getSequenceStrings(Comparison.GapChars.charAt(0)));
258     // System.err.println("Made distances");// dbg
259     makeLeaves();
260     // System.err.println("Made leaves");// dbg
261
262     noClus = cluster.size();
263
264     cluster();
265     // System.err.println("Made clusters");// dbg
266
267   }
268
269   /**
270    * Generate a string representation of the Tree
271    * 
272    * @return Newick File with all tree data available
273    */
274   public String toString()
275   {
276     jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
277
278     return fout.print(isHasBootstrap(),
279     isHasDistances(), isHasRootDistance()); // output all data available for tree
280   }
281
282   /**
283    * 
284    * used when the alignment associated to a tree has changed.
285    * 
286    * @param alignment
287    *          Vector
288    */
289   public void UpdatePlaceHolders(Vector alignment)
290   {
291     Vector leaves = new Vector();
292     findLeaves(top, leaves);
293
294     int sz = leaves.size();
295     SequenceIdMatcher seqmatcher = null;
296     int i = 0;
297
298     while (i < sz)
299     {
300       SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
301
302       if (alignment.contains(leaf.element()))
303       {
304         leaf.setPlaceholder(false);
305       }
306       else
307       {
308         if (seqmatcher == null)
309         {
310           // Only create this the first time we need it
311           SequenceI[] seqs = new SequenceI[alignment.size()];
312
313           for (int j = 0; j < seqs.length; j++)
314           {
315             seqs[j] = (SequenceI) alignment.elementAt(j);
316           }
317
318           seqmatcher = new SequenceIdMatcher(seqs);
319         }
320
321         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
322
323         if (nam != null)
324         {
325           if (!leaf.isPlaceholder())
326           {
327             // remapping the node to a new sequenceI - should remove any refs to
328             // old one.
329             // TODO - make many sequenceI to one leaf mappings possible!
330             // (JBPNote)
331           }
332           leaf.setPlaceholder(false);
333           leaf.setElement(nam);
334         }
335         else
336         {
337           if (!leaf.isPlaceholder())
338           {
339             // Construct a new placeholder sequence object for this leaf
340             leaf.setElement(new Sequence(leaf.getName(),
341                     "THISISAPLACEHLDER"));
342           }
343           leaf.setPlaceholder(true);
344
345         }
346       }
347     }
348   }
349   /**
350    * rename any nodes according to their associated sequence.
351    * This will modify the tree's metadata! (ie the original NewickFile or newly generated BinaryTree's label data) 
352    */
353   public void renameAssociatedNodes() {
354     applyToNodes(new NodeTransformI() {
355
356       @Override
357       public void transform(BinaryNode node)
358       {
359         Object el = node.element();
360         if (el!=null && el instanceof SequenceI)
361         {
362           node.setName(((SequenceI)el).getName());
363         }
364       }
365     });
366   }
367   /**
368    * DOCUMENT ME!
369    */
370   public void cluster()
371   {
372     while (noClus > 2)
373     {
374       if (type.equals("NJ"))
375       {
376         findMinNJDistance();
377       }
378       else
379       {
380         findMinDistance();
381       }
382
383       Cluster c = joinClusters(mini, minj);
384
385       done[minj] = 1;
386
387       cluster.setElementAt(null, minj);
388       cluster.setElementAt(c, mini);
389
390       noClus--;
391     }
392
393     boolean onefound = false;
394
395     int one = -1;
396     int two = -1;
397
398     for (int i = 0; i < noseqs; i++)
399     {
400       if (done[i] != 1)
401       {
402         if (onefound == false)
403         {
404           two = i;
405           onefound = true;
406         }
407         else
408         {
409           one = i;
410         }
411       }
412     }
413
414     joinClusters(one, two);
415     top = (SequenceNode) (node.elementAt(one));
416
417     reCount(top);
418     findHeight(top);
419     findMaxDist(top);
420   }
421
422   /**
423    * DOCUMENT ME!
424    * 
425    * @param i
426    *          DOCUMENT ME!
427    * @param j
428    *          DOCUMENT ME!
429    * 
430    * @return DOCUMENT ME!
431    */
432   public Cluster joinClusters(int i, int j)
433   {
434     float dist = distance[i][j];
435
436     int noi = ((Cluster) cluster.elementAt(i)).value.length;
437     int noj = ((Cluster) cluster.elementAt(j)).value.length;
438
439     int[] value = new int[noi + noj];
440
441     for (int ii = 0; ii < noi; ii++)
442     {
443       value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
444     }
445
446     for (int ii = noi; ii < (noi + noj); ii++)
447     {
448       value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
449     }
450
451     Cluster c = new Cluster(value);
452
453     ri = findr(i, j);
454     rj = findr(j, i);
455
456     if (type.equals("NJ"))
457     {
458       findClusterNJDistance(i, j);
459     }
460     else
461     {
462       findClusterDistance(i, j);
463     }
464
465     SequenceNode sn = new SequenceNode();
466
467     sn.setLeft((SequenceNode) (node.elementAt(i)));
468     sn.setRight((SequenceNode) (node.elementAt(j)));
469
470     SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
471     SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
472
473     if (type.equals("NJ"))
474     {
475       findNewNJDistances(tmpi, tmpj, dist);
476     }
477     else
478     {
479       findNewDistances(tmpi, tmpj, dist);
480     }
481
482     tmpi.setParent(sn);
483     tmpj.setParent(sn);
484
485     node.setElementAt(sn, i);
486
487     return c;
488   }
489
490   /**
491    * DOCUMENT ME!
492    * 
493    * @param tmpi
494    *          DOCUMENT ME!
495    * @param tmpj
496    *          DOCUMENT ME!
497    * @param dist
498    *          DOCUMENT ME!
499    */
500   public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
501           float dist)
502   {
503
504     tmpi.dist = ((dist + ri) - rj) / 2;
505     tmpj.dist = (dist - tmpi.dist);
506
507     if (tmpi.dist < 0)
508     {
509       tmpi.dist = 0;
510     }
511
512     if (tmpj.dist < 0)
513     {
514       tmpj.dist = 0;
515     }
516   }
517
518   /**
519    * DOCUMENT ME!
520    * 
521    * @param tmpi
522    *          DOCUMENT ME!
523    * @param tmpj
524    *          DOCUMENT ME!
525    * @param dist
526    *          DOCUMENT ME!
527    */
528   public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
529           float dist)
530   {
531     float ih = 0;
532     float jh = 0;
533
534     SequenceNode sni = tmpi;
535     SequenceNode snj = tmpj;
536
537     while (sni != null)
538     {
539       ih = ih + sni.dist;
540       sni = (SequenceNode) sni.left();
541     }
542
543     while (snj != null)
544     {
545       jh = jh + snj.dist;
546       snj = (SequenceNode) snj.left();
547     }
548
549     tmpi.dist = ((dist / 2) - ih);
550     tmpj.dist = ((dist / 2) - jh);
551   }
552
553   /**
554    * DOCUMENT ME!
555    * 
556    * @param i
557    *          DOCUMENT ME!
558    * @param j
559    *          DOCUMENT ME!
560    */
561   public void findClusterDistance(int i, int j)
562   {
563     int noi = ((Cluster) cluster.elementAt(i)).value.length;
564     int noj = ((Cluster) cluster.elementAt(j)).value.length;
565
566     // New distances from cluster to others
567     float[] newdist = new float[noseqs];
568
569     for (int l = 0; l < noseqs; l++)
570     {
571       if ((l != i) && (l != j))
572       {
573         newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
574                 / (noi + noj);
575       }
576       else
577       {
578         newdist[l] = 0;
579       }
580     }
581
582     for (int ii = 0; ii < noseqs; ii++)
583     {
584       distance[i][ii] = newdist[ii];
585       distance[ii][i] = newdist[ii];
586     }
587   }
588
589   /**
590    * DOCUMENT ME!
591    * 
592    * @param i
593    *          DOCUMENT ME!
594    * @param j
595    *          DOCUMENT ME!
596    */
597   public void findClusterNJDistance(int i, int j)
598   {
599
600     // New distances from cluster to others
601     float[] newdist = new float[noseqs];
602
603     for (int l = 0; l < noseqs; l++)
604     {
605       if ((l != i) && (l != j))
606       {
607         newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) / 2;
608       }
609       else
610       {
611         newdist[l] = 0;
612       }
613     }
614
615     for (int ii = 0; ii < noseqs; ii++)
616     {
617       distance[i][ii] = newdist[ii];
618       distance[ii][i] = newdist[ii];
619     }
620   }
621
622   /**
623    * DOCUMENT ME!
624    * 
625    * @param i
626    *          DOCUMENT ME!
627    * @param j
628    *          DOCUMENT ME!
629    * 
630    * @return DOCUMENT ME!
631    */
632   public float findr(int i, int j)
633   {
634     float tmp = 1;
635
636     for (int k = 0; k < noseqs; k++)
637     {
638       if ((k != i) && (k != j) && (done[k] != 1))
639       {
640         tmp = tmp + distance[i][k];
641       }
642     }
643
644     if (noClus > 2)
645     {
646       tmp = tmp / (noClus - 2);
647     }
648
649     return tmp;
650   }
651
652   /**
653    * DOCUMENT ME!
654    * 
655    * @return DOCUMENT ME!
656    */
657   public float findMinNJDistance()
658   {
659     float min = 100000;
660
661     for (int i = 0; i < (noseqs - 1); i++)
662     {
663       for (int j = i + 1; j < noseqs; j++)
664       {
665         if ((done[i] != 1) && (done[j] != 1))
666         {
667           float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
668
669           if (tmp < min)
670           {
671             mini = i;
672             minj = j;
673
674             min = tmp;
675           }
676         }
677       }
678     }
679
680     return min;
681   }
682
683   /**
684    * DOCUMENT ME!
685    * 
686    * @return DOCUMENT ME!
687    */
688   public float findMinDistance()
689   {
690     float min = 100000;
691
692     for (int i = 0; i < (noseqs - 1); i++)
693     {
694       for (int j = i + 1; j < noseqs; j++)
695       {
696         if ((done[i] != 1) && (done[j] != 1))
697         {
698           if (distance[i][j] < min)
699           {
700             mini = i;
701             minj = j;
702
703             min = distance[i][j];
704           }
705         }
706       }
707     }
708
709     return min;
710   }
711
712   /**
713    * DOCUMENT ME!
714    * 
715    * @return DOCUMENT ME!
716    */
717   public float[][] findDistances(String[] sequenceString)
718   {
719     float[][] distance = new float[noseqs][noseqs];
720
721     if (pwtype.equals("PID"))
722     {
723       for (int i = 0; i < (noseqs - 1); i++)
724       {
725         for (int j = i; j < noseqs; j++)
726         {
727           if (j == i)
728           {
729             distance[i][i] = 0;
730           }
731           else
732           {
733             distance[i][j] = 100 - Comparison.PID(sequenceString[i],
734                     sequenceString[j]);
735
736             distance[j][i] = distance[i][j];
737           }
738         }
739       }
740     }
741     else
742     {
743       // Pairwise substitution score (with no gap penalties)
744       ScoreMatrix pwmatrix = ResidueProperties.getScoreMatrix(pwtype);
745       if (pwmatrix == null)
746       {
747         pwmatrix = ResidueProperties.getScoreMatrix("BLOSUM62");
748       }
749       int maxscore = 0;
750       int end = sequenceString[0].length();
751       for (int i = 0; i < (noseqs - 1); i++)
752       {
753         for (int j = i; j < noseqs; j++)
754         {
755           int score = 0;
756
757           for (int k = 0; k < end; k++)
758           {
759             try
760             {
761               score += pwmatrix.getPairwiseScore(
762                       sequenceString[i].charAt(k),
763                       sequenceString[j].charAt(k));
764             } catch (Exception ex)
765             {
766               System.err.println("err creating BLOSUM62 tree");
767               ex.printStackTrace();
768             }
769           }
770
771           distance[i][j] = (float) score;
772
773           if (score > maxscore)
774           {
775             maxscore = score;
776           }
777         }
778       }
779
780       for (int i = 0; i < (noseqs - 1); i++)
781       {
782         for (int j = i; j < noseqs; j++)
783         {
784           distance[i][j] = (float) maxscore - distance[i][j];
785           distance[j][i] = distance[i][j];
786         }
787       }
788
789     }
790     return distance;
791
792     // else
793     /*
794      * else if (pwtype.equals("SW")) { float max = -1;
795      * 
796      * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
797      * { AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
798      * as.calcScoreMatrix(); as.traceAlignment(); as.printAlignment(System.out);
799      * distance[i][j] = (float) as.maxscore;
800      * 
801      * if (max < distance[i][j]) { max = distance[i][j]; } } }
802      * 
803      * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
804      * { distance[i][j] = max - distance[i][j]; distance[j][i] = distance[i][j];
805      * } } }/
806      */
807   }
808
809   /**
810    * DOCUMENT ME!
811    */
812   public void makeLeaves()
813   {
814     cluster = new Vector();
815
816     for (int i = 0; i < noseqs; i++)
817     {
818       SequenceNode sn = new SequenceNode();
819
820       sn.setElement(sequence[i]);
821       sn.setName(sequence[i].getName());
822       node.addElement(sn);
823
824       int[] value = new int[1];
825       value[0] = i;
826
827       Cluster c = new Cluster(value);
828       cluster.addElement(c);
829     }
830   }
831
832   /**
833    * Search for leaf nodes.
834    * 
835    * @param node
836    *          root node to search from
837    * @param leaves
838    *          Vector of leaves to add leaf node objects too.
839    * 
840    * @return Vector of leaf nodes on binary tree
841    */
842   public Vector findLeaves(SequenceNode node, Vector leaves)
843   {
844     if (node == null)
845     {
846       return leaves;
847     }
848
849     if ((node.left() == null) && (node.right() == null)) // Interior node
850     // detection
851     {
852       leaves.addElement(node);
853
854       return leaves;
855     }
856     else
857     {
858       /*
859        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
860        * leaves.addElement(node); }
861        */
862       findLeaves((SequenceNode) node.left(), leaves);
863       findLeaves((SequenceNode) node.right(), leaves);
864     }
865
866     return leaves;
867   }
868
869   /**
870    * Find the leaf node with a particular ycount
871    * 
872    * @param node
873    *          initial point on tree to search from
874    * @param count
875    *          value to search for
876    * 
877    * @return null or the node with ycound=count
878    */
879   public Object findLeaf(SequenceNode node, int count)
880   {
881     found = _findLeaf(node, count);
882
883     return found;
884   }
885
886   /*
887    * #see findLeaf(SequenceNode node, count)
888    */
889   public Object _findLeaf(SequenceNode node, int count)
890   {
891     if (node == null)
892     {
893       return null;
894     }
895
896     if (node.ycount == count)
897     {
898       found = node.element();
899
900       return found;
901     }
902     else
903     {
904       _findLeaf((SequenceNode) node.left(), count);
905       _findLeaf((SequenceNode) node.right(), count);
906     }
907
908     return found;
909   }
910
911   /**
912    * printNode is mainly for debugging purposes.
913    * 
914    * @param node
915    *          SequenceNode
916    */
917   public void printNode(SequenceNode node)
918   {
919     if (node == null)
920     {
921       return;
922     }
923
924     if ((node.left() == null) && (node.right() == null))
925     {
926       System.out
927               .println("Leaf = " + ((SequenceI) node.element()).getName());
928       System.out.println("Dist " + ((SequenceNode) node).dist);
929       System.out.println("Boot " + node.getBootstrap());
930     }
931     else
932     {
933       System.out.println("Dist " + ((SequenceNode) node).dist);
934       printNode((SequenceNode) node.left());
935       printNode((SequenceNode) node.right());
936     }
937   }
938
939   /**
940    * DOCUMENT ME!
941    * 
942    * @param node
943    *          DOCUMENT ME!
944    */
945   public void findMaxDist(SequenceNode node)
946   {
947     if (node == null)
948     {
949       return;
950     }
951
952     if ((node.left() == null) && (node.right() == null))
953     {
954       float dist = ((SequenceNode) node).dist;
955
956       if (dist > maxDistValue)
957       {
958         maxdist = (SequenceNode) node;
959         maxDistValue = dist;
960       }
961     }
962     else
963     {
964       findMaxDist((SequenceNode) node.left());
965       findMaxDist((SequenceNode) node.right());
966     }
967   }
968
969   /**
970    * DOCUMENT ME!
971    * 
972    * @return DOCUMENT ME!
973    */
974   public Vector getGroups()
975   {
976     return groups;
977   }
978
979   /**
980    * DOCUMENT ME!
981    * 
982    * @return DOCUMENT ME!
983    */
984   public float getMaxHeight()
985   {
986     return maxheight;
987   }
988
989   /**
990    * DOCUMENT ME!
991    * 
992    * @param node
993    *          DOCUMENT ME!
994    * @param threshold
995    *          DOCUMENT ME!
996    */
997   public void groupNodes(SequenceNode node, float threshold)
998   {
999     if (node == null)
1000     {
1001       return;
1002     }
1003
1004     if ((node.height / maxheight) > threshold)
1005     {
1006       groups.addElement(node);
1007     }
1008     else
1009     {
1010       groupNodes((SequenceNode) node.left(), threshold);
1011       groupNodes((SequenceNode) node.right(), threshold);
1012     }
1013   }
1014
1015   /**
1016    * DOCUMENT ME!
1017    * 
1018    * @param node
1019    *          DOCUMENT ME!
1020    * 
1021    * @return DOCUMENT ME!
1022    */
1023   public float findHeight(SequenceNode node)
1024   {
1025     if (node == null)
1026     {
1027       return maxheight;
1028     }
1029
1030     if ((node.left() == null) && (node.right() == null))
1031     {
1032       node.height = ((SequenceNode) node.parent()).height + node.dist;
1033
1034       if (node.height > maxheight)
1035       {
1036         return node.height;
1037       }
1038       else
1039       {
1040         return maxheight;
1041       }
1042     }
1043     else
1044     {
1045       if (node.parent() != null)
1046       {
1047         node.height = ((SequenceNode) node.parent()).height + node.dist;
1048       }
1049       else
1050       {
1051         maxheight = 0;
1052         node.height = (float) 0.0;
1053       }
1054
1055       maxheight = findHeight((SequenceNode) (node.left()));
1056       maxheight = findHeight((SequenceNode) (node.right()));
1057     }
1058
1059     return maxheight;
1060   }
1061
1062   /**
1063    * DOCUMENT ME!
1064    * 
1065    * @return DOCUMENT ME!
1066    */
1067   public SequenceNode reRoot()
1068   {
1069     if (maxdist != null)
1070     {
1071       ycount = 0;
1072
1073       float tmpdist = maxdist.dist;
1074
1075       // New top
1076       SequenceNode sn = new SequenceNode();
1077       sn.setParent(null);
1078
1079       // New right hand of top
1080       SequenceNode snr = (SequenceNode) maxdist.parent();
1081       changeDirection(snr, maxdist);
1082       System.out.println("Printing reversed tree");
1083       printN(snr);
1084       snr.dist = tmpdist / 2;
1085       maxdist.dist = tmpdist / 2;
1086
1087       snr.setParent(sn);
1088       maxdist.setParent(sn);
1089
1090       sn.setRight(snr);
1091       sn.setLeft(maxdist);
1092
1093       top = sn;
1094
1095       ycount = 0;
1096       reCount(top);
1097       findHeight(top);
1098     }
1099
1100     return top;
1101   }
1102
1103   /**
1104    * 
1105    * @return true if original sequence data can be recovered
1106    */
1107   public boolean hasOriginalSequenceData()
1108   {
1109     return seqData != null;
1110   }
1111
1112   /**
1113    * Returns original alignment data used for calculation - or null where not
1114    * available.
1115    * 
1116    * @return null or cut'n'pasteable alignment
1117    */
1118   public String printOriginalSequenceData(char gapChar)
1119   {
1120     if (seqData == null)
1121     {
1122       return null;
1123     }
1124
1125     StringBuffer sb = new StringBuffer();
1126     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1127     for (int i = 0; i < seqdatas.length; i++)
1128     {
1129       sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequence[i]
1130               .getName()));
1131       sb.append(" " + seqdatas[i] + "\n");
1132     }
1133     return sb.toString();
1134   }
1135
1136   /**
1137    * DOCUMENT ME!
1138    * 
1139    * @param node
1140    *          DOCUMENT ME!
1141    */
1142   public void printN(SequenceNode node)
1143   {
1144     if (node == null)
1145     {
1146       return;
1147     }
1148
1149     if ((node.left() != null) && (node.right() != null))
1150     {
1151       printN((SequenceNode) node.left());
1152       printN((SequenceNode) node.right());
1153     }
1154     else
1155     {
1156       System.out.println(" name = "
1157               + ((SequenceI) node.element()).getName());
1158     }
1159
1160     System.out.println(" dist = " + ((SequenceNode) node).dist + " "
1161             + ((SequenceNode) node).count + " "
1162             + ((SequenceNode) node).height);
1163   }
1164
1165   /**
1166    * DOCUMENT ME!
1167    * 
1168    * @param node
1169    *          DOCUMENT ME!
1170    */
1171   public void reCount(SequenceNode node)
1172   {
1173     ycount = 0;
1174     _lycount = 0;
1175     // _lylimit = this.node.size();
1176     _reCount(node);
1177   }
1178
1179   private long _lycount = 0, _lylimit = 0;
1180
1181   /**
1182    * DOCUMENT ME!
1183    * 
1184    * @param node
1185    *          DOCUMENT ME!
1186    */
1187   public void _reCount(SequenceNode node)
1188   {
1189     // if (_lycount<_lylimit)
1190     // {
1191     // System.err.println("Warning: depth of _recount greater than number of nodes.");
1192     // }
1193     if (node == null)
1194     {
1195       return;
1196     }
1197     _lycount++;
1198
1199     if ((node.left() != null) && (node.right() != null))
1200     {
1201
1202       _reCount((SequenceNode) node.left());
1203       _reCount((SequenceNode) node.right());
1204
1205       SequenceNode l = (SequenceNode) node.left();
1206       SequenceNode r = (SequenceNode) node.right();
1207
1208       ((SequenceNode) node).count = l.count + r.count;
1209       ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1210     }
1211     else
1212     {
1213       ((SequenceNode) node).count = 1;
1214       ((SequenceNode) node).ycount = ycount++;
1215     }
1216     _lycount--;
1217   }
1218
1219   /**
1220    * DOCUMENT ME!
1221    * 
1222    * @param node
1223    *          DOCUMENT ME!
1224    */
1225   public void swapNodes(SequenceNode node)
1226   {
1227     if (node == null)
1228     {
1229       return;
1230     }
1231
1232     SequenceNode tmp = (SequenceNode) node.left();
1233
1234     node.setLeft(node.right());
1235     node.setRight(tmp);
1236   }
1237
1238   /**
1239    * DOCUMENT ME!
1240    * 
1241    * @param node
1242    *          DOCUMENT ME!
1243    * @param dir
1244    *          DOCUMENT ME!
1245    */
1246   public void changeDirection(SequenceNode node, SequenceNode dir)
1247   {
1248     if (node == null)
1249     {
1250       return;
1251     }
1252
1253     if (node.parent() != top)
1254     {
1255       changeDirection((SequenceNode) node.parent(), node);
1256
1257       SequenceNode tmp = (SequenceNode) node.parent();
1258
1259       if (dir == node.left())
1260       {
1261         node.setParent(dir);
1262         node.setLeft(tmp);
1263       }
1264       else if (dir == node.right())
1265       {
1266         node.setParent(dir);
1267         node.setRight(tmp);
1268       }
1269     }
1270     else
1271     {
1272       if (dir == node.left())
1273       {
1274         node.setParent(node.left());
1275
1276         if (top.left() == node)
1277         {
1278           node.setRight(top.right());
1279         }
1280         else
1281         {
1282           node.setRight(top.left());
1283         }
1284       }
1285       else
1286       {
1287         node.setParent(node.right());
1288
1289         if (top.left() == node)
1290         {
1291           node.setLeft(top.right());
1292         }
1293         else
1294         {
1295           node.setLeft(top.left());
1296         }
1297       }
1298     }
1299   }
1300
1301   /**
1302    * DOCUMENT ME!
1303    * 
1304    * @return DOCUMENT ME!
1305    */
1306   public SequenceNode getMaxDist()
1307   {
1308     return maxdist;
1309   }
1310
1311   /**
1312    * DOCUMENT ME!
1313    * 
1314    * @return DOCUMENT ME!
1315    */
1316   public SequenceNode getTopNode()
1317   {
1318     return top;
1319   }
1320
1321   /**
1322    * 
1323    * @return true if tree has real distances
1324    */
1325   public boolean isHasDistances()
1326   {
1327     return hasDistances;
1328   }
1329
1330   /**
1331    * 
1332    * @return true if tree has real bootstrap values
1333    */
1334   public boolean isHasBootstrap()
1335   {
1336     return hasBootstrap;
1337   }
1338
1339   public boolean isHasRootDistance()
1340   {
1341     return hasRootDistance;
1342   }
1343
1344   /**
1345    * apply the given transform to all the nodes in the tree.
1346    * 
1347    * @param nodeTransformI
1348    */
1349   public void applyToNodes(NodeTransformI nodeTransformI)
1350   {
1351     for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
1352             .transform((BinaryNode) nodes.nextElement()))
1353       ;
1354   }
1355 }
1356
1357 /**
1358  * DOCUMENT ME!
1359  * 
1360  * @author $author$
1361  * @version $Revision$
1362  */
1363 class Cluster
1364 {
1365   int[] value;
1366
1367   /**
1368    * Creates a new Cluster object.
1369    * 
1370    * @param value
1371    *          DOCUMENT ME!
1372    */
1373   public Cluster(int[] value)
1374   {
1375     this.value = value;
1376   }
1377 }