src/jalview/analysis/NJTree.java

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