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