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