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 + " " + node.count + " "
1103             + node.height);
1104   }
1105
1106   /**
1107    * DOCUMENT ME!
1108    *
1109    * @param node
1110    *          DOCUMENT ME!
1111    */
1112   public void reCount(SequenceNode node)
1113   {
1114     ycount = 0;
1115     _lycount = 0;
1116     // _lylimit = this.node.size();
1117     _reCount(node);
1118   }
1119
1120   private long _lycount = 0, _lylimit = 0;
1121
1122   /**
1123    * DOCUMENT ME!
1124    *
1125    * @param node
1126    *          DOCUMENT ME!
1127    */
1128   public void _reCount(SequenceNode node)
1129   {
1130     // if (_lycount<_lylimit)
1131     // {
1132     // System.err.println("Warning: depth of _recount greater than number of nodes.");
1133     // }
1134     if (node == null)
1135     {
1136       return;
1137     }
1138     _lycount++;
1139
1140     if ((node.left() != null) && (node.right() != null))
1141     {
1142
1143       _reCount((SequenceNode) node.left());
1144       _reCount((SequenceNode) node.right());
1145
1146       SequenceNode l = (SequenceNode) node.left();
1147       SequenceNode r = (SequenceNode) node.right();
1148
1149       node.count = l.count + r.count;
1150       node.ycount = (l.ycount + r.ycount) / 2;
1151     }
1152     else
1153     {
1154       node.count = 1;
1155       node.ycount = ycount++;
1156     }
1157     _lycount--;
1158   }
1159
1160   /**
1161    * DOCUMENT ME!
1162    *
1163    * @param node
1164    *          DOCUMENT ME!
1165    */
1166   public void swapNodes(SequenceNode node)
1167   {
1168     if (node == null)
1169     {
1170       return;
1171     }
1172
1173     SequenceNode tmp = (SequenceNode) node.left();
1174
1175     node.setLeft(node.right());
1176     node.setRight(tmp);
1177   }
1178
1179   /**
1180    * DOCUMENT ME!
1181    *
1182    * @param node
1183    *          DOCUMENT ME!
1184    * @param dir
1185    *          DOCUMENT ME!
1186    */
1187   public void changeDirection(SequenceNode node, SequenceNode dir)
1188   {
1189     if (node == null)
1190     {
1191       return;
1192     }
1193
1194     if (node.parent() != top)
1195     {
1196       changeDirection((SequenceNode) node.parent(), node);
1197
1198       SequenceNode tmp = (SequenceNode) node.parent();
1199
1200       if (dir == node.left())
1201       {
1202         node.setParent(dir);
1203         node.setLeft(tmp);
1204       }
1205       else if (dir == node.right())
1206       {
1207         node.setParent(dir);
1208         node.setRight(tmp);
1209       }
1210     }
1211     else
1212     {
1213       if (dir == node.left())
1214       {
1215         node.setParent(node.left());
1216
1217         if (top.left() == node)
1218         {
1219           node.setRight(top.right());
1220         }
1221         else
1222         {
1223           node.setRight(top.left());
1224         }
1225       }
1226       else
1227       {
1228         node.setParent(node.right());
1229
1230         if (top.left() == node)
1231         {
1232           node.setLeft(top.right());
1233         }
1234         else
1235         {
1236           node.setLeft(top.left());
1237         }
1238       }
1239     }
1240   }
1241
1242   /**
1243    * DOCUMENT ME!
1244    *
1245    * @return DOCUMENT ME!
1246    */
1247   public SequenceNode getMaxDist()
1248   {
1249     return maxdist;
1250   }
1251
1252   /**
1253    * DOCUMENT ME!
1254    *
1255    * @return DOCUMENT ME!
1256    */
1257   public SequenceNode getTopNode()
1258   {
1259     return top;
1260   }
1261
1262   /**
1263    *
1264    * @return true if tree has real distances
1265    */
1266   public boolean isHasDistances()
1267   {
1268     return hasDistances;
1269   }
1270
1271   /**
1272    *
1273    * @return true if tree has real bootstrap values
1274    */
1275   public boolean isHasBootstrap()
1276   {
1277     return hasBootstrap;
1278   }
1279
1280   public boolean isHasRootDistance()
1281   {
1282     return hasRootDistance;
1283   }
1284
1285   /**
1286    * apply the given transform to all the nodes in the tree.
1287    *
1288    * @param nodeTransformI
1289    */
1290   public void applyToNodes(NodeTransformI nodeTransformI)
1291   {
1292     for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
1293             .transform((BinaryNode) nodes.nextElement()))
1294     {
1295       ;
1296     }
1297   }
1298 }
1299
1300 /**
1301  * DOCUMENT ME!
1302  *
1303  * @author $author$
1304  * @version $Revision$
1305  */
1306 class Cluster
1307 {
1308   int[] value;
1309
1310   /**
1311    * Creates a new Cluster object.
1312    *
1313    * @param value
1314    *          DOCUMENT ME!
1315    */
1316   public Cluster(int[] value)
1317   {
1318     this.value = value;
1319   }
1320 }