src/jalview/analysis/NJTree.java

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