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(isHasBootstrap(), isHasDistances(),
 312             isHasRootDistance()); // 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   public 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   public 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   public 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   public 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   public 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   public 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   public 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   public 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   public 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   public 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    * Find the leaf node with a particular ycount
 842    *
 843    * @param nd
 844    *          initial point on tree to search from
 845    * @param count
 846    *          value to search for
 847    *
 848    * @return null or the node with ycound=count
 849    */
 850   public Object findLeaf(SequenceNode nd, int count)
 851   {
 852     found = _findLeaf(nd, count);
 853
 854     return found;
 855   }
 856
 857   /*
 858    * #see findLeaf(SequenceNode node, count)
 859    */
 860   public Object _findLeaf(SequenceNode nd, int count)
 861   {
 862     if (nd == null)
 863     {
 864       return null;
 865     }
 866
 867     if (nd.ycount == count)
 868     {
 869       found = nd.element();
 870
 871       return found;
 872     }
 873     else
 874     {
 875       _findLeaf((SequenceNode) nd.left(), count);
 876       _findLeaf((SequenceNode) nd.right(), count);
 877     }
 878
 879     return found;
 880   }
 881
 882   /**
 883    * printNode is mainly for debugging purposes.
 884    *
 885    * @param nd
 886    *          SequenceNode
 887    */
 888   public void printNode(SequenceNode nd)
 889   {
 890     if (nd == null)
 891     {
 892       return;
 893     }
 894
 895     if ((nd.left() == null) && (nd.right() == null))
 896     {
 897       System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
 898       System.out.println("Dist " + nd.dist);
 899       System.out.println("Boot " + nd.getBootstrap());
 900     }
 901     else
 902     {
 903       System.out.println("Dist " + nd.dist);
 904       printNode((SequenceNode) nd.left());
 905       printNode((SequenceNode) nd.right());
 906     }
 907   }
 908
 909   /**
 910    * DOCUMENT ME!
 911    *
 912    * @param nd
 913    *          DOCUMENT ME!
 914    */
 915   public void findMaxDist(SequenceNode nd)
 916   {
 917     if (nd == null)
 918     {
 919       return;
 920     }
 921
 922     if ((nd.left() == null) && (nd.right() == null))
 923     {
 924       double dist = nd.dist;
 925
 926       if (dist > maxDistValue)
 927       {
 928         maxdist = nd;
 929         maxDistValue = dist;
 930       }
 931     }
 932     else
 933     {
 934       findMaxDist((SequenceNode) nd.left());
 935       findMaxDist((SequenceNode) nd.right());
 936     }
 937   }
 938
 939   /**
 940    * DOCUMENT ME!
 941    *
 942    * @return DOCUMENT ME!
 943    */
 944   public Vector<SequenceNode> getGroups()
 945   {
 946     return groups;
 947   }
 948
 949   /**
 950    * DOCUMENT ME!
 951    *
 952    * @return DOCUMENT ME!
 953    */
 954   public double getMaxHeight()
 955   {
 956     return maxheight;
 957   }
 958
 959   /**
 960    * DOCUMENT ME!
 961    *
 962    * @param nd
 963    *          DOCUMENT ME!
 964    * @param threshold
 965    *          DOCUMENT ME!
 966    */
 967   public void groupNodes(SequenceNode nd, float threshold)
 968   {
 969     if (nd == null)
 970     {
 971       return;
 972     }
 973
 974     if ((nd.height / maxheight) > threshold)
 975     {
 976       groups.addElement(nd);
 977     }
 978     else
 979     {
 980       groupNodes((SequenceNode) nd.left(), threshold);
 981       groupNodes((SequenceNode) nd.right(), threshold);
 982     }
 983   }
 984
 985   /**
 986    * DOCUMENT ME!
 987    *
 988    * @param nd
 989    *          DOCUMENT ME!
 990    *
 991    * @return DOCUMENT ME!
 992    */
 993   public double findHeight(SequenceNode nd)
 994   {
 995     if (nd == null)
 996     {
 997       return maxheight;
 998     }
 999
1000     if ((nd.left() == null) && (nd.right() == null))
1001     {
1002       nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
1003
1004       if (nd.height > maxheight)
1005       {
1006         return nd.height;
1007       }
1008       else
1009       {
1010         return maxheight;
1011       }
1012     }
1013     else
1014     {
1015       if (nd.parent() != null)
1016       {
1017         nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
1018       }
1019       else
1020       {
1021         maxheight = 0;
1022         nd.height = (float) 0.0;
1023       }
1024
1025       maxheight = findHeight((SequenceNode) (nd.left()));
1026       maxheight = findHeight((SequenceNode) (nd.right()));
1027     }
1028
1029     return maxheight;
1030   }
1031
1032   /**
1033    * DOCUMENT ME!
1034    *
1035    * @return DOCUMENT ME!
1036    */
1037   public SequenceNode reRoot()
1038   {
1039     if (maxdist != null)
1040     {
1041       ycount = 0;
1042
1043       double tmpdist = maxdist.dist;
1044
1045       // New top
1046       SequenceNode sn = new SequenceNode();
1047       sn.setParent(null);
1048
1049       // New right hand of top
1050       SequenceNode snr = (SequenceNode) maxdist.parent();
1051       changeDirection(snr, maxdist);
1052       System.out.println("Printing reversed tree");
1053       printN(snr);
1054       snr.dist = tmpdist / 2;
1055       maxdist.dist = tmpdist / 2;
1056
1057       snr.setParent(sn);
1058       maxdist.setParent(sn);
1059
1060       sn.setRight(snr);
1061       sn.setLeft(maxdist);
1062
1063       top = sn;
1064
1065       ycount = 0;
1066       reCount(top);
1067       findHeight(top);
1068     }
1069
1070     return top;
1071   }
1072
1073   /**
1074    *
1075    * @return true if original sequence data can be recovered
1076    */
1077   public boolean hasOriginalSequenceData()
1078   {
1079     return seqData != null;
1080   }
1081
1082   /**
1083    * Returns original alignment data used for calculation - or null where not
1084    * available.
1085    *
1086    * @return null or cut'n'pasteable alignment
1087    */
1088   public String printOriginalSequenceData(char gapChar)
1089   {
1090     if (seqData == null)
1091     {
1092       return null;
1093     }
1094
1095     StringBuffer sb = new StringBuffer();
1096     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1097     for (int i = 0; i < seqdatas.length; i++)
1098     {
1099       sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequence[i]
1100               .getName()));
1101       sb.append(" " + seqdatas[i] + "\n");
1102     }
1103     return sb.toString();
1104   }
1105
1106   /**
1107    * DOCUMENT ME!
1108    *
1109    * @param nd
1110    *          DOCUMENT ME!
1111    */
1112   public void printN(SequenceNode nd)
1113   {
1114     if (nd == null)
1115     {
1116       return;
1117     }
1118
1119     if ((nd.left() != null) && (nd.right() != null))
1120     {
1121       printN((SequenceNode) nd.left());
1122       printN((SequenceNode) nd.right());
1123     }
1124     else
1125     {
1126       System.out.println(" name = " + ((SequenceI) nd.element()).getName());
1127     }
1128
1129     System.out.println(" dist = " + nd.dist + " " + nd.count + " "
1130             + nd.height);
1131   }
1132
1133   /**
1134    * DOCUMENT ME!
1135    *
1136    * @param nd
1137    *          DOCUMENT ME!
1138    */
1139   public void reCount(SequenceNode nd)
1140   {
1141     ycount = 0;
1142     _lycount = 0;
1143     // _lylimit = this.node.size();
1144     _reCount(nd);
1145   }
1146
1147   private long _lycount = 0, _lylimit = 0;
1148
1149   /**
1150    * DOCUMENT ME!
1151    *
1152    * @param nd
1153    *          DOCUMENT ME!
1154    */
1155   public void _reCount(SequenceNode nd)
1156   {
1157     // if (_lycount<_lylimit)
1158     // {
1159     // System.err.println("Warning: depth of _recount greater than number of nodes.");
1160     // }
1161     if (nd == null)
1162     {
1163       return;
1164     }
1165     _lycount++;
1166
1167     if ((nd.left() != null) && (nd.right() != null))
1168     {
1169
1170       _reCount((SequenceNode) nd.left());
1171       _reCount((SequenceNode) nd.right());
1172
1173       SequenceNode l = (SequenceNode) nd.left();
1174       SequenceNode r = (SequenceNode) nd.right();
1175
1176       nd.count = l.count + r.count;
1177       nd.ycount = (l.ycount + r.ycount) / 2;
1178     }
1179     else
1180     {
1181       nd.count = 1;
1182       nd.ycount = ycount++;
1183     }
1184     _lycount--;
1185   }
1186
1187   /**
1188    * DOCUMENT ME!
1189    *
1190    * @param nd
1191    *          DOCUMENT ME!
1192    */
1193   public void swapNodes(SequenceNode nd)
1194   {
1195     if (nd == null)
1196     {
1197       return;
1198     }
1199
1200     SequenceNode tmp = (SequenceNode) nd.left();
1201
1202     nd.setLeft(nd.right());
1203     nd.setRight(tmp);
1204   }
1205
1206   /**
1207    * DOCUMENT ME!
1208    *
1209    * @param nd
1210    *          DOCUMENT ME!
1211    * @param dir
1212    *          DOCUMENT ME!
1213    */
1214   public void changeDirection(SequenceNode nd, SequenceNode dir)
1215   {
1216     if (nd == null)
1217     {
1218       return;
1219     }
1220
1221     if (nd.parent() != top)
1222     {
1223       changeDirection((SequenceNode) nd.parent(), nd);
1224
1225       SequenceNode tmp = (SequenceNode) nd.parent();
1226
1227       if (dir == nd.left())
1228       {
1229         nd.setParent(dir);
1230         nd.setLeft(tmp);
1231       }
1232       else if (dir == nd.right())
1233       {
1234         nd.setParent(dir);
1235         nd.setRight(tmp);
1236       }
1237     }
1238     else
1239     {
1240       if (dir == nd.left())
1241       {
1242         nd.setParent(nd.left());
1243
1244         if (top.left() == nd)
1245         {
1246           nd.setRight(top.right());
1247         }
1248         else
1249         {
1250           nd.setRight(top.left());
1251         }
1252       }
1253       else
1254       {
1255         nd.setParent(nd.right());
1256
1257         if (top.left() == nd)
1258         {
1259           nd.setLeft(top.right());
1260         }
1261         else
1262         {
1263           nd.setLeft(top.left());
1264         }
1265       }
1266     }
1267   }
1268
1269   /**
1270    * DOCUMENT ME!
1271    *
1272    * @return DOCUMENT ME!
1273    */
1274   public SequenceNode getMaxDist()
1275   {
1276     return maxdist;
1277   }
1278
1279   /**
1280    * DOCUMENT ME!
1281    *
1282    * @return DOCUMENT ME!
1283    */
1284   public SequenceNode getTopNode()
1285   {
1286     return top;
1287   }
1288
1289   /**
1290    *
1291    * @return true if tree has real distances
1292    */
1293   public boolean isHasDistances()
1294   {
1295     return hasDistances;
1296   }
1297
1298   /**
1299    *
1300    * @return true if tree has real bootstrap values
1301    */
1302   public boolean isHasBootstrap()
1303   {
1304     return hasBootstrap;
1305   }
1306
1307   public boolean isHasRootDistance()
1308   {
1309     return hasRootDistance;
1310   }
1311
1312   /**
1313    * apply the given transform to all the nodes in the tree.
1314    *
1315    * @param nodeTransformI
1316    */
1317   public void applyToNodes(NodeTransformI nodeTransformI)
1318   {
1319     for (Enumeration<SequenceNode> nodes = node.elements(); nodes
1320             .hasMoreElements(); nodeTransformI.transform(nodes
1321             .nextElement()))
1322     {
1323       ;
1324     }
1325   }
1326 }
1327
1328 /**
1329  * DOCUMENT ME!
1330  *
1331  * @author $author$
1332  * @version $Revision$
1333  */
1334 // TODO what does this class have that int[] doesn't have already?
1335 class Cluster
1336 {
1337   int[] value;
1338
1339   /**
1340    * Creates a new Cluster object.
1341    *
1342    * @param value
1343    *          DOCUMENT ME!
1344    */
1345   public Cluster(int[] value)
1346   {
1347     this.value = value;
1348   }
1349 }