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 public class NJTree {\r
  33     Vector cluster;\r
  34     SequenceI[] sequence;\r
  35     int[] done;\r
  36     int noseqs;\r
  37     int noClus;\r
  38     float[][] distance;\r
  39     int mini;\r
  40     int minj;\r
  41     float ri;\r
  42     float rj;\r
  43     Vector groups = new Vector();\r
  44     SequenceNode maxdist;\r
  45     SequenceNode top;\r
  46     float maxDistValue;\r
  47     float maxheight;\r
  48     int ycount;\r
  49     Vector node;\r
  50     String type;\r
  51     String pwtype;\r
  52     Object found = null;\r
  53     Object leaves = null;\r
  54     int start;\r
  55     int end;\r
  56 \r
  57     public NJTree(SequenceNode node) {\r
  58         top = node;\r
  59         maxheight = findHeight(top);\r
  60     }\r
  61 \r
  62     public NJTree(SequenceI[] seqs, NewickFile treefile) {\r
  63         top = treefile.getTree();\r
  64         maxheight = findHeight(top);\r
  65 \r
  66         SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);\r
  67 \r
  68         Vector leaves = new Vector();\r
  69         findLeaves(top, leaves);\r
  70 \r
  71         int i = 0;\r
  72         int namesleft = seqs.length;\r
  73 \r
  74         SequenceNode j;\r
  75         SequenceI nam;\r
  76         String realnam;\r
  77 \r
  78         while (i < leaves.size()) {\r
  79             j = (SequenceNode) leaves.elementAt(i++);\r
  80             realnam = j.getName();\r
  81             nam = null;\r
  82 \r
  83             if (namesleft > -1) {\r
  84                 nam = algnIds.findIdMatch(realnam);\r
  85             }\r
  86 \r
  87             if (nam != null) {\r
  88                 j.setElement(nam);\r
  89                 namesleft--;\r
  90             } else {\r
  91                 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));\r
  92                 j.setPlaceholder(true);\r
  93             }\r
  94         }\r
  95     }\r
  96 \r
  97     public NJTree(SequenceI[] sequence, int start, int end) {\r
  98         this(sequence, "NJ", "BL", start, end);\r
  99     }\r
 100 \r
 101     public NJTree(SequenceI[] sequence, String type, String pwtype, int start,\r
 102         int end) {\r
 103         this.sequence = sequence;\r
 104         this.node = new Vector();\r
 105         this.type = type;\r
 106         this.pwtype = pwtype;\r
 107         this.start = start;\r
 108         this.end = end;\r
 109 \r
 110         if (!(type.equals("NJ"))) {\r
 111             type = "AV";\r
 112         }\r
 113 \r
 114         if (!(pwtype.equals("PID"))) {\r
 115             type = "BL";\r
 116         }\r
 117 \r
 118         int i = 0;\r
 119 \r
 120         done = new int[sequence.length];\r
 121 \r
 122         while ((i < sequence.length) && (sequence[i] != null)) {\r
 123             done[i] = 0;\r
 124             i++;\r
 125         }\r
 126 \r
 127         noseqs = i++;\r
 128 \r
 129         distance = findDistances();\r
 130 \r
 131         makeLeaves();\r
 132 \r
 133         noClus = cluster.size();\r
 134 \r
 135         cluster();\r
 136     }\r
 137 \r
 138     public String toString() {\r
 139         jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());\r
 140 \r
 141         return fout.print(false, true); // distances only\r
 142     }\r
 143 \r
 144     /**\r
 145      *\r
 146      * used when the alignment associated to a tree has changed.\r
 147      *\r
 148      * @param alignment Vector\r
 149      */\r
 150     public void UpdatePlaceHolders(Vector alignment) {\r
 151         Vector leaves = new Vector();\r
 152         findLeaves(top, leaves);\r
 153 \r
 154         int sz = leaves.size();\r
 155         SequenceIdMatcher seqmatcher = null;\r
 156         int i = 0;\r
 157 \r
 158         while (i < sz) {\r
 159             SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
 160 \r
 161             if (alignment.contains(leaf.element())) {\r
 162                 leaf.setPlaceholder(false);\r
 163             } else {\r
 164                 if (seqmatcher == null) {\r
 165                     // Only create this the first time we need it\r
 166                     SequenceI[] seqs = new SequenceI[alignment.size()];\r
 167 \r
 168                     for (int j = 0; j < seqs.length; j++)\r
 169                         seqs[j] = (SequenceI) alignment.elementAt(j);\r
 170 \r
 171                     seqmatcher = new SequenceIdMatcher(seqs);\r
 172                 }\r
 173 \r
 174                 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());\r
 175 \r
 176                 if (nam != null) {\r
 177                     leaf.setPlaceholder(false);\r
 178                     leaf.setElement(nam);\r
 179                 } else {\r
 180                     leaf.setPlaceholder(true);\r
 181                 }\r
 182             }\r
 183         }\r
 184     }\r
 185 \r
 186     public void cluster() {\r
 187         while (noClus > 2) {\r
 188             if (type.equals("NJ")) {\r
 189                 float mind = findMinNJDistance();\r
 190             } else {\r
 191                 float mind = findMinDistance();\r
 192             }\r
 193 \r
 194             Cluster c = joinClusters(mini, minj);\r
 195 \r
 196             done[minj] = 1;\r
 197 \r
 198             cluster.setElementAt(null, minj);\r
 199             cluster.setElementAt(c, mini);\r
 200 \r
 201             noClus--;\r
 202         }\r
 203 \r
 204         boolean onefound = false;\r
 205 \r
 206         int one = -1;\r
 207         int two = -1;\r
 208 \r
 209         for (int i = 0; i < noseqs; i++) {\r
 210             if (done[i] != 1) {\r
 211                 if (onefound == false) {\r
 212                     two = i;\r
 213                     onefound = true;\r
 214                 } else {\r
 215                     one = i;\r
 216                 }\r
 217             }\r
 218         }\r
 219 \r
 220         Cluster c = joinClusters(one, two);\r
 221         top = (SequenceNode) (node.elementAt(one));\r
 222 \r
 223         reCount(top);\r
 224         findHeight(top);\r
 225         findMaxDist(top);\r
 226     }\r
 227 \r
 228     public Cluster joinClusters(int i, int j) {\r
 229         float dist = distance[i][j];\r
 230 \r
 231         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
 232         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
 233 \r
 234         int[] value = new int[noi + noj];\r
 235 \r
 236         for (int ii = 0; ii < noi; ii++) {\r
 237             value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];\r
 238         }\r
 239 \r
 240         for (int ii = noi; ii < (noi + noj); ii++) {\r
 241             value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];\r
 242         }\r
 243 \r
 244         Cluster c = new Cluster(value);\r
 245 \r
 246         ri = findr(i, j);\r
 247         rj = findr(j, i);\r
 248 \r
 249         if (type.equals("NJ")) {\r
 250             findClusterNJDistance(i, j);\r
 251         } else {\r
 252             findClusterDistance(i, j);\r
 253         }\r
 254 \r
 255         SequenceNode sn = new SequenceNode();\r
 256 \r
 257         sn.setLeft((SequenceNode) (node.elementAt(i)));\r
 258         sn.setRight((SequenceNode) (node.elementAt(j)));\r
 259 \r
 260         SequenceNode tmpi = (SequenceNode) (node.elementAt(i));\r
 261         SequenceNode tmpj = (SequenceNode) (node.elementAt(j));\r
 262 \r
 263         if (type.equals("NJ")) {\r
 264             findNewNJDistances(tmpi, tmpj, dist);\r
 265         } else {\r
 266             findNewDistances(tmpi, tmpj, dist);\r
 267         }\r
 268 \r
 269         tmpi.setParent(sn);\r
 270         tmpj.setParent(sn);\r
 271 \r
 272         node.setElementAt(sn, i);\r
 273 \r
 274         return c;\r
 275     }\r
 276 \r
 277     public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,\r
 278         float dist) {\r
 279         float ih = 0;\r
 280         float jh = 0;\r
 281 \r
 282         SequenceNode sni = tmpi;\r
 283         SequenceNode snj = tmpj;\r
 284 \r
 285         tmpi.dist = ((dist + ri) - rj) / 2;\r
 286         tmpj.dist = (dist - tmpi.dist);\r
 287 \r
 288         if (tmpi.dist < 0) {\r
 289             tmpi.dist = 0;\r
 290         }\r
 291 \r
 292         if (tmpj.dist < 0) {\r
 293             tmpj.dist = 0;\r
 294         }\r
 295     }\r
 296 \r
 297     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,\r
 298         float dist) {\r
 299         float ih = 0;\r
 300         float jh = 0;\r
 301 \r
 302         SequenceNode sni = tmpi;\r
 303         SequenceNode snj = tmpj;\r
 304 \r
 305         while (sni != null) {\r
 306             ih = ih + sni.dist;\r
 307             sni = (SequenceNode) sni.left();\r
 308         }\r
 309 \r
 310         while (snj != null) {\r
 311             jh = jh + snj.dist;\r
 312             snj = (SequenceNode) snj.left();\r
 313         }\r
 314 \r
 315         tmpi.dist = ((dist / 2) - ih);\r
 316         tmpj.dist = ((dist / 2) - jh);\r
 317     }\r
 318 \r
 319     public void findClusterDistance(int i, int j) {\r
 320         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
 321         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
 322 \r
 323         // New distances from cluster to others\r
 324         float[] newdist = new float[noseqs];\r
 325 \r
 326         for (int l = 0; l < noseqs; l++) {\r
 327             if ((l != i) && (l != j)) {\r
 328                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +\r
 329                     noj);\r
 330             } else {\r
 331                 newdist[l] = 0;\r
 332             }\r
 333         }\r
 334 \r
 335         for (int ii = 0; ii < noseqs; ii++) {\r
 336             distance[i][ii] = newdist[ii];\r
 337             distance[ii][i] = newdist[ii];\r
 338         }\r
 339     }\r
 340 \r
 341     public void findClusterNJDistance(int i, int j) {\r
 342         int noi = ((Cluster) cluster.elementAt(i)).value.length;\r
 343         int noj = ((Cluster) cluster.elementAt(j)).value.length;\r
 344 \r
 345         // New distances from cluster to others\r
 346         float[] newdist = new float[noseqs];\r
 347 \r
 348         for (int l = 0; l < noseqs; l++) {\r
 349             if ((l != i) && (l != j)) {\r
 350                 newdist[l] = ((distance[i][l] + distance[j][l]) -\r
 351                     distance[i][j]) / 2;\r
 352             } else {\r
 353                 newdist[l] = 0;\r
 354             }\r
 355         }\r
 356 \r
 357         for (int ii = 0; ii < noseqs; ii++) {\r
 358             distance[i][ii] = newdist[ii];\r
 359             distance[ii][i] = newdist[ii];\r
 360         }\r
 361     }\r
 362 \r
 363     public float findr(int i, int j) {\r
 364         float tmp = 1;\r
 365 \r
 366         for (int k = 0; k < noseqs; k++) {\r
 367             if ((k != i) && (k != j) && (done[k] != 1)) {\r
 368                 tmp = tmp + distance[i][k];\r
 369             }\r
 370         }\r
 371 \r
 372         if (noClus > 2) {\r
 373             tmp = tmp / (noClus - 2);\r
 374         }\r
 375 \r
 376         return tmp;\r
 377     }\r
 378 \r
 379     public float findMinNJDistance() {\r
 380         float min = 100000;\r
 381 \r
 382         for (int i = 0; i < (noseqs - 1); i++) {\r
 383             for (int j = i + 1; j < noseqs; j++) {\r
 384                 if ((done[i] != 1) && (done[j] != 1)) {\r
 385                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));\r
 386 \r
 387                     if (tmp < min) {\r
 388                         mini = i;\r
 389                         minj = j;\r
 390 \r
 391                         min = tmp;\r
 392                     }\r
 393                 }\r
 394             }\r
 395         }\r
 396 \r
 397         return min;\r
 398     }\r
 399 \r
 400     public float findMinDistance() {\r
 401         float min = 100000;\r
 402 \r
 403         for (int i = 0; i < (noseqs - 1); i++) {\r
 404             for (int j = i + 1; j < noseqs; j++) {\r
 405                 if ((done[i] != 1) && (done[j] != 1)) {\r
 406                     if (distance[i][j] < min) {\r
 407                         mini = i;\r
 408                         minj = j;\r
 409 \r
 410                         min = distance[i][j];\r
 411                     }\r
 412                 }\r
 413             }\r
 414         }\r
 415 \r
 416         return min;\r
 417     }\r
 418 \r
 419     public float[][] findDistances() {\r
 420         float[][] distance = new float[noseqs][noseqs];\r
 421 \r
 422         if (pwtype.equals("PID")) {\r
 423             for (int i = 0; i < (noseqs - 1); i++) {\r
 424                 for (int j = i; j < noseqs; j++) {\r
 425                     if (j == i) {\r
 426                         distance[i][i] = 0;\r
 427                     } else {\r
 428                         distance[i][j] = 100 -\r
 429                             Comparison.PID(sequence[i], sequence[j], start, end);\r
 430                         distance[j][i] = distance[i][j];\r
 431                     }\r
 432                 }\r
 433             }\r
 434         } else if (pwtype.equals("BL")) {\r
 435             int maxscore = 0;\r
 436 \r
 437             for (int i = 0; i < (noseqs - 1); i++) {\r
 438                 for (int j = i; j < noseqs; j++) {\r
 439                     int score = 0;\r
 440 \r
 441                     for (int k = start; k < end; k++) {\r
 442                         try {\r
 443                             score += ResidueProperties.getBLOSUM62(sequence[i].getSequence(\r
 444                                     k, k + 1), sequence[j].getSequence(k, k +\r
 445                                     1));\r
 446                         } catch (Exception ex) {\r
 447                             System.err.println("err creating BLOSUM62 tree");\r
 448                             ex.printStackTrace();\r
 449                         }\r
 450                     }\r
 451 \r
 452                     distance[i][j] = (float) score;\r
 453 \r
 454                     if (score > maxscore) {\r
 455                         maxscore = score;\r
 456                     }\r
 457                 }\r
 458             }\r
 459 \r
 460             for (int i = 0; i < (noseqs - 1); i++) {\r
 461                 for (int j = i; j < noseqs; j++) {\r
 462                     distance[i][j] = (float) maxscore - distance[i][j];\r
 463                     distance[j][i] = distance[i][j];\r
 464                 }\r
 465             }\r
 466         } else if (pwtype.equals("SW")) {\r
 467             float max = -1;\r
 468 \r
 469             for (int i = 0; i < (noseqs - 1); i++) {\r
 470                 for (int j = i; j < noseqs; j++) {\r
 471                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");\r
 472                     as.calcScoreMatrix();\r
 473                     as.traceAlignment();\r
 474                     as.printAlignment();\r
 475                     distance[i][j] = (float) as.maxscore;\r
 476 \r
 477                     if (max < distance[i][j]) {\r
 478                         max = distance[i][j];\r
 479                     }\r
 480                 }\r
 481             }\r
 482 \r
 483             for (int i = 0; i < (noseqs - 1); i++) {\r
 484                 for (int j = i; j < noseqs; j++) {\r
 485                     distance[i][j] = max - distance[i][j];\r
 486                     distance[j][i] = distance[i][j];\r
 487                 }\r
 488             }\r
 489         }\r
 490 \r
 491         return distance;\r
 492     }\r
 493 \r
 494     public void makeLeaves() {\r
 495         cluster = new Vector();\r
 496 \r
 497         for (int i = 0; i < noseqs; i++) {\r
 498             SequenceNode sn = new SequenceNode();\r
 499 \r
 500             sn.setElement(sequence[i]);\r
 501             sn.setName(sequence[i].getName());\r
 502             node.addElement(sn);\r
 503 \r
 504             int[] value = new int[1];\r
 505             value[0] = i;\r
 506 \r
 507             Cluster c = new Cluster(value);\r
 508             cluster.addElement(c);\r
 509         }\r
 510     }\r
 511 \r
 512     public Vector findLeaves(SequenceNode node, Vector leaves) {\r
 513         if (node == null) {\r
 514             return leaves;\r
 515         }\r
 516 \r
 517         if ((node.left() == null) && (node.right() == null)) {\r
 518             leaves.addElement(node);\r
 519 \r
 520             return leaves;\r
 521         } else {\r
 522             findLeaves((SequenceNode) node.left(), leaves);\r
 523             findLeaves((SequenceNode) node.right(), leaves);\r
 524         }\r
 525 \r
 526         return leaves;\r
 527     }\r
 528 \r
 529     public Object findLeaf(SequenceNode node, int count) {\r
 530         found = _findLeaf(node, count);\r
 531 \r
 532         return found;\r
 533     }\r
 534 \r
 535     public Object _findLeaf(SequenceNode node, int count) {\r
 536         if (node == null) {\r
 537             return null;\r
 538         }\r
 539 \r
 540         if (node.ycount == count) {\r
 541             found = node.element();\r
 542 \r
 543             return found;\r
 544         } else {\r
 545             _findLeaf((SequenceNode) node.left(), count);\r
 546             _findLeaf((SequenceNode) node.right(), count);\r
 547         }\r
 548 \r
 549         return found;\r
 550     }\r
 551 \r
 552     /**\r
 553      * printNode is mainly for debugging purposes.\r
 554      *\r
 555      * @param node SequenceNode\r
 556      */\r
 557     public void printNode(SequenceNode node) {\r
 558         if (node == null) {\r
 559             return;\r
 560         }\r
 561 \r
 562         if ((node.left() == null) && (node.right() == null)) {\r
 563             System.out.println("Leaf = " +\r
 564                 ((SequenceI) node.element()).getName());\r
 565             System.out.println("Dist " + ((SequenceNode) node).dist);\r
 566             System.out.println("Boot " + node.getBootstrap());\r
 567         } else {\r
 568             System.out.println("Dist " + ((SequenceNode) node).dist);\r
 569             printNode((SequenceNode) node.left());\r
 570             printNode((SequenceNode) node.right());\r
 571         }\r
 572     }\r
 573 \r
 574     public void findMaxDist(SequenceNode node) {\r
 575         if (node == null) {\r
 576             return;\r
 577         }\r
 578 \r
 579         if ((node.left() == null) && (node.right() == null)) {\r
 580             float dist = ((SequenceNode) node).dist;\r
 581 \r
 582             if (dist > maxDistValue) {\r
 583                 maxdist = (SequenceNode) node;\r
 584                 maxDistValue = dist;\r
 585             }\r
 586         } else {\r
 587             findMaxDist((SequenceNode) node.left());\r
 588             findMaxDist((SequenceNode) node.right());\r
 589         }\r
 590     }\r
 591 \r
 592     public Vector getGroups() {\r
 593         return groups;\r
 594     }\r
 595 \r
 596     public float getMaxHeight() {\r
 597         return maxheight;\r
 598     }\r
 599 \r
 600     public void groupNodes(SequenceNode node, float threshold) {\r
 601         if (node == null) {\r
 602             return;\r
 603         }\r
 604 \r
 605         if ((node.height / maxheight) > threshold) {\r
 606             groups.addElement(node);\r
 607         } else {\r
 608             groupNodes((SequenceNode) node.left(), threshold);\r
 609             groupNodes((SequenceNode) node.right(), threshold);\r
 610         }\r
 611     }\r
 612 \r
 613     public float findHeight(SequenceNode node) {\r
 614         if (node == null) {\r
 615             return maxheight;\r
 616         }\r
 617 \r
 618         if ((node.left() == null) && (node.right() == null)) {\r
 619             node.height = ((SequenceNode) node.parent()).height + node.dist;\r
 620 \r
 621             if (node.height > maxheight) {\r
 622                 return node.height;\r
 623             } else {\r
 624                 return maxheight;\r
 625             }\r
 626         } else {\r
 627             if (node.parent() != null) {\r
 628                 node.height = ((SequenceNode) node.parent()).height +\r
 629                     node.dist;\r
 630             } else {\r
 631                 maxheight = 0;\r
 632                 node.height = (float) 0.0;\r
 633             }\r
 634 \r
 635             maxheight = findHeight((SequenceNode) (node.left()));\r
 636             maxheight = findHeight((SequenceNode) (node.right()));\r
 637         }\r
 638 \r
 639         return maxheight;\r
 640     }\r
 641 \r
 642     public SequenceNode reRoot() {\r
 643         if (maxdist != null) {\r
 644             ycount = 0;\r
 645 \r
 646             float tmpdist = maxdist.dist;\r
 647 \r
 648             // New top\r
 649             SequenceNode sn = new SequenceNode();\r
 650             sn.setParent(null);\r
 651 \r
 652             // New right hand of top\r
 653             SequenceNode snr = (SequenceNode) maxdist.parent();\r
 654             changeDirection(snr, maxdist);\r
 655             System.out.println("Printing reversed tree");\r
 656             printN(snr);\r
 657             snr.dist = tmpdist / 2;\r
 658             maxdist.dist = tmpdist / 2;\r
 659 \r
 660             snr.setParent(sn);\r
 661             maxdist.setParent(sn);\r
 662 \r
 663             sn.setRight(snr);\r
 664             sn.setLeft(maxdist);\r
 665 \r
 666             top = sn;\r
 667 \r
 668             ycount = 0;\r
 669             reCount(top);\r
 670             findHeight(top);\r
 671         }\r
 672 \r
 673         return top;\r
 674     }\r
 675 \r
 676     public static void printN(SequenceNode node) {\r
 677         if (node == null) {\r
 678             return;\r
 679         }\r
 680 \r
 681         if ((node.left() != null) && (node.right() != null)) {\r
 682             printN((SequenceNode) node.left());\r
 683             printN((SequenceNode) node.right());\r
 684         } else {\r
 685             System.out.println(" name = " +\r
 686                 ((SequenceI) node.element()).getName());\r
 687         }\r
 688 \r
 689         System.out.println(" dist = " + ((SequenceNode) node).dist + " " +\r
 690             ((SequenceNode) node).count + " " + ((SequenceNode) node).height);\r
 691     }\r
 692 \r
 693     public void reCount(SequenceNode node) {\r
 694         ycount = 0;\r
 695         _reCount(node);\r
 696     }\r
 697 \r
 698     public void _reCount(SequenceNode node) {\r
 699         if (node == null) {\r
 700             return;\r
 701         }\r
 702 \r
 703         if ((node.left() != null) && (node.right() != null)) {\r
 704             _reCount((SequenceNode) node.left());\r
 705             _reCount((SequenceNode) node.right());\r
 706 \r
 707             SequenceNode l = (SequenceNode) node.left();\r
 708             SequenceNode r = (SequenceNode) node.right();\r
 709 \r
 710             ((SequenceNode) node).count = l.count + r.count;\r
 711             ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;\r
 712         } else {\r
 713             ((SequenceNode) node).count = 1;\r
 714             ((SequenceNode) node).ycount = ycount++;\r
 715         }\r
 716     }\r
 717 \r
 718     public void swapNodes(SequenceNode node) {\r
 719         if (node == null) {\r
 720             return;\r
 721         }\r
 722 \r
 723         SequenceNode tmp = (SequenceNode) node.left();\r
 724 \r
 725         node.setLeft(node.right());\r
 726         node.setRight(tmp);\r
 727     }\r
 728 \r
 729     public void changeDirection(SequenceNode node, SequenceNode dir) {\r
 730         if (node == null) {\r
 731             return;\r
 732         }\r
 733 \r
 734         if (node.parent() != top) {\r
 735             changeDirection((SequenceNode) node.parent(), node);\r
 736 \r
 737             SequenceNode tmp = (SequenceNode) node.parent();\r
 738 \r
 739             if (dir == node.left()) {\r
 740                 node.setParent(dir);\r
 741                 node.setLeft(tmp);\r
 742             } else if (dir == node.right()) {\r
 743                 node.setParent(dir);\r
 744                 node.setRight(tmp);\r
 745             }\r
 746         } else {\r
 747             if (dir == node.left()) {\r
 748                 node.setParent(node.left());\r
 749 \r
 750                 if (top.left() == node) {\r
 751                     node.setRight(top.right());\r
 752                 } else {\r
 753                     node.setRight(top.left());\r
 754                 }\r
 755             } else {\r
 756                 node.setParent(node.right());\r
 757 \r
 758                 if (top.left() == node) {\r
 759                     node.setLeft(top.right());\r
 760                 } else {\r
 761                     node.setLeft(top.left());\r
 762                 }\r
 763             }\r
 764         }\r
 765     }\r
 766 \r
 767     public void setMaxDist(SequenceNode node) {\r
 768         this.maxdist = maxdist;\r
 769     }\r
 770 \r
 771     public SequenceNode getMaxDist() {\r
 772         return maxdist;\r
 773     }\r
 774 \r
 775     public SequenceNode getTopNode() {\r
 776         return top;\r
 777     }\r
 778 }\r
 779 \r
 780 \r
 781 class Cluster {\r
 782     int[] value;\r
 783 \r
 784     public Cluster(int[] value) {\r
 785         this.value = value;\r
 786     }\r
 787 }\r