src/jalview/analysis/NJTree.java

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