src/jalview/analysis/NJTree.java

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