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