src/jalview/analysis/NJTree.java

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