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    * DOCUMENT ME!
 790    *
 791    * @param node DOCUMENT ME!
 792    * @param leaves DOCUMENT ME!
 793    *
 794    * @return DOCUMENT ME!
 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    * DOCUMENT ME!
 820    *
 821    * @param node DOCUMENT ME!
 822    * @param count DOCUMENT ME!
 823    *
 824    * @return DOCUMENT ME!
 825    */
 826   public Object findLeaf(SequenceNode node, int count)
 827   {
 828     found = _findLeaf(node, count);
 829
 830     return found;
 831   }
 832
 833   /**
 834    * DOCUMENT ME!
 835    *
 836    * @param node DOCUMENT ME!
 837    * @param count DOCUMENT ME!
 838    *
 839    * @return DOCUMENT ME!
 840    */
 841   public Object _findLeaf(SequenceNode node, int count)
 842   {
 843     if (node == null)
 844     {
 845       return null;
 846     }
 847
 848     if (node.ycount == count)
 849     {
 850       found = node.element();
 851
 852       return found;
 853     }
 854     else
 855     {
 856       _findLeaf( (SequenceNode) node.left(), count);
 857       _findLeaf( (SequenceNode) node.right(), count);
 858     }
 859
 860     return found;
 861   }
 862
 863   /**
 864    * printNode is mainly for debugging purposes.
 865    *
 866    * @param node SequenceNode
 867    */
 868   public void printNode(SequenceNode node)
 869   {
 870     if (node == null)
 871     {
 872       return;
 873     }
 874
 875     if ( (node.left() == null) && (node.right() == null))
 876     {
 877       System.out.println("Leaf = " +
 878                          ( (SequenceI) node.element()).getName());
 879       System.out.println("Dist " + ( (SequenceNode) node).dist);
 880       System.out.println("Boot " + node.getBootstrap());
 881     }
 882     else
 883     {
 884       System.out.println("Dist " + ( (SequenceNode) node).dist);
 885       printNode( (SequenceNode) node.left());
 886       printNode( (SequenceNode) node.right());
 887     }
 888   }
 889
 890   /**
 891    * DOCUMENT ME!
 892    *
 893    * @param node DOCUMENT ME!
 894    */
 895   public void findMaxDist(SequenceNode node)
 896   {
 897     if (node == null)
 898     {
 899       return;
 900     }
 901
 902     if ( (node.left() == null) && (node.right() == null))
 903     {
 904       float dist = ( (SequenceNode) node).dist;
 905
 906       if (dist > maxDistValue)
 907       {
 908         maxdist = (SequenceNode) node;
 909         maxDistValue = dist;
 910       }
 911     }
 912     else
 913     {
 914       findMaxDist( (SequenceNode) node.left());
 915       findMaxDist( (SequenceNode) node.right());
 916     }
 917   }
 918
 919   /**
 920    * DOCUMENT ME!
 921    *
 922    * @return DOCUMENT ME!
 923    */
 924   public Vector getGroups()
 925   {
 926     return groups;
 927   }
 928
 929   /**
 930    * DOCUMENT ME!
 931    *
 932    * @return DOCUMENT ME!
 933    */
 934   public float getMaxHeight()
 935   {
 936     return maxheight;
 937   }
 938
 939   /**
 940    * DOCUMENT ME!
 941    *
 942    * @param node DOCUMENT ME!
 943    * @param threshold DOCUMENT ME!
 944    */
 945   public void groupNodes(SequenceNode node, float threshold)
 946   {
 947     if (node == null)
 948     {
 949       return;
 950     }
 951
 952     if ( (node.height / maxheight) > threshold)
 953     {
 954       groups.addElement(node);
 955     }
 956     else
 957     {
 958       groupNodes( (SequenceNode) node.left(), threshold);
 959       groupNodes( (SequenceNode) node.right(), threshold);
 960     }
 961   }
 962
 963   /**
 964    * DOCUMENT ME!
 965    *
 966    * @param node DOCUMENT ME!
 967    *
 968    * @return DOCUMENT ME!
 969    */
 970   public float findHeight(SequenceNode node)
 971   {
 972     if (node == null)
 973     {
 974       return maxheight;
 975     }
 976
 977     if ( (node.left() == null) && (node.right() == null))
 978     {
 979       node.height = ( (SequenceNode) node.parent()).height + node.dist;
 980
 981       if (node.height > maxheight)
 982       {
 983         return node.height;
 984       }
 985       else
 986       {
 987         return maxheight;
 988       }
 989     }
 990     else
 991     {
 992       if (node.parent() != null)
 993       {
 994         node.height = ( (SequenceNode) node.parent()).height +
 995             node.dist;
 996       }
 997       else
 998       {
 999         maxheight = 0;
1000         node.height = (float) 0.0;
1001       }
1002
1003       maxheight = findHeight( (SequenceNode) (node.left()));
1004       maxheight = findHeight( (SequenceNode) (node.right()));
1005     }
1006
1007     return maxheight;
1008   }
1009
1010   /**
1011    * DOCUMENT ME!
1012    *
1013    * @return DOCUMENT ME!
1014    */
1015   public SequenceNode reRoot()
1016   {
1017     if (maxdist != null)
1018     {
1019       ycount = 0;
1020
1021       float tmpdist = maxdist.dist;
1022
1023       // New top
1024       SequenceNode sn = new SequenceNode();
1025       sn.setParent(null);
1026
1027       // New right hand of top
1028       SequenceNode snr = (SequenceNode) maxdist.parent();
1029       changeDirection(snr, maxdist);
1030       System.out.println("Printing reversed tree");
1031       printN(snr);
1032       snr.dist = tmpdist / 2;
1033       maxdist.dist = tmpdist / 2;
1034
1035       snr.setParent(sn);
1036       maxdist.setParent(sn);
1037
1038       sn.setRight(snr);
1039       sn.setLeft(maxdist);
1040
1041       top = sn;
1042
1043       ycount = 0;
1044       reCount(top);
1045       findHeight(top);
1046     }
1047
1048     return top;
1049   }
1050
1051   /**
1052    *
1053    * @return true if original sequence data can be recovered
1054    */
1055   public boolean hasOriginalSequenceData()
1056   {
1057     return seqData != null;
1058   }
1059
1060   /**
1061    * Returns original alignment data used for calculation - or null where
1062    * not available.
1063    *
1064    * @return null or cut'n'pasteable alignment
1065    */
1066   public String printOriginalSequenceData(char gapChar)
1067   {
1068     if (seqData == null)
1069     {
1070       return null;
1071     }
1072
1073     StringBuffer sb = new StringBuffer();
1074     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1075     for (int i = 0; i < seqdatas.length; i++)
1076     {
1077       sb.append(new jalview.util.Format("%-" + 15 + "s").form(
1078           sequence[i].getName()));
1079       sb.append(" " + seqdatas[i] + "\n");
1080     }
1081     return sb.toString();
1082   }
1083
1084   /**
1085    * DOCUMENT ME!
1086    *
1087    * @param node DOCUMENT ME!
1088    */
1089   public void printN(SequenceNode node)
1090   {
1091     if (node == null)
1092     {
1093       return;
1094     }
1095
1096     if ( (node.left() != null) && (node.right() != null))
1097     {
1098       printN( (SequenceNode) node.left());
1099       printN( (SequenceNode) node.right());
1100     }
1101     else
1102     {
1103       System.out.println(" name = " +
1104                          ( (SequenceI) node.element()).getName());
1105     }
1106
1107     System.out.println(" dist = " + ( (SequenceNode) node).dist + " " +
1108                        ( (SequenceNode) node).count + " " +
1109                        ( (SequenceNode) node).height);
1110   }
1111
1112   /**
1113    * DOCUMENT ME!
1114    *
1115    * @param node DOCUMENT ME!
1116    */
1117   public void reCount(SequenceNode node)
1118   {
1119     ycount = 0;
1120     _reCount(node);
1121   }
1122
1123   /**
1124    * DOCUMENT ME!
1125    *
1126    * @param node DOCUMENT ME!
1127    */
1128   public void _reCount(SequenceNode node)
1129   {
1130     if (node == null)
1131     {
1132       return;
1133     }
1134
1135     if ( (node.left() != null) && (node.right() != null))
1136     {
1137       _reCount( (SequenceNode) node.left());
1138       _reCount( (SequenceNode) node.right());
1139
1140       SequenceNode l = (SequenceNode) node.left();
1141       SequenceNode r = (SequenceNode) node.right();
1142
1143       ( (SequenceNode) node).count = l.count + r.count;
1144       ( (SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1145     }
1146     else
1147     {
1148       ( (SequenceNode) node).count = 1;
1149       ( (SequenceNode) node).ycount = ycount++;
1150     }
1151   }
1152
1153   /**
1154    * DOCUMENT ME!
1155    *
1156    * @param node DOCUMENT ME!
1157    */
1158   public void swapNodes(SequenceNode node)
1159   {
1160     if (node == null)
1161     {
1162       return;
1163     }
1164
1165     SequenceNode tmp = (SequenceNode) node.left();
1166
1167     node.setLeft(node.right());
1168     node.setRight(tmp);
1169   }
1170
1171   /**
1172    * DOCUMENT ME!
1173    *
1174    * @param node DOCUMENT ME!
1175    * @param dir DOCUMENT ME!
1176    */
1177   public void changeDirection(SequenceNode node, SequenceNode dir)
1178   {
1179     if (node == null)
1180     {
1181       return;
1182     }
1183
1184     if (node.parent() != top)
1185     {
1186       changeDirection( (SequenceNode) node.parent(), node);
1187
1188       SequenceNode tmp = (SequenceNode) node.parent();
1189
1190       if (dir == node.left())
1191       {
1192         node.setParent(dir);
1193         node.setLeft(tmp);
1194       }
1195       else if (dir == node.right())
1196       {
1197         node.setParent(dir);
1198         node.setRight(tmp);
1199       }
1200     }
1201     else
1202     {
1203       if (dir == node.left())
1204       {
1205         node.setParent(node.left());
1206
1207         if (top.left() == node)
1208         {
1209           node.setRight(top.right());
1210         }
1211         else
1212         {
1213           node.setRight(top.left());
1214         }
1215       }
1216       else
1217       {
1218         node.setParent(node.right());
1219
1220         if (top.left() == node)
1221         {
1222           node.setLeft(top.right());
1223         }
1224         else
1225         {
1226           node.setLeft(top.left());
1227         }
1228       }
1229     }
1230   }
1231
1232   /**
1233    * DOCUMENT ME!
1234    *
1235    * @return DOCUMENT ME!
1236    */
1237   public SequenceNode getMaxDist()
1238   {
1239     return maxdist;
1240   }
1241
1242   /**
1243    * DOCUMENT ME!
1244    *
1245    * @return DOCUMENT ME!
1246    */
1247   public SequenceNode getTopNode()
1248   {
1249     return top;
1250   }
1251
1252   /**
1253    *
1254    * @return true if tree has real distances
1255    */
1256   public boolean isHasDistances()
1257   {
1258     return hasDistances;
1259   }
1260
1261   /**
1262    *
1263    * @return true if tree has real bootstrap values
1264    */
1265   public boolean isHasBootstrap()
1266   {
1267     return hasBootstrap;
1268   }
1269
1270   public boolean isHasRootDistance()
1271   {
1272     return hasRootDistance;
1273   }
1274
1275 }
1276
1277 /**
1278  * DOCUMENT ME!
1279  *
1280  * @author $author$
1281  * @version $Revision$
1282  */
1283 class Cluster
1284 {
1285   int[] value;
1286
1287   /**
1288    * Creates a new Cluster object.
1289    *
1290    * @param value DOCUMENT ME!
1291    */
1292   public Cluster(int[] value)
1293   {
1294     this.value = value;
1295   }
1296 }