src/jalview/analysis/NJTree.java

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