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