src/jalview/analysis/NJTree.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Development Version 2.4.1)
   3  * Copyright (C) 2009 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.analysis;
  20
  21 import java.util.*;
  22
  23 import jalview.datamodel.*;
  24 import jalview.io.*;
  25 import jalview.schemes.*;
  26 import jalview.util.*;
  27
  28 /**
  29  * DOCUMENT ME!
  30  *
  31  * @author $author$
  32  * @version $Revision$
  33  */
  34 public class NJTree
  35 {
  36   Vector cluster;
  37
  38   SequenceI[] sequence;
  39
  40   // SequenceData is a string representation of what the user
  41   // sees. The display may contain hidden columns.
  42   public AlignmentView seqData = null;
  43
  44   int[] done;
  45
  46   int noseqs;
  47
  48   int noClus;
  49
  50   float[][] distance;
  51
  52   int mini;
  53
  54   int minj;
  55
  56   float ri;
  57
  58   float rj;
  59
  60   Vector groups = new Vector();
  61
  62   SequenceNode maxdist;
  63
  64   SequenceNode top;
  65
  66   float maxDistValue;
  67
  68   float maxheight;
  69
  70   int ycount;
  71
  72   Vector node;
  73
  74   String type;
  75
  76   String pwtype;
  77
  78   Object found = null;
  79
  80   Object leaves = null;
  81
  82   boolean hasDistances = true; // normal case for jalview trees
  83
  84   boolean hasBootstrap = false; // normal case for jalview trees
  85
  86   private boolean hasRootDistance = true;
  87
  88   /**
  89    * Create a new NJTree object with leaves associated with sequences in seqs,
  90    * and original alignment data represented by Cigar strings.
  91    *
  92    * @param seqs
  93    *                SequenceI[]
  94    * @param odata
  95    *                Cigar[]
  96    * @param treefile
  97    *                NewickFile
  98    */
  99   public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
 100   {
 101     this(seqs, treefile);
 102     if (odata != null)
 103     {
 104       seqData = odata;
 105     }
 106     /*
 107      * sequenceString = new String[odata.length]; char gapChar =
 108      * jalview.util.Comparison.GapChars.charAt(0); for (int i = 0; i <
 109      * odata.length; i++) { SequenceI oseq_aligned = odata[i].getSeq(gapChar);
 110      * sequenceString[i] = oseq_aligned.getSequence(); }
 111      */
 112   }
 113
 114   /**
 115    * Creates a new NJTree object from a tree from an external source
 116    *
 117    * @param seqs
 118    *                SequenceI which should be associated with leafs of treefile
 119    * @param treefile
 120    *                A parsed tree
 121    */
 122   public NJTree(SequenceI[] seqs, NewickFile treefile)
 123   {
 124     this.sequence = seqs;
 125     top = treefile.getTree();
 126
 127     /**
 128      * There is no dependent alignment to be recovered from an imported tree.
 129      *
 130      * if (sequenceString == null) { sequenceString = new String[seqs.length];
 131      * for (int i = 0; i < seqs.length; i++) { sequenceString[i] =
 132      * seqs[i].getSequence(); } }
 133      */
 134
 135     hasDistances = treefile.HasDistances();
 136     hasBootstrap = treefile.HasBootstrap();
 137     hasRootDistance = treefile.HasRootDistance();
 138
 139     maxheight = findHeight(top);
 140
 141     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
 142
 143     Vector leaves = new Vector();
 144     findLeaves(top, leaves);
 145
 146     int i = 0;
 147     int namesleft = seqs.length;
 148
 149     SequenceNode j;
 150     SequenceI nam;
 151     String realnam;
 152     Vector one2many = new Vector();
 153     int countOne2Many = 0;
 154     while (i < leaves.size())
 155     {
 156       j = (SequenceNode) leaves.elementAt(i++);
 157       realnam = j.getName();
 158       nam = null;
 159
 160       if (namesleft > -1)
 161       {
 162         nam = algnIds.findIdMatch(realnam);
 163       }
 164
 165       if (nam != null)
 166       {
 167         j.setElement(nam);
 168         if (one2many.contains(nam))
 169         {
 170           countOne2Many++;
 171           // if (jalview.bin.Cache.log.isDebugEnabled())
 172           // jalview.bin.Cache.log.debug("One 2 many relationship for
 173           // "+nam.getName());
 174         }
 175         else
 176         {
 177           one2many.addElement(nam);
 178           namesleft--;
 179         }
 180       }
 181       else
 182       {
 183         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
 184         j.setPlaceholder(true);
 185       }
 186     }
 187     // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
 188     // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
 189     // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
 190     // more leaves.");
 191     // }
 192     // one2many.clear();
 193   }
 194
 195   /**
 196    * Creates a new NJTree object.
 197    *
 198    * @param sequence
 199    *                DOCUMENT ME!
 200    * @param type
 201    *                DOCUMENT ME!
 202    * @param pwtype
 203    *                DOCUMENT ME!
 204    * @param start
 205    *                DOCUMENT ME!
 206    * @param end
 207    *                DOCUMENT ME!
 208    */
 209   public NJTree(SequenceI[] sequence, AlignmentView seqData, String type,
 210           String pwtype, int start, int end)
 211   {
 212     this.sequence = sequence;
 213     this.node = new Vector();
 214     this.type = type;
 215     this.pwtype = pwtype;
 216     if (seqData != null)
 217     {
 218       this.seqData = seqData;
 219     }
 220     else
 221     {
 222       SeqCigar[] seqs = new SeqCigar[sequence.length];
 223       for (int i = 0; i < sequence.length; i++)
 224       {
 225         seqs[i] = new SeqCigar(sequence[i], start, end);
 226       }
 227       CigarArray sdata = new CigarArray(seqs);
 228       sdata.addOperation(CigarArray.M, end - start + 1);
 229       this.seqData = new AlignmentView(sdata, start);
 230     }
 231 //    System.err.println("Made seqData");// dbg
 232     if (!(type.equals("NJ")))
 233     {
 234       type = "AV";
 235     }
 236
 237     if (!(pwtype.equals("PID")))
 238     {
 239       if (ResidueProperties.getScoreMatrix(pwtype) == null)
 240       {
 241         type = "BLOSUM62";
 242       }
 243     }
 244
 245     int i = 0;
 246
 247     done = new int[sequence.length];
 248
 249     while ((i < sequence.length) && (sequence[i] != null))
 250     {
 251       done[i] = 0;
 252       i++;
 253     }
 254
 255     noseqs = i++;
 256
 257     distance = findDistances(this.seqData
 258             .getSequenceStrings(Comparison.GapChars.charAt(0)));
 259 //    System.err.println("Made distances");// dbg
 260     makeLeaves();
 261 //    System.err.println("Made leaves");// dbg
 262
 263     noClus = cluster.size();
 264
 265     cluster();
 266 //    System.err.println("Made clusters");// dbg
 267
 268   }
 269
 270   /**
 271    * DOCUMENT ME!
 272    *
 273    * @return DOCUMENT ME!
 274    */
 275   public String toString()
 276   {
 277     jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
 278
 279     return fout.print(false, true); // distances only
 280   }
 281
 282   /**
 283    *
 284    * used when the alignment associated to a tree has changed.
 285    *
 286    * @param alignment
 287    *                Vector
 288    */
 289   public void UpdatePlaceHolders(Vector alignment)
 290   {
 291     Vector leaves = new Vector();
 292     findLeaves(top, leaves);
 293
 294     int sz = leaves.size();
 295     SequenceIdMatcher seqmatcher = null;
 296     int i = 0;
 297
 298     while (i < sz)
 299     {
 300       SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
 301
 302       if (alignment.contains(leaf.element()))
 303       {
 304         leaf.setPlaceholder(false);
 305       }
 306       else
 307       {
 308         if (seqmatcher == null)
 309         {
 310           // Only create this the first time we need it
 311           SequenceI[] seqs = new SequenceI[alignment.size()];
 312
 313           for (int j = 0; j < seqs.length; j++)
 314           {
 315             seqs[j] = (SequenceI) alignment.elementAt(j);
 316           }
 317
 318           seqmatcher = new SequenceIdMatcher(seqs);
 319         }
 320
 321         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
 322
 323         if (nam != null)
 324         {
 325           if (!leaf.isPlaceholder())
 326           {
 327             // remapping the node to a new sequenceI - should remove any refs to
 328             // old one.
 329             // TODO - make many sequenceI to one leaf mappings possible!
 330             // (JBPNote)
 331           }
 332           leaf.setPlaceholder(false);
 333           leaf.setElement(nam);
 334         }
 335         else
 336         {
 337           if (!leaf.isPlaceholder())
 338           {
 339             // Construct a new placeholder sequence object for this leaf
 340             leaf.setElement(new Sequence(leaf.getName(),
 341                     "THISISAPLACEHLDER"));
 342           }
 343           leaf.setPlaceholder(true);
 344
 345         }
 346       }
 347     }
 348   }
 349
 350   /**
 351    * DOCUMENT ME!
 352    */
 353   public void cluster()
 354   {
 355     while (noClus > 2)
 356     {
 357       if (type.equals("NJ"))
 358       {
 359         findMinNJDistance();
 360       }
 361       else
 362       {
 363         findMinDistance();
 364       }
 365
 366       Cluster c = joinClusters(mini, minj);
 367
 368       done[minj] = 1;
 369
 370       cluster.setElementAt(null, minj);
 371       cluster.setElementAt(c, mini);
 372
 373       noClus--;
 374     }
 375
 376     boolean onefound = false;
 377
 378     int one = -1;
 379     int two = -1;
 380
 381     for (int i = 0; i < noseqs; i++)
 382     {
 383       if (done[i] != 1)
 384       {
 385         if (onefound == false)
 386         {
 387           two = i;
 388           onefound = true;
 389         }
 390         else
 391         {
 392           one = i;
 393         }
 394       }
 395     }
 396
 397     joinClusters(one, two);
 398     top = (SequenceNode) (node.elementAt(one));
 399
 400     reCount(top);
 401     findHeight(top);
 402     findMaxDist(top);
 403   }
 404
 405   /**
 406    * DOCUMENT ME!
 407    *
 408    * @param i
 409    *                DOCUMENT ME!
 410    * @param j
 411    *                DOCUMENT ME!
 412    *
 413    * @return DOCUMENT ME!
 414    */
 415   public Cluster joinClusters(int i, int j)
 416   {
 417     float dist = distance[i][j];
 418
 419     int noi = ((Cluster) cluster.elementAt(i)).value.length;
 420     int noj = ((Cluster) cluster.elementAt(j)).value.length;
 421
 422     int[] value = new int[noi + noj];
 423
 424     for (int ii = 0; ii < noi; ii++)
 425     {
 426       value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
 427     }
 428
 429     for (int ii = noi; ii < (noi + noj); ii++)
 430     {
 431       value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
 432     }
 433
 434     Cluster c = new Cluster(value);
 435
 436     ri = findr(i, j);
 437     rj = findr(j, i);
 438
 439     if (type.equals("NJ"))
 440     {
 441       findClusterNJDistance(i, j);
 442     }
 443     else
 444     {
 445       findClusterDistance(i, j);
 446     }
 447
 448     SequenceNode sn = new SequenceNode();
 449
 450     sn.setLeft((SequenceNode) (node.elementAt(i)));
 451     sn.setRight((SequenceNode) (node.elementAt(j)));
 452
 453     SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
 454     SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
 455
 456     if (type.equals("NJ"))
 457     {
 458       findNewNJDistances(tmpi, tmpj, dist);
 459     }
 460     else
 461     {
 462       findNewDistances(tmpi, tmpj, dist);
 463     }
 464
 465     tmpi.setParent(sn);
 466     tmpj.setParent(sn);
 467
 468     node.setElementAt(sn, i);
 469
 470     return c;
 471   }
 472
 473   /**
 474    * DOCUMENT ME!
 475    *
 476    * @param tmpi
 477    *                DOCUMENT ME!
 478    * @param tmpj
 479    *                DOCUMENT ME!
 480    * @param dist
 481    *                DOCUMENT ME!
 482    */
 483   public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
 484           float dist)
 485   {
 486
 487     tmpi.dist = ((dist + ri) - rj) / 2;
 488     tmpj.dist = (dist - tmpi.dist);
 489
 490     if (tmpi.dist < 0)
 491     {
 492       tmpi.dist = 0;
 493     }
 494
 495     if (tmpj.dist < 0)
 496     {
 497       tmpj.dist = 0;
 498     }
 499   }
 500
 501   /**
 502    * DOCUMENT ME!
 503    *
 504    * @param tmpi
 505    *                DOCUMENT ME!
 506    * @param tmpj
 507    *                DOCUMENT ME!
 508    * @param dist
 509    *                DOCUMENT ME!
 510    */
 511   public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
 512           float dist)
 513   {
 514     float ih = 0;
 515     float jh = 0;
 516
 517     SequenceNode sni = tmpi;
 518     SequenceNode snj = tmpj;
 519
 520     while (sni != null)
 521     {
 522       ih = ih + sni.dist;
 523       sni = (SequenceNode) sni.left();
 524     }
 525
 526     while (snj != null)
 527     {
 528       jh = jh + snj.dist;
 529       snj = (SequenceNode) snj.left();
 530     }
 531
 532     tmpi.dist = ((dist / 2) - ih);
 533     tmpj.dist = ((dist / 2) - jh);
 534   }
 535
 536   /**
 537    * DOCUMENT ME!
 538    *
 539    * @param i
 540    *                DOCUMENT ME!
 541    * @param j
 542    *                DOCUMENT ME!
 543    */
 544   public void findClusterDistance(int i, int j)
 545   {
 546     int noi = ((Cluster) cluster.elementAt(i)).value.length;
 547     int noj = ((Cluster) cluster.elementAt(j)).value.length;
 548
 549     // New distances from cluster to others
 550     float[] newdist = new float[noseqs];
 551
 552     for (int l = 0; l < noseqs; l++)
 553     {
 554       if ((l != i) && (l != j))
 555       {
 556         newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
 557                 / (noi + noj);
 558       }
 559       else
 560       {
 561         newdist[l] = 0;
 562       }
 563     }
 564
 565     for (int ii = 0; ii < noseqs; ii++)
 566     {
 567       distance[i][ii] = newdist[ii];
 568       distance[ii][i] = newdist[ii];
 569     }
 570   }
 571
 572   /**
 573    * DOCUMENT ME!
 574    *
 575    * @param i
 576    *                DOCUMENT ME!
 577    * @param j
 578    *                DOCUMENT ME!
 579    */
 580   public void findClusterNJDistance(int i, int j)
 581   {
 582
 583     // New distances from cluster to others
 584     float[] newdist = new float[noseqs];
 585
 586     for (int l = 0; l < noseqs; l++)
 587     {
 588       if ((l != i) && (l != j))
 589       {
 590         newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) / 2;
 591       }
 592       else
 593       {
 594         newdist[l] = 0;
 595       }
 596     }
 597
 598     for (int ii = 0; ii < noseqs; ii++)
 599     {
 600       distance[i][ii] = newdist[ii];
 601       distance[ii][i] = newdist[ii];
 602     }
 603   }
 604
 605   /**
 606    * DOCUMENT ME!
 607    *
 608    * @param i
 609    *                DOCUMENT ME!
 610    * @param j
 611    *                DOCUMENT ME!
 612    *
 613    * @return DOCUMENT ME!
 614    */
 615   public float findr(int i, int j)
 616   {
 617     float tmp = 1;
 618
 619     for (int k = 0; k < noseqs; k++)
 620     {
 621       if ((k != i) && (k != j) && (done[k] != 1))
 622       {
 623         tmp = tmp + distance[i][k];
 624       }
 625     }
 626
 627     if (noClus > 2)
 628     {
 629       tmp = tmp / (noClus - 2);
 630     }
 631
 632     return tmp;
 633   }
 634
 635   /**
 636    * DOCUMENT ME!
 637    *
 638    * @return DOCUMENT ME!
 639    */
 640   public float findMinNJDistance()
 641   {
 642     float min = 100000;
 643
 644     for (int i = 0; i < (noseqs - 1); i++)
 645     {
 646       for (int j = i + 1; j < noseqs; j++)
 647       {
 648         if ((done[i] != 1) && (done[j] != 1))
 649         {
 650           float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
 651
 652           if (tmp < min)
 653           {
 654             mini = i;
 655             minj = j;
 656
 657             min = tmp;
 658           }
 659         }
 660       }
 661     }
 662
 663     return min;
 664   }
 665
 666   /**
 667    * DOCUMENT ME!
 668    *
 669    * @return DOCUMENT ME!
 670    */
 671   public float findMinDistance()
 672   {
 673     float min = 100000;
 674
 675     for (int i = 0; i < (noseqs - 1); i++)
 676     {
 677       for (int j = i + 1; j < noseqs; j++)
 678       {
 679         if ((done[i] != 1) && (done[j] != 1))
 680         {
 681           if (distance[i][j] < min)
 682           {
 683             mini = i;
 684             minj = j;
 685
 686             min = distance[i][j];
 687           }
 688         }
 689       }
 690     }
 691
 692     return min;
 693   }
 694
 695   /**
 696    * DOCUMENT ME!
 697    *
 698    * @return DOCUMENT ME!
 699    */
 700   public float[][] findDistances(String[] sequenceString)
 701   {
 702     float[][] distance = new float[noseqs][noseqs];
 703
 704     if (pwtype.equals("PID"))
 705     {
 706       for (int i = 0; i < (noseqs - 1); i++)
 707       {
 708         for (int j = i; j < noseqs; j++)
 709         {
 710           if (j == i)
 711           {
 712             distance[i][i] = 0;
 713           }
 714           else
 715           {
 716             distance[i][j] = 100 - Comparison.PID(sequenceString[i],
 717                     sequenceString[j]);
 718
 719             distance[j][i] = distance[i][j];
 720           }
 721         }
 722       }
 723     }
 724     else
 725     {
 726       // Pairwise substitution score (with no gap penalties)
 727       ScoreMatrix pwmatrix = ResidueProperties.getScoreMatrix(pwtype);
 728       if (pwmatrix == null)
 729       {
 730         pwmatrix = ResidueProperties.getScoreMatrix("BLOSUM62");
 731       }
 732       int maxscore = 0;
 733       int end = sequenceString[0].length();
 734       for (int i = 0; i < (noseqs - 1); i++)
 735       {
 736         for (int j = i; j < noseqs; j++)
 737         {
 738           int score = 0;
 739
 740           for (int k = 0; k < end; k++)
 741           {
 742             try
 743             {
 744               score += pwmatrix.getPairwiseScore(sequenceString[i]
 745                       .charAt(k), 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    * DOCUMENT ME!
 792    */
 793   public void makeLeaves()
 794   {
 795     cluster = new Vector();
 796
 797     for (int i = 0; i < noseqs; i++)
 798     {
 799       SequenceNode sn = new SequenceNode();
 800
 801       sn.setElement(sequence[i]);
 802       sn.setName(sequence[i].getName());
 803       node.addElement(sn);
 804
 805       int[] value = new int[1];
 806       value[0] = i;
 807
 808       Cluster c = new Cluster(value);
 809       cluster.addElement(c);
 810     }
 811   }
 812
 813   /**
 814    * Search for leaf nodes.
 815    *
 816    * @param node
 817    *                root node to search from
 818    * @param leaves
 819    *                Vector of leaves to add leaf node objects too.
 820    *
 821    * @return Vector of leaf nodes on binary tree
 822    */
 823   public Vector findLeaves(SequenceNode node, Vector leaves)
 824   {
 825     if (node == null)
 826     {
 827       return leaves;
 828     }
 829
 830     if ((node.left() == null) && (node.right() == null)) // Interior node
 831                                                           // detection
 832     {
 833       leaves.addElement(node);
 834
 835       return leaves;
 836     }
 837     else
 838     {
 839       /*
 840        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
 841        * leaves.addElement(node); }
 842        */
 843       findLeaves((SequenceNode) node.left(), leaves);
 844       findLeaves((SequenceNode) node.right(), leaves);
 845     }
 846
 847     return leaves;
 848   }
 849
 850   /**
 851    * Find the leaf node with a particular ycount
 852    *
 853    * @param node
 854    *                initial point on tree to search from
 855    * @param count
 856    *                value to search for
 857    *
 858    * @return null or the node with ycound=count
 859    */
 860   public Object findLeaf(SequenceNode node, int count)
 861   {
 862     found = _findLeaf(node, count);
 863
 864     return found;
 865   }
 866
 867   /*
 868    * #see findLeaf(SequenceNode node, count)
 869    *
 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   private long _lycount=0,_lylimit=0;
1161   /**
1162    * DOCUMENT ME!
1163    *
1164    * @param node
1165    *                DOCUMENT ME!
1166    */
1167   public void _reCount(SequenceNode node)
1168   {
1169 //    if (_lycount<_lylimit)
1170 //    {
1171 //      System.err.println("Warning: depth of _recount greater than number of nodes.");
1172 //    }
1173     if (node == null)
1174     {
1175       return;
1176     }
1177     _lycount++;
1178
1179     if ((node.left() != null) && (node.right() != null))
1180     {
1181
1182       _reCount((SequenceNode) node.left());
1183       _reCount((SequenceNode) node.right());
1184
1185       SequenceNode l = (SequenceNode) node.left();
1186       SequenceNode r = (SequenceNode) node.right();
1187
1188       ((SequenceNode) node).count = l.count + r.count;
1189       ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1190     }
1191     else
1192     {
1193       ((SequenceNode) node).count = 1;
1194       ((SequenceNode) node).ycount = ycount++;
1195     }
1196     _lycount--;
1197   }
1198
1199   /**
1200    * DOCUMENT ME!
1201    *
1202    * @param node
1203    *                DOCUMENT ME!
1204    */
1205   public void swapNodes(SequenceNode node)
1206   {
1207     if (node == null)
1208     {
1209       return;
1210     }
1211
1212     SequenceNode tmp = (SequenceNode) node.left();
1213
1214     node.setLeft(node.right());
1215     node.setRight(tmp);
1216   }
1217
1218   /**
1219    * DOCUMENT ME!
1220    *
1221    * @param node
1222    *                DOCUMENT ME!
1223    * @param dir
1224    *                DOCUMENT ME!
1225    */
1226   public void changeDirection(SequenceNode node, SequenceNode dir)
1227   {
1228     if (node == null)
1229     {
1230       return;
1231     }
1232
1233     if (node.parent() != top)
1234     {
1235       changeDirection((SequenceNode) node.parent(), node);
1236
1237       SequenceNode tmp = (SequenceNode) node.parent();
1238
1239       if (dir == node.left())
1240       {
1241         node.setParent(dir);
1242         node.setLeft(tmp);
1243       }
1244       else if (dir == node.right())
1245       {
1246         node.setParent(dir);
1247         node.setRight(tmp);
1248       }
1249     }
1250     else
1251     {
1252       if (dir == node.left())
1253       {
1254         node.setParent(node.left());
1255
1256         if (top.left() == node)
1257         {
1258           node.setRight(top.right());
1259         }
1260         else
1261         {
1262           node.setRight(top.left());
1263         }
1264       }
1265       else
1266       {
1267         node.setParent(node.right());
1268
1269         if (top.left() == node)
1270         {
1271           node.setLeft(top.right());
1272         }
1273         else
1274         {
1275           node.setLeft(top.left());
1276         }
1277       }
1278     }
1279   }
1280
1281   /**
1282    * DOCUMENT ME!
1283    *
1284    * @return DOCUMENT ME!
1285    */
1286   public SequenceNode getMaxDist()
1287   {
1288     return maxdist;
1289   }
1290
1291   /**
1292    * DOCUMENT ME!
1293    *
1294    * @return DOCUMENT ME!
1295    */
1296   public SequenceNode getTopNode()
1297   {
1298     return top;
1299   }
1300
1301   /**
1302    *
1303    * @return true if tree has real distances
1304    */
1305   public boolean isHasDistances()
1306   {
1307     return hasDistances;
1308   }
1309
1310   /**
1311    *
1312    * @return true if tree has real bootstrap values
1313    */
1314   public boolean isHasBootstrap()
1315   {
1316     return hasBootstrap;
1317   }
1318
1319   public boolean isHasRootDistance()
1320   {
1321     return hasRootDistance;
1322   }
1323   /**
1324    * apply the given transform to all the nodes in the tree.
1325    * @param nodeTransformI
1326    */
1327   public void applyToNodes(NodeTransformI nodeTransformI)
1328   {
1329     for (Enumeration nodes = node.elements(); nodes.hasMoreElements();
1330       nodeTransformI.transform((BinaryNode)nodes.nextElement()))
1331       ;
1332   }
1333 }
1334
1335 /**
1336  * DOCUMENT ME!
1337  *
1338  * @author $author$
1339  * @version $Revision$
1340  */
1341 class Cluster
1342 {
1343   int[] value;
1344
1345   /**
1346    * Creates a new Cluster object.
1347    *
1348    * @param value
1349    *                DOCUMENT ME!
1350    */
1351   public Cluster(int[] value)
1352   {
1353     this.value = value;
1354   }
1355 }