src/jalview/analysis/NJTree.java

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