JAL-1159 Merging 2.8.1 patches and Anne Menards work from 2012 into development branch
[jalview.git] / src / jalview / analysis / NJTree.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8)
3  * Copyright (C) 2012 J Procter, AM Waterhouse, LM Lui, J Engelhardt, 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(), isHasDistances(),
279             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 list
287    *          Sequence set to be associated with tree nodes
288    */
289   public void UpdatePlaceHolders(List<SequenceI> list)
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 (list.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[list.size()];
312
313           for (int j = 0; j < seqs.length; j++)
314           {
315             seqs[j] = (SequenceI) list.get(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   /**
351    * rename any nodes according to their associated sequence. This will modify
352    * the tree's metadata! (ie the original NewickFile or newly generated
353    * BinaryTree's label data)
354    */
355   public void renameAssociatedNodes()
356   {
357     applyToNodes(new NodeTransformI()
358     {
359
360       @Override
361       public void transform(BinaryNode node)
362       {
363         Object el = node.element();
364         if (el != null && el instanceof SequenceI)
365         {
366           node.setName(((SequenceI) el).getName());
367         }
368       }
369     });
370   }
371
372   /**
373    * DOCUMENT ME!
374    */
375   public void cluster()
376   {
377     while (noClus > 2)
378     {
379       if (type.equals("NJ"))
380       {
381         findMinNJDistance();
382       }
383       else
384       {
385         findMinDistance();
386       }
387
388       Cluster c = joinClusters(mini, minj);
389
390       done[minj] = 1;
391
392       cluster.setElementAt(null, minj);
393       cluster.setElementAt(c, mini);
394
395       noClus--;
396     }
397
398     boolean onefound = false;
399
400     int one = -1;
401     int two = -1;
402
403     for (int i = 0; i < noseqs; i++)
404     {
405       if (done[i] != 1)
406       {
407         if (onefound == false)
408         {
409           two = i;
410           onefound = true;
411         }
412         else
413         {
414           one = i;
415         }
416       }
417     }
418
419     joinClusters(one, two);
420     top = (SequenceNode) (node.elementAt(one));
421
422     reCount(top);
423     findHeight(top);
424     findMaxDist(top);
425   }
426
427   /**
428    * DOCUMENT ME!
429    * 
430    * @param i
431    *          DOCUMENT ME!
432    * @param j
433    *          DOCUMENT ME!
434    * 
435    * @return DOCUMENT ME!
436    */
437   public Cluster joinClusters(int i, int j)
438   {
439     float dist = distance[i][j];
440
441     int noi = ((Cluster) cluster.elementAt(i)).value.length;
442     int noj = ((Cluster) cluster.elementAt(j)).value.length;
443
444     int[] value = new int[noi + noj];
445
446     for (int ii = 0; ii < noi; ii++)
447     {
448       value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
449     }
450
451     for (int ii = noi; ii < (noi + noj); ii++)
452     {
453       value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
454     }
455
456     Cluster c = new Cluster(value);
457
458     ri = findr(i, j);
459     rj = findr(j, i);
460
461     if (type.equals("NJ"))
462     {
463       findClusterNJDistance(i, j);
464     }
465     else
466     {
467       findClusterDistance(i, j);
468     }
469
470     SequenceNode sn = new SequenceNode();
471
472     sn.setLeft((SequenceNode) (node.elementAt(i)));
473     sn.setRight((SequenceNode) (node.elementAt(j)));
474
475     SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
476     SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
477
478     if (type.equals("NJ"))
479     {
480       findNewNJDistances(tmpi, tmpj, dist);
481     }
482     else
483     {
484       findNewDistances(tmpi, tmpj, dist);
485     }
486
487     tmpi.setParent(sn);
488     tmpj.setParent(sn);
489
490     node.setElementAt(sn, i);
491
492     return c;
493   }
494
495   /**
496    * DOCUMENT ME!
497    * 
498    * @param tmpi
499    *          DOCUMENT ME!
500    * @param tmpj
501    *          DOCUMENT ME!
502    * @param dist
503    *          DOCUMENT ME!
504    */
505   public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
506           float dist)
507   {
508
509     tmpi.dist = ((dist + ri) - rj) / 2;
510     tmpj.dist = (dist - tmpi.dist);
511
512     if (tmpi.dist < 0)
513     {
514       tmpi.dist = 0;
515     }
516
517     if (tmpj.dist < 0)
518     {
519       tmpj.dist = 0;
520     }
521   }
522
523   /**
524    * DOCUMENT ME!
525    * 
526    * @param tmpi
527    *          DOCUMENT ME!
528    * @param tmpj
529    *          DOCUMENT ME!
530    * @param dist
531    *          DOCUMENT ME!
532    */
533   public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
534           float dist)
535   {
536     float ih = 0;
537     float jh = 0;
538
539     SequenceNode sni = tmpi;
540     SequenceNode snj = tmpj;
541
542     while (sni != null)
543     {
544       ih = ih + sni.dist;
545       sni = (SequenceNode) sni.left();
546     }
547
548     while (snj != null)
549     {
550       jh = jh + snj.dist;
551       snj = (SequenceNode) snj.left();
552     }
553
554     tmpi.dist = ((dist / 2) - ih);
555     tmpj.dist = ((dist / 2) - jh);
556   }
557
558   /**
559    * DOCUMENT ME!
560    * 
561    * @param i
562    *          DOCUMENT ME!
563    * @param j
564    *          DOCUMENT ME!
565    */
566   public void findClusterDistance(int i, int j)
567   {
568     int noi = ((Cluster) cluster.elementAt(i)).value.length;
569     int noj = ((Cluster) cluster.elementAt(j)).value.length;
570
571     // New distances from cluster to others
572     float[] newdist = new float[noseqs];
573
574     for (int l = 0; l < noseqs; l++)
575     {
576       if ((l != i) && (l != j))
577       {
578         newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
579                 / (noi + noj);
580       }
581       else
582       {
583         newdist[l] = 0;
584       }
585     }
586
587     for (int ii = 0; ii < noseqs; ii++)
588     {
589       distance[i][ii] = newdist[ii];
590       distance[ii][i] = newdist[ii];
591     }
592   }
593
594   /**
595    * DOCUMENT ME!
596    * 
597    * @param i
598    *          DOCUMENT ME!
599    * @param j
600    *          DOCUMENT ME!
601    */
602   public void findClusterNJDistance(int i, int j)
603   {
604
605     // New distances from cluster to others
606     float[] newdist = new float[noseqs];
607
608     for (int l = 0; l < noseqs; l++)
609     {
610       if ((l != i) && (l != j))
611       {
612         newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) / 2;
613       }
614       else
615       {
616         newdist[l] = 0;
617       }
618     }
619
620     for (int ii = 0; ii < noseqs; ii++)
621     {
622       distance[i][ii] = newdist[ii];
623       distance[ii][i] = newdist[ii];
624     }
625   }
626
627   /**
628    * DOCUMENT ME!
629    * 
630    * @param i
631    *          DOCUMENT ME!
632    * @param j
633    *          DOCUMENT ME!
634    * 
635    * @return DOCUMENT ME!
636    */
637   public float findr(int i, int j)
638   {
639     float tmp = 1;
640
641     for (int k = 0; k < noseqs; k++)
642     {
643       if ((k != i) && (k != j) && (done[k] != 1))
644       {
645         tmp = tmp + distance[i][k];
646       }
647     }
648
649     if (noClus > 2)
650     {
651       tmp = tmp / (noClus - 2);
652     }
653
654     return tmp;
655   }
656
657   /**
658    * DOCUMENT ME!
659    * 
660    * @return DOCUMENT ME!
661    */
662   public float findMinNJDistance()
663   {
664     float min = 100000;
665
666     for (int i = 0; i < (noseqs - 1); i++)
667     {
668       for (int j = i + 1; j < noseqs; j++)
669       {
670         if ((done[i] != 1) && (done[j] != 1))
671         {
672           float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
673
674           if (tmp < min)
675           {
676             mini = i;
677             minj = j;
678
679             min = tmp;
680           }
681         }
682       }
683     }
684
685     return min;
686   }
687
688   /**
689    * DOCUMENT ME!
690    * 
691    * @return DOCUMENT ME!
692    */
693   public float findMinDistance()
694   {
695     float min = 100000;
696
697     for (int i = 0; i < (noseqs - 1); i++)
698     {
699       for (int j = i + 1; j < noseqs; j++)
700       {
701         if ((done[i] != 1) && (done[j] != 1))
702         {
703           if (distance[i][j] < min)
704           {
705             mini = i;
706             minj = j;
707
708             min = distance[i][j];
709           }
710         }
711       }
712     }
713
714     return min;
715   }
716
717   /**
718    * DOCUMENT ME!
719    * 
720    * @return DOCUMENT ME!
721    */
722   public float[][] findDistances(String[] sequenceString)
723   {
724     float[][] distance = new float[noseqs][noseqs];
725
726     if (pwtype.equals("PID"))
727     {
728       for (int i = 0; i < (noseqs - 1); i++)
729       {
730         for (int j = i; j < noseqs; j++)
731         {
732           if (j == i)
733           {
734             distance[i][i] = 0;
735           }
736           else
737           {
738             distance[i][j] = 100 - Comparison.PID(sequenceString[i],
739                     sequenceString[j]);
740
741             distance[j][i] = distance[i][j];
742           }
743         }
744       }
745     }
746     else
747     {
748       // Pairwise substitution score (with no gap penalties)
749       ScoreMatrix pwmatrix = ResidueProperties.getScoreMatrix(pwtype);
750       if (pwmatrix == null)
751       {
752         pwmatrix = ResidueProperties.getScoreMatrix("BLOSUM62");
753       }
754       int maxscore = 0;
755       int end = sequenceString[0].length();
756       for (int i = 0; i < (noseqs - 1); i++)
757       {
758         for (int j = i; j < noseqs; j++)
759         {
760           int score = 0;
761
762           for (int k = 0; k < end; k++)
763           {
764             try
765             {
766               score += pwmatrix.getPairwiseScore(
767                       sequenceString[i].charAt(k),
768                       sequenceString[j].charAt(k));
769             } catch (Exception ex)
770             {
771               System.err.println("err creating BLOSUM62 tree");
772               ex.printStackTrace();
773             }
774           }
775
776           distance[i][j] = (float) score;
777
778           if (score > maxscore)
779           {
780             maxscore = score;
781           }
782         }
783       }
784
785       for (int i = 0; i < (noseqs - 1); i++)
786       {
787         for (int j = i; j < noseqs; j++)
788         {
789           distance[i][j] = (float) maxscore - distance[i][j];
790           distance[j][i] = distance[i][j];
791         }
792       }
793
794     }
795     return distance;
796
797     // else
798     /*
799      * else if (pwtype.equals("SW")) { float max = -1;
800      * 
801      * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
802      * { AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
803      * as.calcScoreMatrix(); as.traceAlignment(); as.printAlignment(System.out);
804      * distance[i][j] = (float) as.maxscore;
805      * 
806      * if (max < distance[i][j]) { max = distance[i][j]; } } }
807      * 
808      * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
809      * { distance[i][j] = max - distance[i][j]; distance[j][i] = distance[i][j];
810      * } } }/
811      */
812   }
813
814   /**
815    * DOCUMENT ME!
816    */
817   public void makeLeaves()
818   {
819     cluster = new Vector();
820
821     for (int i = 0; i < noseqs; i++)
822     {
823       SequenceNode sn = new SequenceNode();
824
825       sn.setElement(sequence[i]);
826       sn.setName(sequence[i].getName());
827       node.addElement(sn);
828
829       int[] value = new int[1];
830       value[0] = i;
831
832       Cluster c = new Cluster(value);
833       cluster.addElement(c);
834     }
835   }
836
837   /**
838    * Search for leaf nodes.
839    * 
840    * @param node
841    *          root node to search from
842    * @param leaves
843    *          Vector of leaves to add leaf node objects too.
844    * 
845    * @return Vector of leaf nodes on binary tree
846    */
847   public Vector findLeaves(SequenceNode node, Vector leaves)
848   {
849     if (node == null)
850     {
851       return leaves;
852     }
853
854     if ((node.left() == null) && (node.right() == null)) // Interior node
855     // detection
856     {
857       leaves.addElement(node);
858
859       return leaves;
860     }
861     else
862     {
863       /*
864        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
865        * leaves.addElement(node); }
866        */
867       findLeaves((SequenceNode) node.left(), leaves);
868       findLeaves((SequenceNode) node.right(), leaves);
869     }
870
871     return leaves;
872   }
873
874   /**
875    * Find the leaf node with a particular ycount
876    * 
877    * @param node
878    *          initial point on tree to search from
879    * @param count
880    *          value to search for
881    * 
882    * @return null or the node with ycound=count
883    */
884   public Object findLeaf(SequenceNode node, int count)
885   {
886     found = _findLeaf(node, count);
887
888     return found;
889   }
890
891   /*
892    * #see findLeaf(SequenceNode node, count)
893    */
894   public Object _findLeaf(SequenceNode node, int count)
895   {
896     if (node == null)
897     {
898       return null;
899     }
900
901     if (node.ycount == count)
902     {
903       found = node.element();
904
905       return found;
906     }
907     else
908     {
909       _findLeaf((SequenceNode) node.left(), count);
910       _findLeaf((SequenceNode) node.right(), count);
911     }
912
913     return found;
914   }
915
916   /**
917    * printNode is mainly for debugging purposes.
918    * 
919    * @param node
920    *          SequenceNode
921    */
922   public void printNode(SequenceNode node)
923   {
924     if (node == null)
925     {
926       return;
927     }
928
929     if ((node.left() == null) && (node.right() == null))
930     {
931       System.out
932               .println("Leaf = " + ((SequenceI) node.element()).getName());
933       System.out.println("Dist " + ((SequenceNode) node).dist);
934       System.out.println("Boot " + node.getBootstrap());
935     }
936     else
937     {
938       System.out.println("Dist " + ((SequenceNode) node).dist);
939       printNode((SequenceNode) node.left());
940       printNode((SequenceNode) node.right());
941     }
942   }
943
944   /**
945    * DOCUMENT ME!
946    * 
947    * @param node
948    *          DOCUMENT ME!
949    */
950   public void findMaxDist(SequenceNode node)
951   {
952     if (node == null)
953     {
954       return;
955     }
956
957     if ((node.left() == null) && (node.right() == null))
958     {
959       float dist = ((SequenceNode) node).dist;
960
961       if (dist > maxDistValue)
962       {
963         maxdist = (SequenceNode) node;
964         maxDistValue = dist;
965       }
966     }
967     else
968     {
969       findMaxDist((SequenceNode) node.left());
970       findMaxDist((SequenceNode) node.right());
971     }
972   }
973
974   /**
975    * DOCUMENT ME!
976    * 
977    * @return DOCUMENT ME!
978    */
979   public Vector getGroups()
980   {
981     return groups;
982   }
983
984   /**
985    * DOCUMENT ME!
986    * 
987    * @return DOCUMENT ME!
988    */
989   public float getMaxHeight()
990   {
991     return maxheight;
992   }
993
994   /**
995    * DOCUMENT ME!
996    * 
997    * @param node
998    *          DOCUMENT ME!
999    * @param threshold
1000    *          DOCUMENT ME!
1001    */
1002   public void groupNodes(SequenceNode node, float threshold)
1003   {
1004     if (node == null)
1005     {
1006       return;
1007     }
1008
1009     if ((node.height / maxheight) > threshold)
1010     {
1011       groups.addElement(node);
1012     }
1013     else
1014     {
1015       groupNodes((SequenceNode) node.left(), threshold);
1016       groupNodes((SequenceNode) node.right(), threshold);
1017     }
1018   }
1019
1020   /**
1021    * DOCUMENT ME!
1022    * 
1023    * @param node
1024    *          DOCUMENT ME!
1025    * 
1026    * @return DOCUMENT ME!
1027    */
1028   public float findHeight(SequenceNode node)
1029   {
1030     if (node == null)
1031     {
1032       return maxheight;
1033     }
1034
1035     if ((node.left() == null) && (node.right() == null))
1036     {
1037       node.height = ((SequenceNode) node.parent()).height + node.dist;
1038
1039       if (node.height > maxheight)
1040       {
1041         return node.height;
1042       }
1043       else
1044       {
1045         return maxheight;
1046       }
1047     }
1048     else
1049     {
1050       if (node.parent() != null)
1051       {
1052         node.height = ((SequenceNode) node.parent()).height + node.dist;
1053       }
1054       else
1055       {
1056         maxheight = 0;
1057         node.height = (float) 0.0;
1058       }
1059
1060       maxheight = findHeight((SequenceNode) (node.left()));
1061       maxheight = findHeight((SequenceNode) (node.right()));
1062     }
1063
1064     return maxheight;
1065   }
1066
1067   /**
1068    * DOCUMENT ME!
1069    * 
1070    * @return DOCUMENT ME!
1071    */
1072   public SequenceNode reRoot()
1073   {
1074     if (maxdist != null)
1075     {
1076       ycount = 0;
1077
1078       float tmpdist = maxdist.dist;
1079
1080       // New top
1081       SequenceNode sn = new SequenceNode();
1082       sn.setParent(null);
1083
1084       // New right hand of top
1085       SequenceNode snr = (SequenceNode) maxdist.parent();
1086       changeDirection(snr, maxdist);
1087       System.out.println("Printing reversed tree");
1088       printN(snr);
1089       snr.dist = tmpdist / 2;
1090       maxdist.dist = tmpdist / 2;
1091
1092       snr.setParent(sn);
1093       maxdist.setParent(sn);
1094
1095       sn.setRight(snr);
1096       sn.setLeft(maxdist);
1097
1098       top = sn;
1099
1100       ycount = 0;
1101       reCount(top);
1102       findHeight(top);
1103     }
1104
1105     return top;
1106   }
1107
1108   /**
1109    * 
1110    * @return true if original sequence data can be recovered
1111    */
1112   public boolean hasOriginalSequenceData()
1113   {
1114     return seqData != null;
1115   }
1116
1117   /**
1118    * Returns original alignment data used for calculation - or null where not
1119    * available.
1120    * 
1121    * @return null or cut'n'pasteable alignment
1122    */
1123   public String printOriginalSequenceData(char gapChar)
1124   {
1125     if (seqData == null)
1126     {
1127       return null;
1128     }
1129
1130     StringBuffer sb = new StringBuffer();
1131     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1132     for (int i = 0; i < seqdatas.length; i++)
1133     {
1134       sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequence[i]
1135               .getName()));
1136       sb.append(" " + seqdatas[i] + "\n");
1137     }
1138     return sb.toString();
1139   }
1140
1141   /**
1142    * DOCUMENT ME!
1143    * 
1144    * @param node
1145    *          DOCUMENT ME!
1146    */
1147   public void printN(SequenceNode node)
1148   {
1149     if (node == null)
1150     {
1151       return;
1152     }
1153
1154     if ((node.left() != null) && (node.right() != null))
1155     {
1156       printN((SequenceNode) node.left());
1157       printN((SequenceNode) node.right());
1158     }
1159     else
1160     {
1161       System.out.println(" name = "
1162               + ((SequenceI) node.element()).getName());
1163     }
1164
1165     System.out.println(" dist = " + ((SequenceNode) node).dist + " "
1166             + ((SequenceNode) node).count + " "
1167             + ((SequenceNode) node).height);
1168   }
1169
1170   /**
1171    * DOCUMENT ME!
1172    * 
1173    * @param node
1174    *          DOCUMENT ME!
1175    */
1176   public void reCount(SequenceNode node)
1177   {
1178     ycount = 0;
1179     _lycount = 0;
1180     // _lylimit = this.node.size();
1181     _reCount(node);
1182   }
1183
1184   private long _lycount = 0, _lylimit = 0;
1185
1186   /**
1187    * DOCUMENT ME!
1188    * 
1189    * @param node
1190    *          DOCUMENT ME!
1191    */
1192   public void _reCount(SequenceNode node)
1193   {
1194     // if (_lycount<_lylimit)
1195     // {
1196     // System.err.println("Warning: depth of _recount greater than number of nodes.");
1197     // }
1198     if (node == null)
1199     {
1200       return;
1201     }
1202     _lycount++;
1203
1204     if ((node.left() != null) && (node.right() != null))
1205     {
1206
1207       _reCount((SequenceNode) node.left());
1208       _reCount((SequenceNode) node.right());
1209
1210       SequenceNode l = (SequenceNode) node.left();
1211       SequenceNode r = (SequenceNode) node.right();
1212
1213       ((SequenceNode) node).count = l.count + r.count;
1214       ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1215     }
1216     else
1217     {
1218       ((SequenceNode) node).count = 1;
1219       ((SequenceNode) node).ycount = ycount++;
1220     }
1221     _lycount--;
1222   }
1223
1224   /**
1225    * DOCUMENT ME!
1226    * 
1227    * @param node
1228    *          DOCUMENT ME!
1229    */
1230   public void swapNodes(SequenceNode node)
1231   {
1232     if (node == null)
1233     {
1234       return;
1235     }
1236
1237     SequenceNode tmp = (SequenceNode) node.left();
1238
1239     node.setLeft(node.right());
1240     node.setRight(tmp);
1241   }
1242
1243   /**
1244    * DOCUMENT ME!
1245    * 
1246    * @param node
1247    *          DOCUMENT ME!
1248    * @param dir
1249    *          DOCUMENT ME!
1250    */
1251   public void changeDirection(SequenceNode node, SequenceNode dir)
1252   {
1253     if (node == null)
1254     {
1255       return;
1256     }
1257
1258     if (node.parent() != top)
1259     {
1260       changeDirection((SequenceNode) node.parent(), node);
1261
1262       SequenceNode tmp = (SequenceNode) node.parent();
1263
1264       if (dir == node.left())
1265       {
1266         node.setParent(dir);
1267         node.setLeft(tmp);
1268       }
1269       else if (dir == node.right())
1270       {
1271         node.setParent(dir);
1272         node.setRight(tmp);
1273       }
1274     }
1275     else
1276     {
1277       if (dir == node.left())
1278       {
1279         node.setParent(node.left());
1280
1281         if (top.left() == node)
1282         {
1283           node.setRight(top.right());
1284         }
1285         else
1286         {
1287           node.setRight(top.left());
1288         }
1289       }
1290       else
1291       {
1292         node.setParent(node.right());
1293
1294         if (top.left() == node)
1295         {
1296           node.setLeft(top.right());
1297         }
1298         else
1299         {
1300           node.setLeft(top.left());
1301         }
1302       }
1303     }
1304   }
1305
1306   /**
1307    * DOCUMENT ME!
1308    * 
1309    * @return DOCUMENT ME!
1310    */
1311   public SequenceNode getMaxDist()
1312   {
1313     return maxdist;
1314   }
1315
1316   /**
1317    * DOCUMENT ME!
1318    * 
1319    * @return DOCUMENT ME!
1320    */
1321   public SequenceNode getTopNode()
1322   {
1323     return top;
1324   }
1325
1326   /**
1327    * 
1328    * @return true if tree has real distances
1329    */
1330   public boolean isHasDistances()
1331   {
1332     return hasDistances;
1333   }
1334
1335   /**
1336    * 
1337    * @return true if tree has real bootstrap values
1338    */
1339   public boolean isHasBootstrap()
1340   {
1341     return hasBootstrap;
1342   }
1343
1344   public boolean isHasRootDistance()
1345   {
1346     return hasRootDistance;
1347   }
1348
1349   /**
1350    * apply the given transform to all the nodes in the tree.
1351    * 
1352    * @param nodeTransformI
1353    */
1354   public void applyToNodes(NodeTransformI nodeTransformI)
1355   {
1356     for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
1357             .transform((BinaryNode) nodes.nextElement()))
1358       ;
1359   }
1360 }
1361
1362 /**
1363  * DOCUMENT ME!
1364  * 
1365  * @author $author$
1366  * @version $Revision$
1367  */
1368 class Cluster
1369 {
1370   int[] value;
1371
1372   /**
1373    * Creates a new Cluster object.
1374    * 
1375    * @param value
1376    *          DOCUMENT ME!
1377    */
1378   public Cluster(int[] value)
1379   {
1380     this.value = value;
1381   }
1382 }