src/jalview/analysis/TreeModel.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.analysis;
  22
  23 import jalview.bin.Cache;
  24 import jalview.datamodel.AlignmentView;
  25 import jalview.datamodel.BinaryNode;
  26 import jalview.datamodel.NodeTransformI;
  27 import jalview.datamodel.Sequence;
  28 import jalview.datamodel.SequenceI;
  29 import jalview.datamodel.SequenceNode;
  30 import jalview.io.NewickFile;
  31
  32 import java.util.ArrayList;
  33 import java.util.Enumeration;
  34 import java.util.List;
  35 import java.util.Vector;
  36
  37 /**
  38  * A model of a tree, either computed by Jalview or loaded from a file or other
  39  * resource or service
  40  */
  41 public class TreeModel
  42 {
  43
  44   SequenceI[] sequences;
  45
  46   /*
  47    * SequenceData is a string representation of what the user
  48    * sees. The display may contain hidden columns.
  49    */
  50   private AlignmentView seqData;
  51
  52   int noseqs;
  53
  54   BinaryNode top;
  55
  56   double maxDistValue;
  57
  58   double maxheight;
  59
  60   int ycount;
  61
  62   Vector<BinaryNode> node;
  63
  64   boolean hasDistances = true; // normal case for jalview trees
  65
  66   boolean hasBootstrap = false; // normal case for jalview trees
  67
  68   private boolean hasRootDistance = true;
  69
  70   /**
  71    * Create a new TreeModel object with leaves associated with sequences in
  72    * seqs, and (optionally) original alignment data represented by Cigar strings
  73    *
  74    * @param seqs
  75    *          SequenceI[]
  76    * @param odata
  77    *          Cigar[]
  78    * @param treefile
  79    *          NewickFile
  80    */
  81   public TreeModel(SequenceI[] seqs, AlignmentView odata,
  82           NewickFile treefile)
  83   {
  84     this(seqs, (SequenceNode) treefile.getTree(), treefile.HasDistances(),
  85             treefile.HasBootstrap(), treefile.HasRootDistance());
  86     seqData = odata;
  87
  88     associateLeavesToSequences(seqs);
  89   }
  90
  91   /**
  92    * Constructor given a calculated tree
  93    *
  94    * @param tree
  95    */
  96   public TreeModel(TreeBuilder tree)
  97   {
  98     this(tree.getSequences(), (SequenceNode) tree.getTopNode(), tree.hasDistances(),
  99             tree.hasBootstrap(), tree.hasRootDistance());
 100     seqData = tree.getOriginalData();
 101   }
 102
 103   /**
 104    * Constructor given sequences, root node and tree property flags
 105    *
 106    * @param seqs
 107    * @param root
 108    * @param hasDist
 109    * @param hasBoot
 110    * @param hasRootDist
 111    */
 112   public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
 113           boolean hasBoot, boolean hasRootDist)
 114   {
 115     this.sequences = seqs;
 116     top = root;
 117
 118     hasDistances = hasDist;
 119     hasBootstrap = hasBoot;
 120     hasRootDistance = hasRootDist;
 121
 122     maxheight = findHeight(top);
 123   }
 124
 125   /**
 126    * @param seqs
 127    */
 128   public void associateLeavesToSequences(SequenceI[] seqs)
 129   {
 130     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
 131
 132     Vector<BinaryNode> leaves = findLeaves(top);
 133
 134     int i = 0;
 135     int namesleft = seqs.length;
 136
 137     SequenceNode j;
 138     SequenceI nam;
 139     String realnam;
 140     Vector<SequenceI> one2many = new Vector<SequenceI>();
 141     // int countOne2Many = 0;
 142     while (i < leaves.size())
 143     {
 144       // TODO - decide if we get rid of the polymorphism here ?
 145       j = (SequenceNode)leaves.elementAt(i++);
 146       realnam = j.getName();
 147       nam = null;
 148
 149       if (namesleft > -1)
 150       {
 151         nam = algnIds.findIdMatch(realnam);
 152       }
 153
 154       if (nam != null)
 155       {
 156         j.setElement(nam);
 157         if (one2many.contains(nam))
 158         {
 159           // countOne2Many++;
 160           // if (Cache.isDebugEnabled())
 161           // Cache.debug("One 2 many relationship for
 162           // "+nam.getName());
 163         }
 164         else
 165         {
 166           one2many.addElement(nam);
 167           namesleft--;
 168         }
 169       }
 170       else
 171       {
 172         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
 173         j.setPlaceholder(true);
 174       }
 175     }
 176     // if (Cache.isDebugEnabled() && countOne2Many>0) {
 177     // Cache.debug("There were "+countOne2Many+" alignment
 178     // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
 179     // more leaves.");
 180     // }
 181     // one2many.clear();
 182   }
 183
 184   /**
 185    * Generate a string representation of the Tree
 186    *
 187    * @return Newick File with all tree data available
 188    */
 189   public String print()
 190   {
 191     NewickFile fout = new NewickFile(getTopNode());
 192
 193     return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
 194                                                                           // all
 195                                                                           // data
 196                                                                           // available
 197                                                                           // for
 198                                                                           // tree
 199   }
 200
 201   /**
 202    *
 203    * used when the alignment associated to a tree has changed.
 204    *
 205    * @param list
 206    *          Sequence set to be associated with tree nodes
 207    */
 208   public void updatePlaceHolders(List<SequenceI> list)
 209   {
 210     Vector<BinaryNode> leaves = findLeaves(top);
 211
 212     int sz = leaves.size();
 213     SequenceIdMatcher seqmatcher = null;
 214     int i = 0;
 215
 216     while (i < sz)
 217     {
 218       SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
 219
 220       if (list.contains(leaf.element()))
 221       {
 222         leaf.setPlaceholder(false);
 223       }
 224       else
 225       {
 226         if (seqmatcher == null)
 227         {
 228           // Only create this the first time we need it
 229           SequenceI[] seqs = new SequenceI[list.size()];
 230
 231           for (int j = 0; j < seqs.length; j++)
 232           {
 233             seqs[j] = list.get(j);
 234           }
 235
 236           seqmatcher = new SequenceIdMatcher(seqs);
 237         }
 238
 239         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
 240
 241         if (nam != null)
 242         {
 243           if (!leaf.isPlaceholder())
 244           {
 245             // remapping the node to a new sequenceI - should remove any refs to
 246             // old one.
 247             // TODO - make many sequenceI to one leaf mappings possible!
 248             // (JBPNote)
 249           }
 250           leaf.setPlaceholder(false);
 251           leaf.setElement(nam);
 252         }
 253         else
 254         {
 255           if (!leaf.isPlaceholder())
 256           {
 257             // Construct a new placeholder sequence object for this leaf
 258             leaf.setElement(
 259                     new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
 260           }
 261           leaf.setPlaceholder(true);
 262
 263         }
 264       }
 265     }
 266   }
 267
 268   /**
 269    * rename any nodes according to their associated sequence. This will modify
 270    * the tree's metadata! (ie the original NewickFile or newly generated
 271    * BinaryTree's label data)
 272    */
 273   public void renameAssociatedNodes()
 274   {
 275     applyToNodes(new NodeTransformI()
 276     {
 277
 278       @Override
 279       public void transform(BinaryNode nd)
 280       {
 281         Object el = nd.element();
 282         if (el != null && el instanceof SequenceI)
 283         {
 284           nd.setName(((SequenceI) el).getName());
 285         }
 286       }
 287     });
 288   }
 289
 290   /**
 291    * Search for leaf nodes below (or at) the given node
 292    *
 293    * @param top2
 294    *          root node to search from
 295    *
 296    * @return
 297    */
 298   public Vector<BinaryNode> findLeaves(BinaryNode top2)
 299   {
 300     Vector<BinaryNode> leaves = new Vector<BinaryNode>();
 301     findLeaves(top2, leaves);
 302     return leaves;
 303   }
 304
 305   /**
 306    * Search for leaf nodes.
 307    *
 308    * @param nd
 309    *          root node to search from
 310    * @param leaves
 311    *          Vector of leaves to add leaf node objects too.
 312    *
 313    * @return Vector of leaf nodes on binary tree
 314    */
 315   Vector<BinaryNode> findLeaves(BinaryNode nd,
 316           Vector<BinaryNode> leaves)
 317   {
 318     if (nd == null)
 319     {
 320       return leaves;
 321     }
 322
 323     if ((nd.left() == null) && (nd.right() == null)) // Interior node
 324     // detection
 325     {
 326       leaves.addElement(nd);
 327
 328       return leaves;
 329     }
 330     else
 331     {
 332       /*
 333        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
 334        * leaves.addElement(node); }
 335        */
 336       findLeaves((SequenceNode) nd.left(), leaves);
 337       findLeaves((SequenceNode) nd.right(), leaves);
 338     }
 339
 340     return leaves;
 341   }
 342
 343   /**
 344    * printNode is mainly for debugging purposes.
 345    *
 346    * @param nd
 347    *          SequenceNode
 348    */
 349   void printNode(BinaryNode nd)
 350   {
 351     if (nd == null)
 352     {
 353       return;
 354     }
 355
 356     if ((nd.left() == null) && (nd.right() == null))
 357     {
 358       System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
 359       System.out.println("Dist " + nd.dist);
 360       System.out.println("Boot " + nd.getBootstrap());
 361     }
 362     else
 363     {
 364       System.out.println("Dist " + nd.dist);
 365       printNode((BinaryNode) nd.left());
 366       printNode((BinaryNode) nd.right());
 367     }
 368   }
 369
 370   /**
 371    * DOCUMENT ME!
 372    *
 373    * @return DOCUMENT ME!
 374    */
 375   public double getMaxHeight()
 376   {
 377     return maxheight;
 378   }
 379
 380   /**
 381    * Makes a list of groups, where each group is represented by a node whose
 382    * height (distance from the root node), as a fraction of the height of the
 383    * whole tree, is greater than the given threshold. This corresponds to
 384    * selecting the nodes immediately to the right of a vertical line
 385    * partitioning the tree (if the tree is drawn with root to the left). Each
 386    * such node represents a group that contains all of the sequences linked to
 387    * the child leaf nodes.
 388    *
 389    * @param threshold
 390    * @see #getGroups()
 391    */
 392   public List<BinaryNode> groupNodes(float threshold)
 393   {
 394     List<BinaryNode> groups = new ArrayList<BinaryNode>();
 395     _groupNodes(groups, getTopNode(), threshold);
 396     return groups;
 397   }
 398
 399   protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
 400           float threshold)
 401   {
 402     if (nd == null)
 403     {
 404       return;
 405     }
 406
 407     if ((nd.height / maxheight) > threshold)
 408     {
 409       groups.add(nd);
 410     }
 411     else
 412     {
 413       _groupNodes(groups, (SequenceNode) nd.left(), threshold);
 414       _groupNodes(groups, (SequenceNode) nd.right(), threshold);
 415     }
 416   }
 417
 418   /**
 419    * DOCUMENT ME!
 420    *
 421    * @param nd
 422    *          DOCUMENT ME!
 423    *
 424    * @return DOCUMENT ME!
 425    */
 426   public double findHeight(BinaryNode nd)
 427   {
 428     if (nd == null)
 429     {
 430       return maxheight;
 431     }
 432
 433     if ((nd.left() == null) && (nd.right() == null))
 434     {
 435       nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 436
 437       if (nd.height > maxheight)
 438       {
 439         return nd.height;
 440       }
 441       else
 442       {
 443         return maxheight;
 444       }
 445     }
 446     else
 447     {
 448       if (nd.parent() != null)
 449       {
 450         nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 451       }
 452       else
 453       {
 454         maxheight = 0;
 455         nd.height = (float) 0.0;
 456       }
 457
 458       maxheight = findHeight((BinaryNode) (nd.left()));
 459       maxheight = findHeight((BinaryNode) (nd.right()));
 460     }
 461
 462     return maxheight;
 463   }
 464
 465   /**
 466    * DOCUMENT ME!
 467    *
 468    * @param nd
 469    *          DOCUMENT ME!
 470    */
 471   void printN(BinaryNode nd)
 472   {
 473     if (nd == null)
 474     {
 475       return;
 476     }
 477
 478     if ((nd.left() != null) && (nd.right() != null))
 479     {
 480       printN((BinaryNode) nd.left());
 481       printN((BinaryNode) nd.right());
 482     }
 483     else
 484     {
 485       System.out.println(" name = " + ((SequenceI) nd.element()).getName());
 486     }
 487
 488     System.out.println(
 489             " dist = " + nd.dist + " " + nd.count + " " + nd.height);
 490   }
 491
 492   /**
 493    * DOCUMENT ME!
 494    *
 495    * @param nd
 496    *          DOCUMENT ME!
 497    */
 498   public void reCount(BinaryNode nd)
 499   {
 500     ycount = 0;
 501     // _lycount = 0;
 502     // _lylimit = this.node.size();
 503     _reCount(nd);
 504   }
 505
 506   // private long _lycount = 0, _lylimit = 0;
 507
 508   /**
 509    * DOCUMENT ME!
 510    *
 511    * @param nd
 512    *          DOCUMENT ME!
 513    */
 514   void _reCount(BinaryNode nd)
 515   {
 516     // if (_lycount<_lylimit)
 517     // {
 518     // System.err.println("Warning: depth of _recount greater than number of
 519     // nodes.");
 520     // }
 521     if (nd == null)
 522     {
 523       return;
 524     }
 525     // _lycount++;
 526
 527     if ((nd.left() != null) && (nd.right() != null))
 528     {
 529
 530       _reCount((BinaryNode) nd.left());
 531       _reCount((BinaryNode) nd.right());
 532
 533       BinaryNode l = (BinaryNode) nd.left();
 534       BinaryNode r = (BinaryNode) nd.right();
 535
 536       nd.count = l.count + r.count;
 537       nd.ycount = (l.ycount + r.ycount) / 2;
 538     }
 539     else
 540     {
 541       nd.count = 1;
 542       nd.ycount = ycount++;
 543     }
 544     // _lycount--;
 545   }
 546
 547   /**
 548    * DOCUMENT ME!
 549    *
 550    * @param nd
 551    *          DOCUMENT ME!
 552    */
 553   public void swapNodes(BinaryNode nd)
 554   {
 555     if (nd == null)
 556     {
 557       return;
 558     }
 559
 560     BinaryNode tmp = (BinaryNode) nd.left();
 561
 562     nd.setLeft(nd.right());
 563     nd.setRight(tmp);
 564   }
 565
 566   /**
 567    * DOCUMENT ME!
 568    *
 569    * @param nd
 570    *          DOCUMENT ME!
 571    * @param dir
 572    *          DOCUMENT ME!
 573    */
 574   void changeDirection(BinaryNode nd, BinaryNode dir)
 575   {
 576     if (nd == null)
 577     {
 578       return;
 579     }
 580
 581     if (nd.parent() != top)
 582     {
 583       changeDirection((BinaryNode) nd.parent(), nd);
 584
 585       BinaryNode tmp = (BinaryNode) nd.parent();
 586
 587       if (dir == nd.left())
 588       {
 589         nd.setParent(dir);
 590         nd.setLeft(tmp);
 591       }
 592       else if (dir == nd.right())
 593       {
 594         nd.setParent(dir);
 595         nd.setRight(tmp);
 596       }
 597     }
 598     else
 599     {
 600       if (dir == nd.left())
 601       {
 602         nd.setParent(nd.left());
 603
 604         if (top.left() == nd)
 605         {
 606           nd.setRight(top.right());
 607         }
 608         else
 609         {
 610           nd.setRight(top.left());
 611         }
 612       }
 613       else
 614       {
 615         nd.setParent(nd.right());
 616
 617         if (top.left() == nd)
 618         {
 619           nd.setLeft(top.right());
 620         }
 621         else
 622         {
 623           nd.setLeft(top.left());
 624         }
 625       }
 626     }
 627   }
 628
 629   /**
 630    * DOCUMENT ME!
 631    *
 632    * @return DOCUMENT ME!
 633    */
 634   public BinaryNode getTopNode()
 635   {
 636     return top;
 637   }
 638
 639   /**
 640    *
 641    * @return true if tree has real distances
 642    */
 643   public boolean hasDistances()
 644   {
 645     return hasDistances;
 646   }
 647
 648   /**
 649    *
 650    * @return true if tree has real bootstrap values
 651    */
 652   public boolean hasBootstrap()
 653   {
 654     return hasBootstrap;
 655   }
 656
 657   public boolean hasRootDistance()
 658   {
 659     return hasRootDistance;
 660   }
 661
 662   /**
 663    * apply the given transform to all the nodes in the tree.
 664    *
 665    * @param nodeTransformI
 666    */
 667   public void applyToNodes(NodeTransformI nodeTransformI)
 668   {
 669     for (Enumeration<BinaryNode> nodes = node.elements(); nodes
 670             .hasMoreElements(); nodeTransformI
 671                     .transform(nodes.nextElement()))
 672     {
 673       ;
 674     }
 675   }
 676
 677   public AlignmentView getOriginalData()
 678   {
 679     return seqData;
 680   }
 681 }