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