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                 float mind = findMinNJDistance();\r
 257             }\r
 258             else\r
 259             {\r
 260                 float mind = 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         Cluster c = 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         float ih = 0;\r
 379         float jh = 0;\r
 380 \r
 381         SequenceNode sni = tmpi;\r
 382         SequenceNode snj = tmpj;\r
 383 \r
 384         tmpi.dist = ((dist + ri) - rj) / 2;\r
 385         tmpj.dist = (dist - tmpi.dist);\r
 386 \r
 387         if (tmpi.dist < 0)\r
 388         {\r
 389             tmpi.dist = 0;\r
 390         }\r
 391 \r
 392         if (tmpj.dist < 0)\r
 393         {\r
 394             tmpj.dist = 0;\r
 395         }\r
 396     }\r
 397 \r
 398     /**\r
 399      * DOCUMENT ME!\r
 400      *\r
 401      * @param tmpi DOCUMENT ME!\r
 402      * @param tmpj DOCUMENT ME!\r
 403      * @param dist DOCUMENT ME!\r
 404      */\r
 405     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,\r
 406         float dist)\r
 407     {\r
 408         float ih = 0;\r
 409         float jh = 0;\r
 410 \r
 411         SequenceNode sni = tmpi;\r
 412         SequenceNode snj = tmpj;\r
 413 \r
 414         while (sni != null)\r
 415         {\r
 416             ih = ih + sni.dist;\r
 417             sni = (SequenceNode) sni.left();\r
 418         }\r
 419 \r
 420         while (snj != null)\r
 421         {\r
 422             jh = jh + snj.dist;\r
 423             snj = (SequenceNode) snj.left();\r
 424         }\r
 425 \r
 426         tmpi.dist = ((dist / 2) - ih);\r
 427         tmpj.dist = ((dist / 2) - jh);\r
 428     }\r
 429 \r
 430     /**\r
 431      * DOCUMENT ME!\r
 432      *\r
 433      * @param i DOCUMENT ME!\r
 434      * @param j DOCUMENT ME!\r
 435      */\r
 436     public void findClusterDistance(int i, int j)\r
 437     {\r
 438         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
 439         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
 440 \r
 441         // New distances from cluster to others\r
 442         float[] newdist = new float[noseqs];\r
 443 \r
 444         for (int l = 0; l < noseqs; l++)\r
 445         {\r
 446             if ((l != i) && (l != j))\r
 447             {\r
 448                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +\r
 449                     noj);\r
 450             }\r
 451             else\r
 452             {\r
 453                 newdist[l] = 0;\r
 454             }\r
 455         }\r
 456 \r
 457         for (int ii = 0; ii < noseqs; ii++)\r
 458         {\r
 459             distance[i][ii] = newdist[ii];\r
 460             distance[ii][i] = newdist[ii];\r
 461         }\r
 462     }\r
 463 \r
 464     /**\r
 465      * DOCUMENT ME!\r
 466      *\r
 467      * @param i DOCUMENT ME!\r
 468      * @param j DOCUMENT ME!\r
 469      */\r
 470     public void findClusterNJDistance(int i, int j)\r
 471     {\r
 472         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
 473         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
 474 \r
 475         // New distances from cluster to others\r
 476         float[] newdist = new float[noseqs];\r
 477 \r
 478         for (int l = 0; l < noseqs; l++)\r
 479         {\r
 480             if ((l != i) && (l != j))\r
 481             {\r
 482                 newdist[l] = ((distance[i][l] + distance[j][l]) -\r
 483                     distance[i][j]) / 2;\r
 484             }\r
 485             else\r
 486             {\r
 487                 newdist[l] = 0;\r
 488             }\r
 489         }\r
 490 \r
 491         for (int ii = 0; ii < noseqs; ii++)\r
 492         {\r
 493             distance[i][ii] = newdist[ii];\r
 494             distance[ii][i] = newdist[ii];\r
 495         }\r
 496     }\r
 497 \r
 498     /**\r
 499      * DOCUMENT ME!\r
 500      *\r
 501      * @param i DOCUMENT ME!\r
 502      * @param j DOCUMENT ME!\r
 503      *\r
 504      * @return DOCUMENT ME!\r
 505      */\r
 506     public float findr(int i, int j)\r
 507     {\r
 508         float tmp = 1;\r
 509 \r
 510         for (int k = 0; k < noseqs; k++)\r
 511         {\r
 512             if ((k != i) && (k != j) && (done[k] != 1))\r
 513             {\r
 514                 tmp = tmp + distance[i][k];\r
 515             }\r
 516         }\r
 517 \r
 518         if (noClus > 2)\r
 519         {\r
 520             tmp = tmp / (noClus - 2);\r
 521         }\r
 522 \r
 523         return tmp;\r
 524     }\r
 525 \r
 526     /**\r
 527      * DOCUMENT ME!\r
 528      *\r
 529      * @return DOCUMENT ME!\r
 530      */\r
 531     public float findMinNJDistance()\r
 532     {\r
 533         float min = 100000;\r
 534 \r
 535         for (int i = 0; i < (noseqs - 1); i++)\r
 536         {\r
 537             for (int j = i + 1; j < noseqs; j++)\r
 538             {\r
 539                 if ((done[i] != 1) && (done[j] != 1))\r
 540                 {\r
 541                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));\r
 542 \r
 543                     if (tmp < min)\r
 544                     {\r
 545                         mini = i;\r
 546                         minj = j;\r
 547 \r
 548                         min = tmp;\r
 549                     }\r
 550                 }\r
 551             }\r
 552         }\r
 553 \r
 554         return min;\r
 555     }\r
 556 \r
 557     /**\r
 558      * DOCUMENT ME!\r
 559      *\r
 560      * @return DOCUMENT ME!\r
 561      */\r
 562     public float findMinDistance()\r
 563     {\r
 564         float min = 100000;\r
 565 \r
 566         for (int i = 0; i < (noseqs - 1); i++)\r
 567         {\r
 568             for (int j = i + 1; j < noseqs; j++)\r
 569             {\r
 570                 if ((done[i] != 1) && (done[j] != 1))\r
 571                 {\r
 572                     if (distance[i][j] < min)\r
 573                     {\r
 574                         mini = i;\r
 575                         minj = j;\r
 576 \r
 577                         min = distance[i][j];\r
 578                     }\r
 579                 }\r
 580             }\r
 581         }\r
 582 \r
 583         return min;\r
 584     }\r
 585 \r
 586     /**\r
 587      * DOCUMENT ME!\r
 588      *\r
 589      * @return DOCUMENT ME!\r
 590      */\r
 591     public float[][] findDistances()\r
 592     {\r
 593         float[][] distance = new float[noseqs][noseqs];\r
 594 \r
 595         if (pwtype.equals("PID"))\r
 596         {\r
 597             for (int i = 0; i < (noseqs - 1); i++)\r
 598             {\r
 599                 for (int j = i; j < noseqs; j++)\r
 600                 {\r
 601                     if (j == i)\r
 602                     {\r
 603                         distance[i][i] = 0;\r
 604                     }\r
 605                     else\r
 606                     {\r
 607                         distance[i][j] = 100 -\r
 608                             Comparison.PID(sequence[i], sequence[j], start, end);\r
 609                         distance[j][i] = distance[i][j];\r
 610                     }\r
 611                 }\r
 612             }\r
 613         }\r
 614         else if (pwtype.equals("BL"))\r
 615         {\r
 616             int maxscore = 0;\r
 617 \r
 618             for (int i = 0; i < (noseqs - 1); i++)\r
 619             {\r
 620                 for (int j = i; j < noseqs; j++)\r
 621                 {\r
 622                     int score = 0;\r
 623 \r
 624                     for (int k = start; k < end; k++)\r
 625                     {\r
 626                         try\r
 627                         {\r
 628                             score += ResidueProperties.getBLOSUM62(sequence[i].getSequence(\r
 629                                     k, k + 1), sequence[j].getSequence(k, k +\r
 630                                     1));\r
 631                         }\r
 632                         catch (Exception ex)\r
 633                         {\r
 634                             System.err.println("err creating BLOSUM62 tree");\r
 635                             ex.printStackTrace();\r
 636                         }\r
 637                     }\r
 638 \r
 639                     distance[i][j] = (float) score;\r
 640 \r
 641                     if (score > maxscore)\r
 642                     {\r
 643                         maxscore = score;\r
 644                     }\r
 645                 }\r
 646             }\r
 647 \r
 648             for (int i = 0; i < (noseqs - 1); i++)\r
 649             {\r
 650                 for (int j = i; j < noseqs; j++)\r
 651                 {\r
 652                     distance[i][j] = (float) maxscore - distance[i][j];\r
 653                     distance[j][i] = distance[i][j];\r
 654                 }\r
 655             }\r
 656         }\r
 657         else if (pwtype.equals("SW"))\r
 658         {\r
 659             float max = -1;\r
 660 \r
 661             for (int i = 0; i < (noseqs - 1); i++)\r
 662             {\r
 663                 for (int j = i; j < noseqs; j++)\r
 664                 {\r
 665                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");\r
 666                     as.calcScoreMatrix();\r
 667                     as.traceAlignment();\r
 668                     as.printAlignment();\r
 669                     distance[i][j] = (float) as.maxscore;\r
 670 \r
 671                     if (max < distance[i][j])\r
 672                     {\r
 673                         max = distance[i][j];\r
 674                     }\r
 675                 }\r
 676             }\r
 677 \r
 678             for (int i = 0; i < (noseqs - 1); i++)\r
 679             {\r
 680                 for (int j = i; j < noseqs; j++)\r
 681                 {\r
 682                     distance[i][j] = max - distance[i][j];\r
 683                     distance[j][i] = distance[i][j];\r
 684                 }\r
 685             }\r
 686         }\r
 687 \r
 688         return distance;\r
 689     }\r
 690 \r
 691     /**\r
 692      * DOCUMENT ME!\r
 693      */\r
 694     public void makeLeaves()\r
 695     {\r
 696         cluster = new Vector();\r
 697 \r
 698         for (int i = 0; i < noseqs; i++)\r
 699         {\r
 700             SequenceNode sn = new SequenceNode();\r
 701 \r
 702             sn.setElement(sequence[i]);\r
 703             sn.setName(sequence[i].getName());\r
 704             node.addElement(sn);\r
 705 \r
 706             int[] value = new int[1];\r
 707             value[0] = i;\r
 708 \r
 709             Cluster c = new Cluster(value);\r
 710             cluster.addElement(c);\r
 711         }\r
 712     }\r
 713 \r
 714     /**\r
 715      * DOCUMENT ME!\r
 716      *\r
 717      * @param node DOCUMENT ME!\r
 718      * @param leaves DOCUMENT ME!\r
 719      *\r
 720      * @return DOCUMENT ME!\r
 721      */\r
 722     public Vector findLeaves(SequenceNode node, Vector leaves)\r
 723     {\r
 724         if (node == null)\r
 725         {\r
 726             return leaves;\r
 727         }\r
 728 \r
 729         if ((node.left() == null) && (node.right() == null))\r
 730         {\r
 731             leaves.addElement(node);\r
 732 \r
 733             return leaves;\r
 734         }\r
 735         else\r
 736         {\r
 737             findLeaves((SequenceNode) node.left(), leaves);\r
 738             findLeaves((SequenceNode) node.right(), leaves);\r
 739         }\r
 740 \r
 741         return leaves;\r
 742     }\r
 743 \r
 744     /**\r
 745      * DOCUMENT ME!\r
 746      *\r
 747      * @param node DOCUMENT ME!\r
 748      * @param count DOCUMENT ME!\r
 749      *\r
 750      * @return DOCUMENT ME!\r
 751      */\r
 752     public Object findLeaf(SequenceNode node, int count)\r
 753     {\r
 754         found = _findLeaf(node, count);\r
 755 \r
 756         return found;\r
 757     }\r
 758 \r
 759     /**\r
 760      * DOCUMENT ME!\r
 761      *\r
 762      * @param node DOCUMENT ME!\r
 763      * @param count DOCUMENT ME!\r
 764      *\r
 765      * @return DOCUMENT ME!\r
 766      */\r
 767     public Object _findLeaf(SequenceNode node, int count)\r
 768     {\r
 769         if (node == null)\r
 770         {\r
 771             return null;\r
 772         }\r
 773 \r
 774         if (node.ycount == count)\r
 775         {\r
 776             found = node.element();\r
 777 \r
 778             return found;\r
 779         }\r
 780         else\r
 781         {\r
 782             _findLeaf((SequenceNode) node.left(), count);\r
 783             _findLeaf((SequenceNode) node.right(), count);\r
 784         }\r
 785 \r
 786         return found;\r
 787     }\r
 788 \r
 789     /**\r
 790      * printNode is mainly for debugging purposes.\r
 791      *\r
 792      * @param node SequenceNode\r
 793      */\r
 794     public void printNode(SequenceNode node)\r
 795     {\r
 796         if (node == null)\r
 797         {\r
 798             return;\r
 799         }\r
 800 \r
 801         if ((node.left() == null) && (node.right() == null))\r
 802         {\r
 803             System.out.println("Leaf = " +\r
 804                 ((SequenceI) node.element()).getName());\r
 805             System.out.println("Dist " + ((SequenceNode) node).dist);\r
 806             System.out.println("Boot " + node.getBootstrap());\r
 807         }\r
 808         else\r
 809         {\r
 810             System.out.println("Dist " + ((SequenceNode) node).dist);\r
 811             printNode((SequenceNode) node.left());\r
 812             printNode((SequenceNode) node.right());\r
 813         }\r
 814     }\r
 815 \r
 816     /**\r
 817      * DOCUMENT ME!\r
 818      *\r
 819      * @param node DOCUMENT ME!\r
 820      */\r
 821     public void findMaxDist(SequenceNode node)\r
 822     {\r
 823         if (node == null)\r
 824         {\r
 825             return;\r
 826         }\r
 827 \r
 828         if ((node.left() == null) && (node.right() == null))\r
 829         {\r
 830             float dist = ((SequenceNode) node).dist;\r
 831 \r
 832             if (dist > maxDistValue)\r
 833             {\r
 834                 maxdist = (SequenceNode) node;\r
 835                 maxDistValue = dist;\r
 836             }\r
 837         }\r
 838         else\r
 839         {\r
 840             findMaxDist((SequenceNode) node.left());\r
 841             findMaxDist((SequenceNode) node.right());\r
 842         }\r
 843     }\r
 844 \r
 845     /**\r
 846      * DOCUMENT ME!\r
 847      *\r
 848      * @return DOCUMENT ME!\r
 849      */\r
 850     public Vector getGroups()\r
 851     {\r
 852         return groups;\r
 853     }\r
 854 \r
 855     /**\r
 856      * DOCUMENT ME!\r
 857      *\r
 858      * @return DOCUMENT ME!\r
 859      */\r
 860     public float getMaxHeight()\r
 861     {\r
 862         return maxheight;\r
 863     }\r
 864 \r
 865     /**\r
 866      * DOCUMENT ME!\r
 867      *\r
 868      * @param node DOCUMENT ME!\r
 869      * @param threshold DOCUMENT ME!\r
 870      */\r
 871     public void groupNodes(SequenceNode node, float threshold)\r
 872     {\r
 873         if (node == null)\r
 874         {\r
 875             return;\r
 876         }\r
 877 \r
 878         if ((node.height / maxheight) > threshold)\r
 879         {\r
 880             groups.addElement(node);\r
 881         }\r
 882         else\r
 883         {\r
 884             groupNodes((SequenceNode) node.left(), threshold);\r
 885             groupNodes((SequenceNode) node.right(), threshold);\r
 886         }\r
 887     }\r
 888 \r
 889     /**\r
 890      * DOCUMENT ME!\r
 891      *\r
 892      * @param node DOCUMENT ME!\r
 893      *\r
 894      * @return DOCUMENT ME!\r
 895      */\r
 896     public float findHeight(SequenceNode node)\r
 897     {\r
 898         if (node == null)\r
 899         {\r
 900             return maxheight;\r
 901         }\r
 902 \r
 903         if ((node.left() == null) && (node.right() == null))\r
 904         {\r
 905             node.height = ((SequenceNode) node.parent()).height + node.dist;\r
 906 \r
 907             if (node.height > maxheight)\r
 908             {\r
 909                 return node.height;\r
 910             }\r
 911             else\r
 912             {\r
 913                 return maxheight;\r
 914             }\r
 915         }\r
 916         else\r
 917         {\r
 918             if (node.parent() != null)\r
 919             {\r
 920                 node.height = ((SequenceNode) node.parent()).height +\r
 921                     node.dist;\r
 922             }\r
 923             else\r
 924             {\r
 925                 maxheight = 0;\r
 926                 node.height = (float) 0.0;\r
 927             }\r
 928 \r
 929             maxheight = findHeight((SequenceNode) (node.left()));\r
 930             maxheight = findHeight((SequenceNode) (node.right()));\r
 931         }\r
 932 \r
 933         return maxheight;\r
 934     }\r
 935 \r
 936     /**\r
 937      * DOCUMENT ME!\r
 938      *\r
 939      * @return DOCUMENT ME!\r
 940      */\r
 941     public SequenceNode reRoot()\r
 942     {\r
 943         if (maxdist != null)\r
 944         {\r
 945             ycount = 0;\r
 946 \r
 947             float tmpdist = maxdist.dist;\r
 948 \r
 949             // New top\r
 950             SequenceNode sn = new SequenceNode();\r
 951             sn.setParent(null);\r
 952 \r
 953             // New right hand of top\r
 954             SequenceNode snr = (SequenceNode) maxdist.parent();\r
 955             changeDirection(snr, maxdist);\r
 956             System.out.println("Printing reversed tree");\r
 957             printN(snr);\r
 958             snr.dist = tmpdist / 2;\r
 959             maxdist.dist = tmpdist / 2;\r
 960 \r
 961             snr.setParent(sn);\r
 962             maxdist.setParent(sn);\r
 963 \r
 964             sn.setRight(snr);\r
 965             sn.setLeft(maxdist);\r
 966 \r
 967             top = sn;\r
 968 \r
 969             ycount = 0;\r
 970             reCount(top);\r
 971             findHeight(top);\r
 972         }\r
 973 \r
 974         return top;\r
 975     }\r
 976 \r
 977     /**\r
 978      * DOCUMENT ME!\r
 979      *\r
 980      * @param node DOCUMENT ME!\r
 981      */\r
 982     public static void printN(SequenceNode node)\r
 983     {\r
 984         if (node == null)\r
 985         {\r
 986             return;\r
 987         }\r
 988 \r
 989         if ((node.left() != null) && (node.right() != null))\r
 990         {\r
 991             printN((SequenceNode) node.left());\r
 992             printN((SequenceNode) node.right());\r
 993         }\r
 994         else\r
 995         {\r
 996             System.out.println(" name = " +\r
 997                 ((SequenceI) node.element()).getName());\r
 998         }\r
 999 \r
1000         System.out.println(" dist = " + ((SequenceNode) node).dist + " " +\r
1001             ((SequenceNode) node).count + " " + ((SequenceNode) node).height);\r
1002     }\r
1003 \r
1004     /**\r
1005      * DOCUMENT ME!\r
1006      *\r
1007      * @param node DOCUMENT ME!\r
1008      */\r
1009     public void reCount(SequenceNode node)\r
1010     {\r
1011         ycount = 0;\r
1012         _reCount(node);\r
1013     }\r
1014 \r
1015     /**\r
1016      * DOCUMENT ME!\r
1017      *\r
1018      * @param node DOCUMENT ME!\r
1019      */\r
1020     public void _reCount(SequenceNode node)\r
1021     {\r
1022         if (node == null)\r
1023         {\r
1024             return;\r
1025         }\r
1026 \r
1027         if ((node.left() != null) && (node.right() != null))\r
1028         {\r
1029             _reCount((SequenceNode) node.left());\r
1030             _reCount((SequenceNode) node.right());\r
1031 \r
1032             SequenceNode l = (SequenceNode) node.left();\r
1033             SequenceNode r = (SequenceNode) node.right();\r
1034 \r
1035             ((SequenceNode) node).count = l.count + r.count;\r
1036             ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;\r
1037         }\r
1038         else\r
1039         {\r
1040             ((SequenceNode) node).count = 1;\r
1041             ((SequenceNode) node).ycount = ycount++;\r
1042         }\r
1043     }\r
1044 \r
1045     /**\r
1046      * DOCUMENT ME!\r
1047      *\r
1048      * @param node DOCUMENT ME!\r
1049      */\r
1050     public void swapNodes(SequenceNode node)\r
1051     {\r
1052         if (node == null)\r
1053         {\r
1054             return;\r
1055         }\r
1056 \r
1057         SequenceNode tmp = (SequenceNode) node.left();\r
1058 \r
1059         node.setLeft(node.right());\r
1060         node.setRight(tmp);\r
1061     }\r
1062 \r
1063     /**\r
1064      * DOCUMENT ME!\r
1065      *\r
1066      * @param node DOCUMENT ME!\r
1067      * @param dir DOCUMENT ME!\r
1068      */\r
1069     public void changeDirection(SequenceNode node, SequenceNode dir)\r
1070     {\r
1071         if (node == null)\r
1072         {\r
1073             return;\r
1074         }\r
1075 \r
1076         if (node.parent() != top)\r
1077         {\r
1078             changeDirection((SequenceNode) node.parent(), node);\r
1079 \r
1080             SequenceNode tmp = (SequenceNode) node.parent();\r
1081 \r
1082             if (dir == node.left())\r
1083             {\r
1084                 node.setParent(dir);\r
1085                 node.setLeft(tmp);\r
1086             }\r
1087             else if (dir == node.right())\r
1088             {\r
1089                 node.setParent(dir);\r
1090                 node.setRight(tmp);\r
1091             }\r
1092         }\r
1093         else\r
1094         {\r
1095             if (dir == node.left())\r
1096             {\r
1097                 node.setParent(node.left());\r
1098 \r
1099                 if (top.left() == node)\r
1100                 {\r
1101                     node.setRight(top.right());\r
1102                 }\r
1103                 else\r
1104                 {\r
1105                     node.setRight(top.left());\r
1106                 }\r
1107             }\r
1108             else\r
1109             {\r
1110                 node.setParent(node.right());\r
1111 \r
1112                 if (top.left() == node)\r
1113                 {\r
1114                     node.setLeft(top.right());\r
1115                 }\r
1116                 else\r
1117                 {\r
1118                     node.setLeft(top.left());\r
1119                 }\r
1120             }\r
1121         }\r
1122     }\r
1123 \r
1124     /**\r
1125      * DOCUMENT ME!\r
1126      *\r
1127      * @param node DOCUMENT ME!\r
1128      */\r
1129     public void setMaxDist(SequenceNode node)\r
1130     {\r
1131         this.maxdist = maxdist;\r
1132     }\r
1133 \r
1134     /**\r
1135      * DOCUMENT ME!\r
1136      *\r
1137      * @return DOCUMENT ME!\r
1138      */\r
1139     public SequenceNode getMaxDist()\r
1140     {\r
1141         return maxdist;\r
1142     }\r
1143 \r
1144     /**\r
1145      * DOCUMENT ME!\r
1146      *\r
1147      * @return DOCUMENT ME!\r
1148      */\r
1149     public SequenceNode getTopNode()\r
1150     {\r
1151         return top;\r
1152     }\r
1153 }\r
1154 \r
1155 \r
1156 /**\r
1157  * DOCUMENT ME!\r
1158  *\r
1159  * @author $author$\r
1160  * @version $Revision$\r
1161  */\r
1162 class Cluster\r
1163 {\r
1164     int[] value;\r
1165 \r
1166     /**\r
1167      * Creates a new Cluster object.\r
1168      *\r
1169      * @param value DOCUMENT ME!\r
1170      */\r
1171     public Cluster(int[] value)\r
1172     {\r
1173         this.value = value;\r
1174     }\r
1175 }\r