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