src/jalview/analysis/NJTree.java

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