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.api.analysis.ScoreModelI;
  24 import jalview.datamodel.AlignmentView;
  25 import jalview.datamodel.BinaryNode;
  26 import jalview.datamodel.CigarArray;
  27 import jalview.datamodel.NodeTransformI;
  28 import jalview.datamodel.SeqCigar;
  29 import jalview.datamodel.Sequence;
  30 import jalview.datamodel.SequenceI;
  31 import jalview.datamodel.SequenceNode;
  32 import jalview.io.NewickFile;
  33 import jalview.schemes.ResidueProperties;
  34 import jalview.util.Format;
  35
  36 import java.util.Enumeration;
  37 import java.util.List;
  38 import java.util.Vector;
  39
  40 /**
  41  * NeighborJoining tree
  42  *
  43  * @author $author$
  44  * @version $Revision$
  45  */
  46 public class NJTree
  47 {
  48   Vector cluster;
  49
  50   SequenceI[] sequence;
  51
  52   // SequenceData is a string representation of what the user
  53   // sees. The display may contain hidden columns.
  54   public AlignmentView seqData = null;
  55
  56   int[] done;
  57
  58   int noseqs;
  59
  60   int noClus;
  61
  62   float[][] distance;
  63
  64   int mini;
  65
  66   int minj;
  67
  68   float ri;
  69
  70   float rj;
  71
  72   Vector groups = new Vector();
  73
  74   SequenceNode maxdist;
  75
  76   SequenceNode top;
  77
  78   float maxDistValue;
  79
  80   float maxheight;
  81
  82   int ycount;
  83
  84   Vector node;
  85
  86   String type;
  87
  88   String pwtype;
  89
  90   Object found = null;
  91
  92   Object leaves = null;
  93
  94   boolean hasDistances = true; // normal case for jalview trees
  95
  96   boolean hasBootstrap = false; // normal case for jalview trees
  97
  98   private boolean hasRootDistance = true;
  99
 100   /**
 101    * Create a new NJTree object with leaves associated with sequences in seqs,
 102    * and original alignment data represented by Cigar strings.
 103    *
 104    * @param seqs
 105    *          SequenceI[]
 106    * @param odata
 107    *          Cigar[]
 108    * @param treefile
 109    *          NewickFile
 110    */
 111   public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
 112   {
 113     this(seqs, treefile);
 114     if (odata != null)
 115     {
 116       seqData = odata;
 117     }
 118     /*
 119      * sequenceString = new String[odata.length]; char gapChar =
 120      * Comparison.GapChars.charAt(0); for (int i = 0; i <
 121      * odata.length; i++) { SequenceI oseq_aligned = odata[i].getSeq(gapChar);
 122      * sequenceString[i] = oseq_aligned.getSequence(); }
 123      */
 124   }
 125
 126   /**
 127    * Creates a new NJTree object from a tree from an external source
 128    *
 129    * @param seqs
 130    *          SequenceI which should be associated with leafs of treefile
 131    * @param treefile
 132    *          A parsed tree
 133    */
 134   public NJTree(SequenceI[] seqs, NewickFile treefile)
 135   {
 136     this.sequence = seqs;
 137     top = treefile.getTree();
 138
 139     /**
 140      * There is no dependent alignment to be recovered from an imported tree.
 141      *
 142      * if (sequenceString == null) { sequenceString = new String[seqs.length];
 143      * for (int i = 0; i < seqs.length; i++) { sequenceString[i] =
 144      * seqs[i].getSequence(); } }
 145      */
 146
 147     hasDistances = treefile.HasDistances();
 148     hasBootstrap = treefile.HasBootstrap();
 149     hasRootDistance = treefile.HasRootDistance();
 150
 151     maxheight = findHeight(top);
 152
 153     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
 154
 155     Vector leaves = new Vector();
 156     findLeaves(top, leaves);
 157
 158     int i = 0;
 159     int namesleft = seqs.length;
 160
 161     SequenceNode j;
 162     SequenceI nam;
 163     String realnam;
 164     Vector one2many = new Vector();
 165     int countOne2Many = 0;
 166     while (i < leaves.size())
 167     {
 168       j = (SequenceNode) 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 (Cache.log.isDebugEnabled())
 184           // 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 (Cache.log.isDebugEnabled() && countOne2Many>0) {
 200     // 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();
 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("NJ")))
 245     {
 246       type = "AV";
 247     }
 248
 249     if (sm == null && !(pwtype.equals("PID")))
 250     {
 251       if (ResidueProperties.getScoreMatrix(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   public String toString()
 287   {
 288     NewickFile fout = new NewickFile(getTopNode());
 289
 290     return fout.print(isHasBootstrap(), isHasDistances(),
 291             isHasRootDistance()); // output all data available for tree
 292   }
 293
 294   /**
 295    *
 296    * used when the alignment associated to a tree has changed.
 297    *
 298    * @param list
 299    *          Sequence set to be associated with tree nodes
 300    */
 301   public void UpdatePlaceHolders(List<SequenceI> list)
 302   {
 303     Vector leaves = new Vector();
 304     findLeaves(top, leaves);
 305
 306     int sz = leaves.size();
 307     SequenceIdMatcher seqmatcher = null;
 308     int i = 0;
 309
 310     while (i < sz)
 311     {
 312       SequenceNode leaf = (SequenceNode) 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 node)
 374       {
 375         Object el = node.element();
 376         if (el != null && el instanceof SequenceI)
 377         {
 378           node.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("NJ"))
 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 = (SequenceNode) (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) cluster.elementAt(i)).value.length;
 454     int noj = ((Cluster) 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) cluster.elementAt(i)).value[ii];
 461     }
 462
 463     for (int ii = noi; ii < (noi + noj); ii++)
 464     {
 465       value[ii] = ((Cluster) 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("NJ"))
 474     {
 475       findClusterNJDistance(i, j);
 476     }
 477     else
 478     {
 479       findClusterDistance(i, j);
 480     }
 481
 482     SequenceNode sn = new SequenceNode();
 483
 484     sn.setLeft((SequenceNode) (node.elementAt(i)));
 485     sn.setRight((SequenceNode) (node.elementAt(j)));
 486
 487     SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
 488     SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
 489
 490     if (type.equals("NJ"))
 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) cluster.elementAt(i)).value.length;
 581     int noj = ((Cluster) 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[][] distance = new float[noseqs][noseqs];
 738     if (_pwmatrix == null)
 739     {
 740       // Resolve substitution model
 741       _pwmatrix = ResidueProperties.getScoreModel(pwtype);
 742       if (_pwmatrix == null)
 743       {
 744         _pwmatrix = ResidueProperties.getScoreMatrix("BLOSUM62");
 745       }
 746     }
 747     distance = _pwmatrix.findDistances(seqData);
 748     return distance;
 749
 750   }
 751
 752   /**
 753    * DOCUMENT ME!
 754    */
 755   public void makeLeaves()
 756   {
 757     cluster = new Vector();
 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.
 777    *
 778    * @param node
 779    *          root node to search from
 780    * @param leaves
 781    *          Vector of leaves to add leaf node objects too.
 782    *
 783    * @return Vector of leaf nodes on binary tree
 784    */
 785   public Vector findLeaves(SequenceNode node, Vector leaves)
 786   {
 787     if (node == null)
 788     {
 789       return leaves;
 790     }
 791
 792     if ((node.left() == null) && (node.right() == null)) // Interior node
 793     // detection
 794     {
 795       leaves.addElement(node);
 796
 797       return leaves;
 798     }
 799     else
 800     {
 801       /*
 802        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
 803        * leaves.addElement(node); }
 804        */
 805       findLeaves((SequenceNode) node.left(), leaves);
 806       findLeaves((SequenceNode) node.right(), leaves);
 807     }
 808
 809     return leaves;
 810   }
 811
 812   /**
 813    * Find the leaf node with a particular ycount
 814    *
 815    * @param node
 816    *          initial point on tree to search from
 817    * @param count
 818    *          value to search for
 819    *
 820    * @return null or the node with ycound=count
 821    */
 822   public Object findLeaf(SequenceNode node, int count)
 823   {
 824     found = _findLeaf(node, count);
 825
 826     return found;
 827   }
 828
 829   /*
 830    * #see findLeaf(SequenceNode node, count)
 831    */
 832   public Object _findLeaf(SequenceNode node, int count)
 833   {
 834     if (node == null)
 835     {
 836       return null;
 837     }
 838
 839     if (node.ycount == count)
 840     {
 841       found = node.element();
 842
 843       return found;
 844     }
 845     else
 846     {
 847       _findLeaf((SequenceNode) node.left(), count);
 848       _findLeaf((SequenceNode) node.right(), count);
 849     }
 850
 851     return found;
 852   }
 853
 854   /**
 855    * printNode is mainly for debugging purposes.
 856    *
 857    * @param node
 858    *          SequenceNode
 859    */
 860   public void printNode(SequenceNode node)
 861   {
 862     if (node == null)
 863     {
 864       return;
 865     }
 866
 867     if ((node.left() == null) && (node.right() == null))
 868     {
 869       System.out
 870               .println("Leaf = " + ((SequenceI) node.element()).getName());
 871       System.out.println("Dist " + node.dist);
 872       System.out.println("Boot " + node.getBootstrap());
 873     }
 874     else
 875     {
 876       System.out.println("Dist " + node.dist);
 877       printNode((SequenceNode) node.left());
 878       printNode((SequenceNode) node.right());
 879     }
 880   }
 881
 882   /**
 883    * DOCUMENT ME!
 884    *
 885    * @param node
 886    *          DOCUMENT ME!
 887    */
 888   public void findMaxDist(SequenceNode node)
 889   {
 890     if (node == null)
 891     {
 892       return;
 893     }
 894
 895     if ((node.left() == null) && (node.right() == null))
 896     {
 897       float dist = node.dist;
 898
 899       if (dist > maxDistValue)
 900       {
 901         maxdist = node;
 902         maxDistValue = dist;
 903       }
 904     }
 905     else
 906     {
 907       findMaxDist((SequenceNode) node.left());
 908       findMaxDist((SequenceNode) node.right());
 909     }
 910   }
 911
 912   /**
 913    * DOCUMENT ME!
 914    *
 915    * @return DOCUMENT ME!
 916    */
 917   public Vector getGroups()
 918   {
 919     return groups;
 920   }
 921
 922   /**
 923    * DOCUMENT ME!
 924    *
 925    * @return DOCUMENT ME!
 926    */
 927   public float getMaxHeight()
 928   {
 929     return maxheight;
 930   }
 931
 932   /**
 933    * DOCUMENT ME!
 934    *
 935    * @param node
 936    *          DOCUMENT ME!
 937    * @param threshold
 938    *          DOCUMENT ME!
 939    */
 940   public void groupNodes(SequenceNode node, float threshold)
 941   {
 942     if (node == null)
 943     {
 944       return;
 945     }
 946
 947     if ((node.height / maxheight) > threshold)
 948     {
 949       groups.addElement(node);
 950     }
 951     else
 952     {
 953       groupNodes((SequenceNode) node.left(), threshold);
 954       groupNodes((SequenceNode) node.right(), threshold);
 955     }
 956   }
 957
 958   /**
 959    * DOCUMENT ME!
 960    *
 961    * @param node
 962    *          DOCUMENT ME!
 963    *
 964    * @return DOCUMENT ME!
 965    */
 966   public float findHeight(SequenceNode node)
 967   {
 968     if (node == null)
 969     {
 970       return maxheight;
 971     }
 972
 973     if ((node.left() == null) && (node.right() == null))
 974     {
 975       node.height = ((SequenceNode) node.parent()).height + node.dist;
 976
 977       if (node.height > maxheight)
 978       {
 979         return node.height;
 980       }
 981       else
 982       {
 983         return maxheight;
 984       }
 985     }
 986     else
 987     {
 988       if (node.parent() != null)
 989       {
 990         node.height = ((SequenceNode) node.parent()).height + node.dist;
 991       }
 992       else
 993       {
 994         maxheight = 0;
 995         node.height = (float) 0.0;
 996       }
 997
 998       maxheight = findHeight((SequenceNode) (node.left()));
 999       maxheight = findHeight((SequenceNode) (node.right()));
1000     }
1001
1002     return maxheight;
1003   }
1004
1005   /**
1006    * DOCUMENT ME!
1007    *
1008    * @return DOCUMENT ME!
1009    */
1010   public SequenceNode reRoot()
1011   {
1012     if (maxdist != null)
1013     {
1014       ycount = 0;
1015
1016       float tmpdist = maxdist.dist;
1017
1018       // New top
1019       SequenceNode sn = new SequenceNode();
1020       sn.setParent(null);
1021
1022       // New right hand of top
1023       SequenceNode snr = (SequenceNode) maxdist.parent();
1024       changeDirection(snr, maxdist);
1025       System.out.println("Printing reversed tree");
1026       printN(snr);
1027       snr.dist = tmpdist / 2;
1028       maxdist.dist = tmpdist / 2;
1029
1030       snr.setParent(sn);
1031       maxdist.setParent(sn);
1032
1033       sn.setRight(snr);
1034       sn.setLeft(maxdist);
1035
1036       top = sn;
1037
1038       ycount = 0;
1039       reCount(top);
1040       findHeight(top);
1041     }
1042
1043     return top;
1044   }
1045
1046   /**
1047    *
1048    * @return true if original sequence data can be recovered
1049    */
1050   public boolean hasOriginalSequenceData()
1051   {
1052     return seqData != null;
1053   }
1054
1055   /**
1056    * Returns original alignment data used for calculation - or null where not
1057    * available.
1058    *
1059    * @return null or cut'n'pasteable alignment
1060    */
1061   public String printOriginalSequenceData(char gapChar)
1062   {
1063     if (seqData == null)
1064     {
1065       return null;
1066     }
1067
1068     StringBuffer sb = new StringBuffer();
1069     String[] seqdatas = seqData.getSequenceStrings(gapChar);
1070     for (int i = 0; i < seqdatas.length; i++)
1071     {
1072       sb.append(new Format("%-" + 15 + "s").form(sequence[i].getName()));
1073       sb.append(" " + seqdatas[i] + "\n");
1074     }
1075     return sb.toString();
1076   }
1077
1078   /**
1079    * DOCUMENT ME!
1080    *
1081    * @param node
1082    *          DOCUMENT ME!
1083    */
1084   public void printN(SequenceNode node)
1085   {
1086     if (node == null)
1087     {
1088       return;
1089     }
1090
1091     if ((node.left() != null) && (node.right() != null))
1092     {
1093       printN((SequenceNode) node.left());
1094       printN((SequenceNode) node.right());
1095     }
1096     else
1097     {
1098       System.out.println(" name = "
1099               + ((SequenceI) node.element()).getName());
1100     }
1101
1102     System.out.println(" dist = " + node.dist + " "
1103             + node.count + " "
1104             + node.height);
1105   }
1106
1107   /**
1108    * DOCUMENT ME!
1109    *
1110    * @param node
1111    *          DOCUMENT ME!
1112    */
1113   public void reCount(SequenceNode node)
1114   {
1115     ycount = 0;
1116     _lycount = 0;
1117     // _lylimit = this.node.size();
1118     _reCount(node);
1119   }
1120
1121   private long _lycount = 0, _lylimit = 0;
1122
1123   /**
1124    * DOCUMENT ME!
1125    *
1126    * @param node
1127    *          DOCUMENT ME!
1128    */
1129   public void _reCount(SequenceNode node)
1130   {
1131     // if (_lycount<_lylimit)
1132     // {
1133     // System.err.println("Warning: depth of _recount greater than number of nodes.");
1134     // }
1135     if (node == null)
1136     {
1137       return;
1138     }
1139     _lycount++;
1140
1141     if ((node.left() != null) && (node.right() != null))
1142     {
1143
1144       _reCount((SequenceNode) node.left());
1145       _reCount((SequenceNode) node.right());
1146
1147       SequenceNode l = (SequenceNode) node.left();
1148       SequenceNode r = (SequenceNode) node.right();
1149
1150       node.count = l.count + r.count;
1151       node.ycount = (l.ycount + r.ycount) / 2;
1152     }
1153     else
1154     {
1155       node.count = 1;
1156       node.ycount = ycount++;
1157     }
1158     _lycount--;
1159   }
1160
1161   /**
1162    * DOCUMENT ME!
1163    *
1164    * @param node
1165    *          DOCUMENT ME!
1166    */
1167   public void swapNodes(SequenceNode node)
1168   {
1169     if (node == null)
1170     {
1171       return;
1172     }
1173
1174     SequenceNode tmp = (SequenceNode) node.left();
1175
1176     node.setLeft(node.right());
1177     node.setRight(tmp);
1178   }
1179
1180   /**
1181    * DOCUMENT ME!
1182    *
1183    * @param node
1184    *          DOCUMENT ME!
1185    * @param dir
1186    *          DOCUMENT ME!
1187    */
1188   public void changeDirection(SequenceNode node, SequenceNode dir)
1189   {
1190     if (node == null)
1191     {
1192       return;
1193     }
1194
1195     if (node.parent() != top)
1196     {
1197       changeDirection((SequenceNode) node.parent(), node);
1198
1199       SequenceNode tmp = (SequenceNode) node.parent();
1200
1201       if (dir == node.left())
1202       {
1203         node.setParent(dir);
1204         node.setLeft(tmp);
1205       }
1206       else if (dir == node.right())
1207       {
1208         node.setParent(dir);
1209         node.setRight(tmp);
1210       }
1211     }
1212     else
1213     {
1214       if (dir == node.left())
1215       {
1216         node.setParent(node.left());
1217
1218         if (top.left() == node)
1219         {
1220           node.setRight(top.right());
1221         }
1222         else
1223         {
1224           node.setRight(top.left());
1225         }
1226       }
1227       else
1228       {
1229         node.setParent(node.right());
1230
1231         if (top.left() == node)
1232         {
1233           node.setLeft(top.right());
1234         }
1235         else
1236         {
1237           node.setLeft(top.left());
1238         }
1239       }
1240     }
1241   }
1242
1243   /**
1244    * DOCUMENT ME!
1245    *
1246    * @return DOCUMENT ME!
1247    */
1248   public SequenceNode getMaxDist()
1249   {
1250     return maxdist;
1251   }
1252
1253   /**
1254    * DOCUMENT ME!
1255    *
1256    * @return DOCUMENT ME!
1257    */
1258   public SequenceNode getTopNode()
1259   {
1260     return top;
1261   }
1262
1263   /**
1264    *
1265    * @return true if tree has real distances
1266    */
1267   public boolean isHasDistances()
1268   {
1269     return hasDistances;
1270   }
1271
1272   /**
1273    *
1274    * @return true if tree has real bootstrap values
1275    */
1276   public boolean isHasBootstrap()
1277   {
1278     return hasBootstrap;
1279   }
1280
1281   public boolean isHasRootDistance()
1282   {
1283     return hasRootDistance;
1284   }
1285
1286   /**
1287    * apply the given transform to all the nodes in the tree.
1288    *
1289    * @param nodeTransformI
1290    */
1291   public void applyToNodes(NodeTransformI nodeTransformI)
1292   {
1293     for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
1294             .transform((BinaryNode) nodes.nextElement()))
1295     {
1296       ;
1297     }
1298   }
1299 }
1300
1301 /**
1302  * DOCUMENT ME!
1303  *
1304  * @author $author$
1305  * @version $Revision$
1306  */
1307 class Cluster
1308 {
1309   int[] value;
1310
1311   /**
1312    * Creates a new Cluster object.
1313    *
1314    * @param value
1315    *          DOCUMENT ME!
1316    */
1317   public Cluster(int[] value)
1318   {
1319     this.value = value;
1320   }
1321 }