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