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