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