src/jalview/analysis/NJTree.java

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