src/jalview/analysis/NJTree.java

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