FileParse object can be re-used to read different files concatenated together
[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)) // Interior node detection
804     {
805       leaves.addElement(node);
806
807       return leaves;
808     }
809     else
810     {
811 /*  TODO: Identify internal nodes...    if (node.isSequenceLabel())
812       {
813         leaves.addElement(node);
814       }*/
815       findLeaves( (SequenceNode) node.left(), leaves);
816       findLeaves( (SequenceNode) node.right(), leaves);
817     }
818
819     return leaves;
820   }
821
822   /**
823    * Find the leaf node with a particular ycount 
824    *
825    * @param node initial point on tree to search from
826    * @param count value to search for
827    *
828    * @return null or the node with ycound=count
829    */
830   public Object findLeaf(SequenceNode node, int count)
831   {
832     found = _findLeaf(node, count);
833
834     return found;
835   }
836
837   /*#see findLeaf(SequenceNode node, count)
838    *
839    */
840   public Object _findLeaf(SequenceNode node, int count)
841   {
842     if (node == null)
843     {
844       return null;
845     }
846
847     if (node.ycount == count)
848     {
849       found = node.element();
850
851       return found;
852     }
853     else
854     {
855       _findLeaf( (SequenceNode) node.left(), count);
856       _findLeaf( (SequenceNode) node.right(), count);
857     }
858
859     return found;
860   }
861
862   /**
863    * printNode is mainly for debugging purposes.
864    *
865    * @param node SequenceNode
866    */
867   public void printNode(SequenceNode node)
868   {
869     if (node == null)
870     {
871       return;
872     }
873
874     if ( (node.left() == null) && (node.right() == null))
875     {
876       System.out.println("Leaf = " +
877                          ( (SequenceI) node.element()).getName());
878       System.out.println("Dist " + ( (SequenceNode) node).dist);
879       System.out.println("Boot " + node.getBootstrap());
880     }
881     else
882     {
883       System.out.println("Dist " + ( (SequenceNode) node).dist);
884       printNode( (SequenceNode) node.left());
885       printNode( (SequenceNode) node.right());
886     }
887   }
888
889   /**
890    * DOCUMENT ME!
891    *
892    * @param node DOCUMENT ME!
893    */
894   public void findMaxDist(SequenceNode node)
895   {
896     if (node == null)
897     {
898       return;
899     }
900
901     if ( (node.left() == null) && (node.right() == null))
902     {
903       float dist = ( (SequenceNode) node).dist;
904
905       if (dist > maxDistValue)
906       {
907         maxdist = (SequenceNode) node;
908         maxDistValue = dist;
909       }
910     }
911     else
912     {
913       findMaxDist( (SequenceNode) node.left());
914       findMaxDist( (SequenceNode) node.right());
915     }
916   }
917
918   /**
919    * DOCUMENT ME!
920    *
921    * @return DOCUMENT ME!
922    */
923   public Vector getGroups()
924   {
925     return groups;
926   }
927
928   /**
929    * DOCUMENT ME!
930    *
931    * @return DOCUMENT ME!
932    */
933   public float getMaxHeight()
934   {
935     return maxheight;
936   }
937
938   /**
939    * DOCUMENT ME!
940    *
941    * @param node DOCUMENT ME!
942    * @param threshold DOCUMENT ME!
943    */
944   public void groupNodes(SequenceNode node, float threshold)
945   {
946     if (node == null)
947     {
948       return;
949     }
950
951     if ( (node.height / maxheight) > threshold)
952     {
953       groups.addElement(node);
954     }
955     else
956     {
957       groupNodes( (SequenceNode) node.left(), threshold);
958       groupNodes( (SequenceNode) node.right(), threshold);
959     }
960   }
961
962   /**
963    * DOCUMENT ME!
964    *
965    * @param node DOCUMENT ME!
966    *
967    * @return DOCUMENT ME!
968    */
969   public float findHeight(SequenceNode node)
970   {
971     if (node == null)
972     {
973       return maxheight;
974     }
975
976     if ( (node.left() == null) && (node.right() == null))
977     {
978       node.height = ( (SequenceNode) node.parent()).height + node.dist;
979
980       if (node.height > maxheight)
981       {
982         return node.height;
983       }
984       else
985       {
986         return maxheight;
987       }
988     }
989     else
990     {
991       if (node.parent() != null)
992       {
993         node.height = ( (SequenceNode) node.parent()).height +
994             node.dist;
995       }
996       else
997       {
998         maxheight = 0;
999         node.height = (float) 0.0;
1000       }
1001
1002       maxheight = findHeight( (SequenceNode) (node.left()));
1003       maxheight = findHeight( (SequenceNode) (node.right()));
1004     }
1005
1006     return maxheight;
1007   }
1008
1009   /**
1010    * DOCUMENT ME!
1011    *
1012    * @return DOCUMENT ME!
1013    */
1014   public SequenceNode reRoot()
1015   {
1016     if (maxdist != null)
1017     {
1018       ycount = 0;
1019
1020       float tmpdist = maxdist.dist;
1021
1022       // New top
1023       SequenceNode sn = new SequenceNode();
1024       sn.setParent(null);
1025
1026       // New right hand of top
1027       SequenceNode snr = (SequenceNode) maxdist.parent();
1028       changeDirection(snr, maxdist);
1029       System.out.println("Printing reversed tree");
1030       printN(snr);
1031       snr.dist = tmpdist / 2;
1032       maxdist.dist = tmpdist / 2;
1033
1034       snr.setParent(sn);
1035       maxdist.setParent(sn);
1036
1037       sn.setRight(snr);
1038       sn.setLeft(maxdist);
1039
1040       top = sn;
1041
1042       ycount = 0;
1043       reCount(top);
1044       findHeight(top);
1045     }
1046
1047     return top;
1048   }
1049
1050   /**
1051    *
1052    * @return true if original sequence data can be recovered
1053    */
1054   public boolean hasOriginalSequenceData()
1055   {
1056     return seqData != null;
1057   }
1058
1059   /**
1060    * Returns original alignment data used for calculation - or null where
1061    * not available.
1062    *
1063    * @return null or cut'n'pasteable alignment
1064    */
1065   public String printOriginalSequenceData(char gapChar)
1066   {
1067     if (seqData == null)
1068     {
1069       return null;
1070     }
1071
1072     StringBuffer sb = new StringBuffer();
1073     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1074     for (int i = 0; i < seqdatas.length; i++)
1075     {
1076       sb.append(new jalview.util.Format("%-" + 15 + "s").form(
1077           sequence[i].getName()));
1078       sb.append(" " + seqdatas[i] + "\n");
1079     }
1080     return sb.toString();
1081   }
1082
1083   /**
1084    * DOCUMENT ME!
1085    *
1086    * @param node DOCUMENT ME!
1087    */
1088   public void printN(SequenceNode node)
1089   {
1090     if (node == null)
1091     {
1092       return;
1093     }
1094
1095     if ( (node.left() != null) && (node.right() != null))
1096     {
1097       printN( (SequenceNode) node.left());
1098       printN( (SequenceNode) node.right());
1099     }
1100     else
1101     {
1102       System.out.println(" name = " +
1103                          ( (SequenceI) node.element()).getName());
1104     }
1105
1106     System.out.println(" dist = " + ( (SequenceNode) node).dist + " " +
1107                        ( (SequenceNode) node).count + " " +
1108                        ( (SequenceNode) node).height);
1109   }
1110
1111   /**
1112    * DOCUMENT ME!
1113    *
1114    * @param node DOCUMENT ME!
1115    */
1116   public void reCount(SequenceNode node)
1117   {
1118     ycount = 0;
1119     _reCount(node);
1120   }
1121
1122   /**
1123    * DOCUMENT ME!
1124    *
1125    * @param node DOCUMENT ME!
1126    */
1127   public void _reCount(SequenceNode node)
1128   {
1129     if (node == null)
1130     {
1131       return;
1132     }
1133
1134     if ( (node.left() != null) && (node.right() != null))
1135     {
1136       _reCount( (SequenceNode) node.left());
1137       _reCount( (SequenceNode) node.right());
1138
1139       SequenceNode l = (SequenceNode) node.left();
1140       SequenceNode r = (SequenceNode) node.right();
1141
1142       ( (SequenceNode) node).count = l.count + r.count;
1143       ( (SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1144     }
1145     else
1146     {
1147       ( (SequenceNode) node).count = 1;
1148       ( (SequenceNode) node).ycount = ycount++;
1149     }
1150   }
1151
1152   /**
1153    * DOCUMENT ME!
1154    *
1155    * @param node DOCUMENT ME!
1156    */
1157   public void swapNodes(SequenceNode node)
1158   {
1159     if (node == null)
1160     {
1161       return;
1162     }
1163
1164     SequenceNode tmp = (SequenceNode) node.left();
1165
1166     node.setLeft(node.right());
1167     node.setRight(tmp);
1168   }
1169
1170   /**
1171    * DOCUMENT ME!
1172    *
1173    * @param node DOCUMENT ME!
1174    * @param dir DOCUMENT ME!
1175    */
1176   public void changeDirection(SequenceNode node, SequenceNode dir)
1177   {
1178     if (node == null)
1179     {
1180       return;
1181     }
1182
1183     if (node.parent() != top)
1184     {
1185       changeDirection( (SequenceNode) node.parent(), node);
1186
1187       SequenceNode tmp = (SequenceNode) node.parent();
1188
1189       if (dir == node.left())
1190       {
1191         node.setParent(dir);
1192         node.setLeft(tmp);
1193       }
1194       else if (dir == node.right())
1195       {
1196         node.setParent(dir);
1197         node.setRight(tmp);
1198       }
1199     }
1200     else
1201     {
1202       if (dir == node.left())
1203       {
1204         node.setParent(node.left());
1205
1206         if (top.left() == node)
1207         {
1208           node.setRight(top.right());
1209         }
1210         else
1211         {
1212           node.setRight(top.left());
1213         }
1214       }
1215       else
1216       {
1217         node.setParent(node.right());
1218
1219         if (top.left() == node)
1220         {
1221           node.setLeft(top.right());
1222         }
1223         else
1224         {
1225           node.setLeft(top.left());
1226         }
1227       }
1228     }
1229   }
1230
1231   /**
1232    * DOCUMENT ME!
1233    *
1234    * @return DOCUMENT ME!
1235    */
1236   public SequenceNode getMaxDist()
1237   {
1238     return maxdist;
1239   }
1240
1241   /**
1242    * DOCUMENT ME!
1243    *
1244    * @return DOCUMENT ME!
1245    */
1246   public SequenceNode getTopNode()
1247   {
1248     return top;
1249   }
1250
1251   /**
1252    *
1253    * @return true if tree has real distances
1254    */
1255   public boolean isHasDistances()
1256   {
1257     return hasDistances;
1258   }
1259
1260   /**
1261    *
1262    * @return true if tree has real bootstrap values
1263    */
1264   public boolean isHasBootstrap()
1265   {
1266     return hasBootstrap;
1267   }
1268
1269   public boolean isHasRootDistance()
1270   {
1271     return hasRootDistance;
1272   }
1273
1274 }
1275
1276 /**
1277  * DOCUMENT ME!
1278  *
1279  * @author $author$
1280  * @version $Revision$
1281  */
1282 class Cluster
1283 {
1284   int[] value;
1285
1286   /**
1287    * Creates a new Cluster object.
1288    *
1289    * @param value DOCUMENT ME!
1290    */
1291   public Cluster(int[] value)
1292   {
1293     this.value = value;
1294   }
1295 }