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