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