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