src/jalview/analysis/NJTree.java

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