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