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