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