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