src/jalview/analysis/NJTree.java

   1 /*
   2 * Jalview - A Sequence Alignment Editor and Viewer
   3 * Copyright (C) 2006 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 jalview.datamodel.*;
  22
  23 import jalview.io.NewickFile;
  24
  25 import jalview.schemes.ResidueProperties;
  26
  27 import jalview.util.*;
  28
  29 import java.util.*;
  30
  31
  32 /**
  33  * DOCUMENT ME!
  34  *
  35  * @author $author$
  36  * @version $Revision$
  37  */
  38 public class NJTree
  39 {
  40     Vector cluster;
  41     SequenceI[] sequence;
  42
  43     //SequenceData is a string representation of what the user
  44     //sees. The display may contain hidden columns.
  45     public AlignmentView seqData=null;
  46
  47     int[] done;
  48     int noseqs;
  49     int noClus;
  50     float[][] distance;
  51     int mini;
  52     int minj;
  53     float ri;
  54     float rj;
  55     Vector groups = new Vector();
  56     SequenceNode maxdist;
  57     SequenceNode top;
  58     float maxDistValue;
  59     float maxheight;
  60     int ycount;
  61     Vector node;
  62     String type;
  63     String pwtype;
  64     Object found = null;
  65     Object leaves = null;
  66
  67     boolean hasDistances = true; // normal case for jalview trees
  68     boolean hasBootstrap = false; // normal case for jalview trees
  69
  70     private boolean hasRootDistance = true;
  71
  72     /**
  73      * Create a new NJTree object with leaves associated with sequences in seqs,
  74      * and original alignment data represented by Cigar strings.
  75      * @param seqs SequenceI[]
  76      * @param odata Cigar[]
  77      * @param treefile NewickFile
  78      */
  79     public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile) {
  80       this(seqs, treefile);
  81       if (odata!=null)
  82         seqData = odata;
  83       /*
  84       sequenceString = new String[odata.length];
  85       char gapChar = jalview.util.Comparison.GapChars.charAt(0);
  86       for (int i = 0; i < odata.length; i++)
  87       {
  88         SequenceI oseq_aligned = odata[i].getSeq(gapChar);
  89           sequenceString[i] = oseq_aligned.getSequence();
  90       } */
  91     }
  92
  93     /**
  94      * Creates a new NJTree object from a tree from an external source
  95      *
  96      * @param seqs SequenceI which should be associated with leafs of treefile
  97      * @param treefile A parsed tree
  98      */
  99     public NJTree(SequenceI[] seqs,  NewickFile treefile)
 100     {
 101         this.sequence = seqs;
 102         top = treefile.getTree();
 103
 104         /**
 105          * There is no dependent alignment to be recovered from an
 106          * imported tree.
 107          *
 108         if (sequenceString == null)
 109         {
 110           sequenceString = new String[seqs.length];
 111           for (int i = 0; i < seqs.length; i++)
 112           {
 113             sequenceString[i] = seqs[i].getSequence();
 114           }
 115         }
 116         */
 117
 118         hasDistances = treefile.HasDistances();
 119         hasBootstrap = treefile.HasBootstrap();
 120         hasRootDistance = treefile.HasRootDistance();
 121
 122         maxheight = findHeight(top);
 123
 124         SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
 125
 126         Vector leaves = new Vector();
 127         findLeaves(top, leaves);
 128
 129         int i = 0;
 130         int namesleft = seqs.length;
 131
 132         SequenceNode j;
 133         SequenceI nam;
 134         String realnam;
 135         Vector one2many=new Vector();
 136         int countOne2Many=0;
 137         while (i < leaves.size())
 138         {
 139             j = (SequenceNode) leaves.elementAt(i++);
 140             realnam = j.getName();
 141             nam = null;
 142
 143             if (namesleft > -1)
 144             {
 145                 nam = algnIds.findIdMatch(realnam);
 146             }
 147
 148             if (nam != null)
 149             {
 150                 j.setElement(nam);
 151                 if (one2many.contains(nam)) {
 152                   countOne2Many++;
 153                 //  if (jalview.bin.Cache.log.isDebugEnabled())
 154                 //    jalview.bin.Cache.log.debug("One 2 many relationship for "+nam.getName());
 155                 } else {
 156                   one2many.addElement(nam);
 157                   namesleft--;
 158                 }
 159             }
 160             else
 161             {
 162                 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
 163                 j.setPlaceholder(true);
 164             }
 165         }
 166       //  if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
 167       //    jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment sequence ids (out of "+one2many.size()+" unique ids) linked to two or more leaves.");
 168       //  }
 169       //  one2many.clear();
 170     }
 171
 172     /**
 173      * Creates a new NJTree object.
 174      *
 175      * @param sequence DOCUMENT ME!
 176      * @param type DOCUMENT ME!
 177      * @param pwtype DOCUMENT ME!
 178      * @param start DOCUMENT ME!
 179      * @param end DOCUMENT ME!
 180      */
 181     public NJTree(SequenceI[] sequence,
 182                   AlignmentView seqData,
 183                   String type,
 184                   String pwtype,
 185                   int start, int end)
 186     {
 187         this.sequence = sequence;
 188         this.node = new Vector();
 189         this.type = type;
 190         this.pwtype = pwtype;
 191         if (seqData!=null) {
 192           this.seqData = seqData;
 193         } else {
 194           SeqCigar[] seqs = new SeqCigar[sequence.length];
 195           for(int i=0; i<sequence.length; i++)
 196             {
 197               seqs[i] = new SeqCigar(sequence[i], start, end);
 198             }
 199             CigarArray sdata = new CigarArray(seqs);
 200             sdata.addOperation(CigarArray.M, end-start+1);
 201             this.seqData = new AlignmentView(sdata, start);
 202         }
 203
 204         if (!(type.equals("NJ")))
 205         {
 206             type = "AV";
 207         }
 208
 209         if (!(pwtype.equals("PID")))
 210         {
 211             type = "BL";
 212         }
 213
 214         int i = 0;
 215
 216         done = new int[sequence.length];
 217
 218         while ((i < sequence.length) && (sequence[i] != null))
 219         {
 220             done[i] = 0;
 221             i++;
 222         }
 223
 224         noseqs = i++;
 225
 226         distance = findDistances(this.seqData.getSequenceStrings(Comparison.GapChars.charAt(0)));
 227
 228         makeLeaves();
 229
 230         noClus = cluster.size();
 231
 232         cluster();
 233     }
 234
 235     /**
 236      * DOCUMENT ME!
 237      *
 238      * @return DOCUMENT ME!
 239      */
 240     public String toString()
 241     {
 242         jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
 243
 244         return fout.print(false, true); // distances only
 245     }
 246
 247     /**
 248      *
 249      * used when the alignment associated to a tree has changed.
 250      *
 251      * @param alignment Vector
 252      */
 253     public void UpdatePlaceHolders(Vector alignment)
 254     {
 255         Vector leaves = new Vector();
 256         findLeaves(top, leaves);
 257
 258         int sz = leaves.size();
 259         SequenceIdMatcher seqmatcher = null;
 260         int i = 0;
 261
 262         while (i < sz)
 263         {
 264             SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
 265
 266             if (alignment.contains(leaf.element()))
 267             {
 268                 leaf.setPlaceholder(false);
 269             }
 270             else
 271             {
 272                 if (seqmatcher == null)
 273                 {
 274                     // Only create this the first time we need it
 275                     SequenceI[] seqs = new SequenceI[alignment.size()];
 276
 277                     for (int j = 0; j < seqs.length; j++)
 278                         seqs[j] = (SequenceI) alignment.elementAt(j);
 279
 280                     seqmatcher = new SequenceIdMatcher(seqs);
 281                 }
 282
 283                 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
 284
 285                 if (nam != null)
 286                 {
 287                     if (!leaf.isPlaceholder()) {
 288                       // remapping the node to a new sequenceI - should remove any refs to old one.
 289                       // TODO - make many sequenceI to one leaf mappings possible! (JBPNote)
 290                     }
 291                     leaf.setPlaceholder(false);
 292                     leaf.setElement(nam);
 293                 }
 294                 else
 295                 {
 296                     if (!leaf.isPlaceholder()) {
 297                         // Construct a new placeholder sequence object for this leaf
 298                         leaf.setElement(new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
 299                     }
 300                     leaf.setPlaceholder(true);
 301
 302                 }
 303             }
 304         }
 305     }
 306
 307     /**
 308      * DOCUMENT ME!
 309      */
 310     public void cluster()
 311     {
 312         while (noClus > 2)
 313         {
 314             if (type.equals("NJ"))
 315             {
 316                 findMinNJDistance();
 317             }
 318             else
 319             {
 320                 findMinDistance();
 321             }
 322
 323             Cluster c = joinClusters(mini, minj);
 324
 325             done[minj] = 1;
 326
 327             cluster.setElementAt(null, minj);
 328             cluster.setElementAt(c, mini);
 329
 330             noClus--;
 331         }
 332
 333         boolean onefound = false;
 334
 335         int one = -1;
 336         int two = -1;
 337
 338         for (int i = 0; i < noseqs; i++)
 339         {
 340             if (done[i] != 1)
 341             {
 342                 if (onefound == false)
 343                 {
 344                     two = i;
 345                     onefound = true;
 346                 }
 347                 else
 348                 {
 349                     one = i;
 350                 }
 351             }
 352         }
 353
 354         joinClusters(one, two);
 355         top = (SequenceNode) (node.elementAt(one));
 356
 357         reCount(top);
 358         findHeight(top);
 359         findMaxDist(top);
 360     }
 361
 362     /**
 363      * DOCUMENT ME!
 364      *
 365      * @param i DOCUMENT ME!
 366      * @param j DOCUMENT ME!
 367      *
 368      * @return DOCUMENT ME!
 369      */
 370     public Cluster joinClusters(int i, int j)
 371     {
 372         float dist = distance[i][j];
 373
 374         int noi = ((Cluster) cluster.elementAt(i)).value.length;
 375         int noj = ((Cluster) cluster.elementAt(j)).value.length;
 376
 377         int[] value = new int[noi + noj];
 378
 379         for (int ii = 0; ii < noi; ii++)
 380         {
 381             value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
 382         }
 383
 384         for (int ii = noi; ii < (noi + noj); ii++)
 385         {
 386             value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
 387         }
 388
 389         Cluster c = new Cluster(value);
 390
 391         ri = findr(i, j);
 392         rj = findr(j, i);
 393
 394         if (type.equals("NJ"))
 395         {
 396             findClusterNJDistance(i, j);
 397         }
 398         else
 399         {
 400             findClusterDistance(i, j);
 401         }
 402
 403         SequenceNode sn = new SequenceNode();
 404
 405         sn.setLeft((SequenceNode) (node.elementAt(i)));
 406         sn.setRight((SequenceNode) (node.elementAt(j)));
 407
 408         SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
 409         SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
 410
 411         if (type.equals("NJ"))
 412         {
 413             findNewNJDistances(tmpi, tmpj, dist);
 414         }
 415         else
 416         {
 417             findNewDistances(tmpi, tmpj, dist);
 418         }
 419
 420         tmpi.setParent(sn);
 421         tmpj.setParent(sn);
 422
 423         node.setElementAt(sn, i);
 424
 425         return c;
 426     }
 427
 428     /**
 429      * DOCUMENT ME!
 430      *
 431      * @param tmpi DOCUMENT ME!
 432      * @param tmpj DOCUMENT ME!
 433      * @param dist DOCUMENT ME!
 434      */
 435     public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
 436         float dist)
 437     {
 438
 439         tmpi.dist = ((dist + ri) - rj) / 2;
 440         tmpj.dist = (dist - tmpi.dist);
 441
 442         if (tmpi.dist < 0)
 443         {
 444             tmpi.dist = 0;
 445         }
 446
 447         if (tmpj.dist < 0)
 448         {
 449             tmpj.dist = 0;
 450         }
 451     }
 452
 453     /**
 454      * DOCUMENT ME!
 455      *
 456      * @param tmpi DOCUMENT ME!
 457      * @param tmpj DOCUMENT ME!
 458      * @param dist DOCUMENT ME!
 459      */
 460     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
 461         float dist)
 462     {
 463         float ih = 0;
 464         float jh = 0;
 465
 466         SequenceNode sni = tmpi;
 467         SequenceNode snj = tmpj;
 468
 469         while (sni != null)
 470         {
 471             ih = ih + sni.dist;
 472             sni = (SequenceNode) sni.left();
 473         }
 474
 475         while (snj != null)
 476         {
 477             jh = jh + snj.dist;
 478             snj = (SequenceNode) snj.left();
 479         }
 480
 481         tmpi.dist = ((dist / 2) - ih);
 482         tmpj.dist = ((dist / 2) - jh);
 483     }
 484
 485     /**
 486      * DOCUMENT ME!
 487      *
 488      * @param i DOCUMENT ME!
 489      * @param j DOCUMENT ME!
 490      */
 491     public void findClusterDistance(int i, int j)
 492     {
 493         int noi = ((Cluster) cluster.elementAt(i)).value.length;
 494         int noj = ((Cluster) cluster.elementAt(j)).value.length;
 495
 496         // New distances from cluster to others
 497         float[] newdist = new float[noseqs];
 498
 499         for (int l = 0; l < noseqs; l++)
 500         {
 501             if ((l != i) && (l != j))
 502             {
 503                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +
 504                     noj);
 505             }
 506             else
 507             {
 508                 newdist[l] = 0;
 509             }
 510         }
 511
 512         for (int ii = 0; ii < noseqs; ii++)
 513         {
 514             distance[i][ii] = newdist[ii];
 515             distance[ii][i] = newdist[ii];
 516         }
 517     }
 518
 519     /**
 520      * DOCUMENT ME!
 521      *
 522      * @param i DOCUMENT ME!
 523      * @param j DOCUMENT ME!
 524      */
 525     public void findClusterNJDistance(int i, int j)
 526     {
 527
 528         // New distances from cluster to others
 529         float[] newdist = new float[noseqs];
 530
 531         for (int l = 0; l < noseqs; l++)
 532         {
 533             if ((l != i) && (l != j))
 534             {
 535                 newdist[l] = ((distance[i][l] + distance[j][l]) -
 536                     distance[i][j]) / 2;
 537             }
 538             else
 539             {
 540                 newdist[l] = 0;
 541             }
 542         }
 543
 544         for (int ii = 0; ii < noseqs; ii++)
 545         {
 546             distance[i][ii] = newdist[ii];
 547             distance[ii][i] = newdist[ii];
 548         }
 549     }
 550
 551     /**
 552      * DOCUMENT ME!
 553      *
 554      * @param i DOCUMENT ME!
 555      * @param j DOCUMENT ME!
 556      *
 557      * @return DOCUMENT ME!
 558      */
 559     public float findr(int i, int j)
 560     {
 561         float tmp = 1;
 562
 563         for (int k = 0; k < noseqs; k++)
 564         {
 565             if ((k != i) && (k != j) && (done[k] != 1))
 566             {
 567                 tmp = tmp + distance[i][k];
 568             }
 569         }
 570
 571         if (noClus > 2)
 572         {
 573             tmp = tmp / (noClus - 2);
 574         }
 575
 576         return tmp;
 577     }
 578
 579     /**
 580      * DOCUMENT ME!
 581      *
 582      * @return DOCUMENT ME!
 583      */
 584     public float findMinNJDistance()
 585     {
 586         float min = 100000;
 587
 588         for (int i = 0; i < (noseqs - 1); i++)
 589         {
 590             for (int j = i + 1; j < noseqs; j++)
 591             {
 592                 if ((done[i] != 1) && (done[j] != 1))
 593                 {
 594                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
 595
 596                     if (tmp < min)
 597                     {
 598                         mini = i;
 599                         minj = j;
 600
 601                         min = tmp;
 602                     }
 603                 }
 604             }
 605         }
 606
 607         return min;
 608     }
 609
 610     /**
 611      * DOCUMENT ME!
 612      *
 613      * @return DOCUMENT ME!
 614      */
 615     public float findMinDistance()
 616     {
 617         float min = 100000;
 618
 619         for (int i = 0; i < (noseqs - 1); i++)
 620         {
 621             for (int j = i + 1; j < noseqs; j++)
 622             {
 623                 if ((done[i] != 1) && (done[j] != 1))
 624                 {
 625                     if (distance[i][j] < min)
 626                     {
 627                         mini = i;
 628                         minj = j;
 629
 630                         min = distance[i][j];
 631                     }
 632                 }
 633             }
 634         }
 635
 636         return min;
 637     }
 638
 639     /**
 640      * DOCUMENT ME!
 641      *
 642      * @return DOCUMENT ME!
 643      */
 644     public float[][] findDistances(String[] sequenceString)
 645     {
 646         float[][] distance = new float[noseqs][noseqs];
 647
 648         if (pwtype.equals("PID"))
 649         {
 650             for (int i = 0; i < (noseqs - 1); i++)
 651             {
 652                 for (int j = i; j < noseqs; j++)
 653                 {
 654                     if (j == i)
 655                     {
 656                         distance[i][i] = 0;
 657                     }
 658                     else
 659                     {
 660                         distance[i][j] = 100 -
 661                              Comparison.PID(sequenceString[i], sequenceString[j]);
 662
 663                         distance[j][i] = distance[i][j];
 664                     }
 665                 }
 666             }
 667         }
 668         else if (pwtype.equals("BL"))
 669         {
 670             int maxscore = 0;
 671             int end = sequenceString[0].length();
 672             for (int i = 0; i < (noseqs - 1); i++)
 673             {
 674                 for (int j = i; j < noseqs; j++)
 675                 {
 676                     int score = 0;
 677
 678                     for (int k = 0; k < end; k++)
 679                     {
 680                         try
 681                         {
 682                             score += ResidueProperties.getBLOSUM62(
 683                               sequenceString[i].substring(k, k + 1),
 684                               sequenceString[j].substring(k, k + 1));
 685                         }
 686                         catch (Exception ex)
 687                         {
 688                             System.err.println("err creating BLOSUM62 tree");
 689                             ex.printStackTrace();
 690                         }
 691                     }
 692
 693                     distance[i][j] = (float) score;
 694
 695                     if (score > maxscore)
 696                     {
 697                         maxscore = score;
 698                     }
 699                 }
 700             }
 701
 702             for (int i = 0; i < (noseqs - 1); i++)
 703             {
 704                 for (int j = i; j < noseqs; j++)
 705                 {
 706                     distance[i][j] = (float) maxscore - distance[i][j];
 707                     distance[j][i] = distance[i][j];
 708                 }
 709             }
 710         }
 711       /*  else if (pwtype.equals("SW"))
 712         {
 713             float max = -1;
 714
 715             for (int i = 0; i < (noseqs - 1); i++)
 716             {
 717                 for (int j = i; j < noseqs; j++)
 718                 {
 719                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
 720                     as.calcScoreMatrix();
 721                     as.traceAlignment();
 722                     as.printAlignment(System.out);
 723                     distance[i][j] = (float) as.maxscore;
 724
 725                     if (max < distance[i][j])
 726                     {
 727                         max = distance[i][j];
 728                     }
 729                 }
 730             }
 731
 732             for (int i = 0; i < (noseqs - 1); i++)
 733             {
 734                 for (int j = i; j < noseqs; j++)
 735                 {
 736                     distance[i][j] = max - distance[i][j];
 737                     distance[j][i] = distance[i][j];
 738                 }
 739             }
 740         }/*/
 741
 742         return distance;
 743     }
 744
 745     /**
 746      * DOCUMENT ME!
 747      */
 748     public void makeLeaves()
 749     {
 750         cluster = new Vector();
 751
 752         for (int i = 0; i < noseqs; i++)
 753         {
 754             SequenceNode sn = new SequenceNode();
 755
 756             sn.setElement(sequence[i]);
 757             sn.setName(sequence[i].getName());
 758             node.addElement(sn);
 759
 760             int[] value = new int[1];
 761             value[0] = i;
 762
 763             Cluster c = new Cluster(value);
 764             cluster.addElement(c);
 765         }
 766     }
 767
 768     /**
 769      * DOCUMENT ME!
 770      *
 771      * @param node DOCUMENT ME!
 772      * @param leaves DOCUMENT ME!
 773      *
 774      * @return DOCUMENT ME!
 775      */
 776     public Vector findLeaves(SequenceNode node, Vector leaves)
 777     {
 778         if (node == null)
 779         {
 780             return leaves;
 781         }
 782
 783         if ((node.left() == null) && (node.right() == null))
 784         {
 785             leaves.addElement(node);
 786
 787             return leaves;
 788         }
 789         else
 790         {
 791             findLeaves((SequenceNode) node.left(), leaves);
 792             findLeaves((SequenceNode) node.right(), leaves);
 793         }
 794
 795         return leaves;
 796     }
 797
 798     /**
 799      * DOCUMENT ME!
 800      *
 801      * @param node DOCUMENT ME!
 802      * @param count DOCUMENT ME!
 803      *
 804      * @return DOCUMENT ME!
 805      */
 806     public Object findLeaf(SequenceNode node, int count)
 807     {
 808         found = _findLeaf(node, count);
 809
 810         return found;
 811     }
 812
 813     /**
 814      * DOCUMENT ME!
 815      *
 816      * @param node DOCUMENT ME!
 817      * @param count DOCUMENT ME!
 818      *
 819      * @return DOCUMENT ME!
 820      */
 821     public Object _findLeaf(SequenceNode node, int count)
 822     {
 823         if (node == null)
 824         {
 825             return null;
 826         }
 827
 828         if (node.ycount == count)
 829         {
 830             found = node.element();
 831
 832             return found;
 833         }
 834         else
 835         {
 836             _findLeaf((SequenceNode) node.left(), count);
 837             _findLeaf((SequenceNode) node.right(), count);
 838         }
 839
 840         return found;
 841     }
 842
 843     /**
 844      * printNode is mainly for debugging purposes.
 845      *
 846      * @param node SequenceNode
 847      */
 848     public void printNode(SequenceNode node)
 849     {
 850         if (node == null)
 851         {
 852             return;
 853         }
 854
 855         if ((node.left() == null) && (node.right() == null))
 856         {
 857             System.out.println("Leaf = " +
 858                 ((SequenceI) node.element()).getName());
 859             System.out.println("Dist " + ((SequenceNode) node).dist);
 860             System.out.println("Boot " + node.getBootstrap());
 861         }
 862         else
 863         {
 864             System.out.println("Dist " + ((SequenceNode) node).dist);
 865             printNode((SequenceNode) node.left());
 866             printNode((SequenceNode) node.right());
 867         }
 868     }
 869
 870     /**
 871      * DOCUMENT ME!
 872      *
 873      * @param node DOCUMENT ME!
 874      */
 875     public void findMaxDist(SequenceNode node)
 876     {
 877         if (node == null)
 878         {
 879             return;
 880         }
 881
 882         if ((node.left() == null) && (node.right() == null))
 883         {
 884             float dist = ((SequenceNode) node).dist;
 885
 886             if (dist > maxDistValue)
 887             {
 888                 maxdist = (SequenceNode) node;
 889                 maxDistValue = dist;
 890             }
 891         }
 892         else
 893         {
 894             findMaxDist((SequenceNode) node.left());
 895             findMaxDist((SequenceNode) node.right());
 896         }
 897     }
 898
 899     /**
 900      * DOCUMENT ME!
 901      *
 902      * @return DOCUMENT ME!
 903      */
 904     public Vector getGroups()
 905     {
 906         return groups;
 907     }
 908
 909     /**
 910      * DOCUMENT ME!
 911      *
 912      * @return DOCUMENT ME!
 913      */
 914     public float getMaxHeight()
 915     {
 916         return maxheight;
 917     }
 918
 919     /**
 920      * DOCUMENT ME!
 921      *
 922      * @param node DOCUMENT ME!
 923      * @param threshold DOCUMENT ME!
 924      */
 925     public void groupNodes(SequenceNode node, float threshold)
 926     {
 927         if (node == null)
 928         {
 929             return;
 930         }
 931
 932         if ((node.height / maxheight) > threshold)
 933         {
 934             groups.addElement(node);
 935         }
 936         else
 937         {
 938             groupNodes((SequenceNode) node.left(), threshold);
 939             groupNodes((SequenceNode) node.right(), threshold);
 940         }
 941     }
 942
 943     /**
 944      * DOCUMENT ME!
 945      *
 946      * @param node DOCUMENT ME!
 947      *
 948      * @return DOCUMENT ME!
 949      */
 950     public float findHeight(SequenceNode node)
 951     {
 952         if (node == null)
 953         {
 954             return maxheight;
 955         }
 956
 957         if ((node.left() == null) && (node.right() == null))
 958         {
 959             node.height = ((SequenceNode) node.parent()).height + node.dist;
 960
 961             if (node.height > maxheight)
 962             {
 963                 return node.height;
 964             }
 965             else
 966             {
 967                 return maxheight;
 968             }
 969         }
 970         else
 971         {
 972             if (node.parent() != null)
 973             {
 974                 node.height = ((SequenceNode) node.parent()).height +
 975                     node.dist;
 976             }
 977             else
 978             {
 979                 maxheight = 0;
 980                 node.height = (float) 0.0;
 981             }
 982
 983             maxheight = findHeight((SequenceNode) (node.left()));
 984             maxheight = findHeight((SequenceNode) (node.right()));
 985         }
 986
 987         return maxheight;
 988     }
 989
 990     /**
 991      * DOCUMENT ME!
 992      *
 993      * @return DOCUMENT ME!
 994      */
 995     public SequenceNode reRoot()
 996     {
 997         if (maxdist != null)
 998         {
 999             ycount = 0;
1000
1001             float tmpdist = maxdist.dist;
1002
1003             // New top
1004             SequenceNode sn = new SequenceNode();
1005             sn.setParent(null);
1006
1007             // New right hand of top
1008             SequenceNode snr = (SequenceNode) maxdist.parent();
1009             changeDirection(snr, maxdist);
1010             System.out.println("Printing reversed tree");
1011             printN(snr);
1012             snr.dist = tmpdist / 2;
1013             maxdist.dist = tmpdist / 2;
1014
1015             snr.setParent(sn);
1016             maxdist.setParent(sn);
1017
1018             sn.setRight(snr);
1019             sn.setLeft(maxdist);
1020
1021             top = sn;
1022
1023             ycount = 0;
1024             reCount(top);
1025             findHeight(top);
1026         }
1027
1028         return top;
1029     }
1030     /**
1031      *
1032      * @return true if original sequence data can be recovered
1033      */
1034     public boolean hasOriginalSequenceData() {
1035       return seqData!=null;
1036     }
1037     /**
1038      * Returns original alignment data used for calculation - or null where
1039      * not available.
1040      *
1041      * @return null or cut'n'pasteable alignment
1042      */
1043     public String printOriginalSequenceData(char gapChar)
1044     {
1045       if (seqData==null)
1046         return null;
1047
1048       StringBuffer sb = new StringBuffer();
1049       String[] seqdatas = seqData.getSequenceStrings(gapChar);
1050       for(int i=0; i<seqdatas.length; i++)
1051       {
1052         sb.append(new jalview.util.Format("%-" + 15 + "s").form(
1053             sequence[i].getName()));
1054         sb.append(" "+seqdatas[i]+"\n");
1055       }
1056       return sb.toString();
1057     }
1058     /**
1059      * DOCUMENT ME!
1060      *
1061      * @param node DOCUMENT ME!
1062      */
1063     public void printN(SequenceNode node)
1064     {
1065         if (node == null)
1066         {
1067             return;
1068         }
1069
1070         if ((node.left() != null) && (node.right() != null))
1071         {
1072             printN((SequenceNode) node.left());
1073             printN((SequenceNode) node.right());
1074         }
1075         else
1076         {
1077             System.out.println(" name = " +
1078                 ((SequenceI) node.element()).getName());
1079         }
1080
1081         System.out.println(" dist = " + ((SequenceNode) node).dist + " " +
1082             ((SequenceNode) node).count + " " + ((SequenceNode) node).height);
1083     }
1084
1085     /**
1086      * DOCUMENT ME!
1087      *
1088      * @param node DOCUMENT ME!
1089      */
1090     public void reCount(SequenceNode node)
1091     {
1092         ycount = 0;
1093         _reCount(node);
1094     }
1095
1096     /**
1097      * DOCUMENT ME!
1098      *
1099      * @param node DOCUMENT ME!
1100      */
1101     public void _reCount(SequenceNode node)
1102     {
1103         if (node == null)
1104         {
1105             return;
1106         }
1107
1108         if ((node.left() != null) && (node.right() != null))
1109         {
1110             _reCount((SequenceNode) node.left());
1111             _reCount((SequenceNode) node.right());
1112
1113             SequenceNode l = (SequenceNode) node.left();
1114             SequenceNode r = (SequenceNode) node.right();
1115
1116             ((SequenceNode) node).count = l.count + r.count;
1117             ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1118         }
1119         else
1120         {
1121             ((SequenceNode) node).count = 1;
1122             ((SequenceNode) node).ycount = ycount++;
1123         }
1124     }
1125
1126     /**
1127      * DOCUMENT ME!
1128      *
1129      * @param node DOCUMENT ME!
1130      */
1131     public void swapNodes(SequenceNode node)
1132     {
1133         if (node == null)
1134         {
1135             return;
1136         }
1137
1138         SequenceNode tmp = (SequenceNode) node.left();
1139
1140         node.setLeft(node.right());
1141         node.setRight(tmp);
1142     }
1143
1144     /**
1145      * DOCUMENT ME!
1146      *
1147      * @param node DOCUMENT ME!
1148      * @param dir DOCUMENT ME!
1149      */
1150     public void changeDirection(SequenceNode node, SequenceNode dir)
1151     {
1152         if (node == null)
1153         {
1154             return;
1155         }
1156
1157         if (node.parent() != top)
1158         {
1159             changeDirection((SequenceNode) node.parent(), node);
1160
1161             SequenceNode tmp = (SequenceNode) node.parent();
1162
1163             if (dir == node.left())
1164             {
1165                 node.setParent(dir);
1166                 node.setLeft(tmp);
1167             }
1168             else if (dir == node.right())
1169             {
1170                 node.setParent(dir);
1171                 node.setRight(tmp);
1172             }
1173         }
1174         else
1175         {
1176             if (dir == node.left())
1177             {
1178                 node.setParent(node.left());
1179
1180                 if (top.left() == node)
1181                 {
1182                     node.setRight(top.right());
1183                 }
1184                 else
1185                 {
1186                     node.setRight(top.left());
1187                 }
1188             }
1189             else
1190             {
1191                 node.setParent(node.right());
1192
1193                 if (top.left() == node)
1194                 {
1195                     node.setLeft(top.right());
1196                 }
1197                 else
1198                 {
1199                     node.setLeft(top.left());
1200                 }
1201             }
1202         }
1203     }
1204
1205
1206     /**
1207      * DOCUMENT ME!
1208      *
1209      * @return DOCUMENT ME!
1210      */
1211     public SequenceNode getMaxDist()
1212     {
1213         return maxdist;
1214     }
1215
1216     /**
1217      * DOCUMENT ME!
1218      *
1219      * @return DOCUMENT ME!
1220      */
1221     public SequenceNode getTopNode()
1222     {
1223         return top;
1224     }
1225     /**
1226      *
1227      * @return true if tree has real distances
1228      */
1229     public boolean isHasDistances() {
1230       return hasDistances;
1231     }
1232
1233     /**
1234      *
1235      * @return true if tree has real bootstrap values
1236      */
1237     public boolean isHasBootstrap() {
1238       return hasBootstrap;
1239     }
1240
1241   public boolean isHasRootDistance()
1242   {
1243     return hasRootDistance;
1244   }
1245
1246 }
1247
1248
1249 /**
1250  * DOCUMENT ME!
1251  *
1252  * @author $author$
1253  * @version $Revision$
1254  */
1255 class Cluster
1256 {
1257     int[] value;
1258
1259     /**
1260      * Creates a new Cluster object.
1261      *
1262      * @param value DOCUMENT ME!
1263      */
1264     public Cluster(int[] value)
1265     {
1266         this.value = value;
1267     }
1268 }
1269