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