src/jalview/analysis/NJTree.java

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