src/jalview/analysis/NJTree.java

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