src/jalview/analysis/NJTree.java

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