src/jalview/analysis/NJTree.java

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