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   SequenceNode top;
  55
  56   double maxDistValue;
  57
  58   double maxheight;
  59
  60   int ycount;
  61
  62   Vector<SequenceNode> 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, 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(), 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<SequenceNode> 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       j = leaves.elementAt(i++);
 145       realnam = j.getName();
 146       nam = null;
 147
 148       if (namesleft > -1)
 149       {
 150         nam = algnIds.findIdMatch(realnam);
 151       }
 152
 153       if (nam != null)
 154       {
 155         j.setElement(nam);
 156         if (one2many.contains(nam))
 157         {
 158           // countOne2Many++;
 159           // if (Cache.isDebugEnabled())
 160           // Cache.debug("One 2 many relationship for
 161           // "+nam.getName());
 162         }
 163         else
 164         {
 165           one2many.addElement(nam);
 166           namesleft--;
 167         }
 168       }
 169       else
 170       {
 171         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
 172         j.setPlaceholder(true);
 173       }
 174     }
 175     // if (Cache.isDebugEnabled() && countOne2Many>0) {
 176     // Cache.debug("There were "+countOne2Many+" alignment
 177     // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
 178     // more leaves.");
 179     // }
 180     // one2many.clear();
 181   }
 182
 183   /**
 184    * Generate a string representation of the Tree
 185    *
 186    * @return Newick File with all tree data available
 187    */
 188   public String print()
 189   {
 190     NewickFile fout = new NewickFile(getTopNode());
 191
 192     return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
 193                                                                           // all
 194                                                                           // data
 195                                                                           // available
 196                                                                           // for
 197                                                                           // tree
 198   }
 199
 200   /**
 201    *
 202    * used when the alignment associated to a tree has changed.
 203    *
 204    * @param list
 205    *          Sequence set to be associated with tree nodes
 206    */
 207   public void updatePlaceHolders(List<SequenceI> list)
 208   {
 209     Vector<SequenceNode> leaves = findLeaves(top);
 210
 211     int sz = leaves.size();
 212     SequenceIdMatcher seqmatcher = null;
 213     int i = 0;
 214
 215     while (i < sz)
 216     {
 217       SequenceNode leaf = leaves.elementAt(i++);
 218
 219       if (list.contains(leaf.element()))
 220       {
 221         leaf.setPlaceholder(false);
 222       }
 223       else
 224       {
 225         if (seqmatcher == null)
 226         {
 227           // Only create this the first time we need it
 228           SequenceI[] seqs = new SequenceI[list.size()];
 229
 230           for (int j = 0; j < seqs.length; j++)
 231           {
 232             seqs[j] = list.get(j);
 233           }
 234
 235           seqmatcher = new SequenceIdMatcher(seqs);
 236         }
 237
 238         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
 239
 240         if (nam != null)
 241         {
 242           if (!leaf.isPlaceholder())
 243           {
 244             // remapping the node to a new sequenceI - should remove any refs to
 245             // old one.
 246             // TODO - make many sequenceI to one leaf mappings possible!
 247             // (JBPNote)
 248           }
 249           leaf.setPlaceholder(false);
 250           leaf.setElement(nam);
 251         }
 252         else
 253         {
 254           if (!leaf.isPlaceholder())
 255           {
 256             // Construct a new placeholder sequence object for this leaf
 257             leaf.setElement(
 258                     new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
 259           }
 260           leaf.setPlaceholder(true);
 261
 262         }
 263       }
 264     }
 265   }
 266
 267   /**
 268    * rename any nodes according to their associated sequence. This will modify
 269    * the tree's metadata! (ie the original NewickFile or newly generated
 270    * BinaryTree's label data)
 271    */
 272   public void renameAssociatedNodes()
 273   {
 274     applyToNodes(new NodeTransformI()
 275     {
 276
 277       @Override
 278       public void transform(BinaryNode nd)
 279       {
 280         Object el = nd.element();
 281         if (el != null && el instanceof SequenceI)
 282         {
 283           nd.setName(((SequenceI) el).getName());
 284         }
 285       }
 286     });
 287   }
 288
 289   /**
 290    * Search for leaf nodes below (or at) the given node
 291    *
 292    * @param nd
 293    *          root node to search from
 294    *
 295    * @return
 296    */
 297   public Vector<SequenceNode> findLeaves(SequenceNode nd)
 298   {
 299     Vector<SequenceNode> leaves = new Vector<SequenceNode>();
 300     findLeaves(nd, leaves);
 301     return leaves;
 302   }
 303
 304   /**
 305    * Search for leaf nodes.
 306    *
 307    * @param nd
 308    *          root node to search from
 309    * @param leaves
 310    *          Vector of leaves to add leaf node objects too.
 311    *
 312    * @return Vector of leaf nodes on binary tree
 313    */
 314   Vector<SequenceNode> findLeaves(SequenceNode nd,
 315           Vector<SequenceNode> leaves)
 316   {
 317     if (nd == null)
 318     {
 319       return leaves;
 320     }
 321
 322     if ((nd.left() == null) && (nd.right() == null)) // Interior node
 323     // detection
 324     {
 325       leaves.addElement(nd);
 326
 327       return leaves;
 328     }
 329     else
 330     {
 331       /*
 332        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
 333        * leaves.addElement(node); }
 334        */
 335       findLeaves((SequenceNode) nd.left(), leaves);
 336       findLeaves((SequenceNode) nd.right(), leaves);
 337     }
 338
 339     return leaves;
 340   }
 341
 342   /**
 343    * printNode is mainly for debugging purposes.
 344    *
 345    * @param nd
 346    *          SequenceNode
 347    */
 348   void printNode(SequenceNode nd)
 349   {
 350     if (nd == null)
 351     {
 352       return;
 353     }
 354
 355     if ((nd.left() == null) && (nd.right() == null))
 356     {
 357       System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
 358       System.out.println("Dist " + nd.dist);
 359       System.out.println("Boot " + nd.getBootstrap());
 360     }
 361     else
 362     {
 363       System.out.println("Dist " + nd.dist);
 364       printNode((SequenceNode) nd.left());
 365       printNode((SequenceNode) nd.right());
 366     }
 367   }
 368
 369   /**
 370    * DOCUMENT ME!
 371    *
 372    * @return DOCUMENT ME!
 373    */
 374   public double getMaxHeight()
 375   {
 376     return maxheight;
 377   }
 378
 379   /**
 380    * Makes a list of groups, where each group is represented by a node whose
 381    * height (distance from the root node), as a fraction of the height of the
 382    * whole tree, is greater than the given threshold. This corresponds to
 383    * selecting the nodes immediately to the right of a vertical line
 384    * partitioning the tree (if the tree is drawn with root to the left). Each
 385    * such node represents a group that contains all of the sequences linked to
 386    * the child leaf nodes.
 387    *
 388    * @param threshold
 389    * @see #getGroups()
 390    */
 391   public List<SequenceNode> groupNodes(float threshold)
 392   {
 393     List<SequenceNode> groups = new ArrayList<SequenceNode>();
 394     _groupNodes(groups, getTopNode(), threshold);
 395     return groups;
 396   }
 397
 398   protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
 399           float threshold)
 400   {
 401     if (nd == null)
 402     {
 403       return;
 404     }
 405
 406     if ((nd.height / maxheight) > threshold)
 407     {
 408       groups.add(nd);
 409     }
 410     else
 411     {
 412       _groupNodes(groups, (SequenceNode) nd.left(), threshold);
 413       _groupNodes(groups, (SequenceNode) nd.right(), threshold);
 414     }
 415   }
 416
 417   /**
 418    * DOCUMENT ME!
 419    *
 420    * @param nd
 421    *          DOCUMENT ME!
 422    *
 423    * @return DOCUMENT ME!
 424    */
 425   public double findHeight(SequenceNode nd)
 426   {
 427     if (nd == null)
 428     {
 429       return maxheight;
 430     }
 431
 432     if ((nd.left() == null) && (nd.right() == null))
 433     {
 434       nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
 435
 436       if (nd.height > maxheight)
 437       {
 438         return nd.height;
 439       }
 440       else
 441       {
 442         return maxheight;
 443       }
 444     }
 445     else
 446     {
 447       if (nd.parent() != null)
 448       {
 449         nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
 450       }
 451       else
 452       {
 453         maxheight = 0;
 454         nd.height = (float) 0.0;
 455       }
 456
 457       maxheight = findHeight((SequenceNode) (nd.left()));
 458       maxheight = findHeight((SequenceNode) (nd.right()));
 459     }
 460
 461     return maxheight;
 462   }
 463
 464   /**
 465    * DOCUMENT ME!
 466    *
 467    * @param nd
 468    *          DOCUMENT ME!
 469    */
 470   void printN(SequenceNode nd)
 471   {
 472     if (nd == null)
 473     {
 474       return;
 475     }
 476
 477     if ((nd.left() != null) && (nd.right() != null))
 478     {
 479       printN((SequenceNode) nd.left());
 480       printN((SequenceNode) nd.right());
 481     }
 482     else
 483     {
 484       System.out.println(" name = " + ((SequenceI) nd.element()).getName());
 485     }
 486
 487     System.out.println(
 488             " dist = " + nd.dist + " " + nd.count + " " + nd.height);
 489   }
 490
 491   /**
 492    * DOCUMENT ME!
 493    *
 494    * @param nd
 495    *          DOCUMENT ME!
 496    */
 497   public void reCount(SequenceNode nd)
 498   {
 499     ycount = 0;
 500     // _lycount = 0;
 501     // _lylimit = this.node.size();
 502     _reCount(nd);
 503   }
 504
 505   // private long _lycount = 0, _lylimit = 0;
 506
 507   /**
 508    * DOCUMENT ME!
 509    *
 510    * @param nd
 511    *          DOCUMENT ME!
 512    */
 513   void _reCount(SequenceNode nd)
 514   {
 515     // if (_lycount<_lylimit)
 516     // {
 517     // System.err.println("Warning: depth of _recount greater than number of
 518     // nodes.");
 519     // }
 520     if (nd == null)
 521     {
 522       return;
 523     }
 524     // _lycount++;
 525
 526     if ((nd.left() != null) && (nd.right() != null))
 527     {
 528
 529       _reCount((SequenceNode) nd.left());
 530       _reCount((SequenceNode) nd.right());
 531
 532       SequenceNode l = (SequenceNode) nd.left();
 533       SequenceNode r = (SequenceNode) nd.right();
 534
 535       nd.count = l.count + r.count;
 536       nd.ycount = (l.ycount + r.ycount) / 2;
 537     }
 538     else
 539     {
 540       nd.count = 1;
 541       nd.ycount = ycount++;
 542     }
 543     // _lycount--;
 544   }
 545
 546   /**
 547    * DOCUMENT ME!
 548    *
 549    * @param nd
 550    *          DOCUMENT ME!
 551    */
 552   public void swapNodes(SequenceNode nd)
 553   {
 554     if (nd == null)
 555     {
 556       return;
 557     }
 558
 559     SequenceNode tmp = (SequenceNode) nd.left();
 560
 561     nd.setLeft(nd.right());
 562     nd.setRight(tmp);
 563   }
 564
 565   /**
 566    * DOCUMENT ME!
 567    *
 568    * @param nd
 569    *          DOCUMENT ME!
 570    * @param dir
 571    *          DOCUMENT ME!
 572    */
 573   void changeDirection(SequenceNode nd, SequenceNode dir)
 574   {
 575     if (nd == null)
 576     {
 577       return;
 578     }
 579
 580     if (nd.parent() != top)
 581     {
 582       changeDirection((SequenceNode) nd.parent(), nd);
 583
 584       SequenceNode tmp = (SequenceNode) nd.parent();
 585
 586       if (dir == nd.left())
 587       {
 588         nd.setParent(dir);
 589         nd.setLeft(tmp);
 590       }
 591       else if (dir == nd.right())
 592       {
 593         nd.setParent(dir);
 594         nd.setRight(tmp);
 595       }
 596     }
 597     else
 598     {
 599       if (dir == nd.left())
 600       {
 601         nd.setParent(nd.left());
 602
 603         if (top.left() == nd)
 604         {
 605           nd.setRight(top.right());
 606         }
 607         else
 608         {
 609           nd.setRight(top.left());
 610         }
 611       }
 612       else
 613       {
 614         nd.setParent(nd.right());
 615
 616         if (top.left() == nd)
 617         {
 618           nd.setLeft(top.right());
 619         }
 620         else
 621         {
 622           nd.setLeft(top.left());
 623         }
 624       }
 625     }
 626   }
 627
 628   /**
 629    * DOCUMENT ME!
 630    *
 631    * @return DOCUMENT ME!
 632    */
 633   public SequenceNode getTopNode()
 634   {
 635     return top;
 636   }
 637
 638   /**
 639    *
 640    * @return true if tree has real distances
 641    */
 642   public boolean hasDistances()
 643   {
 644     return hasDistances;
 645   }
 646
 647   /**
 648    *
 649    * @return true if tree has real bootstrap values
 650    */
 651   public boolean hasBootstrap()
 652   {
 653     return hasBootstrap;
 654   }
 655
 656   public boolean hasRootDistance()
 657   {
 658     return hasRootDistance;
 659   }
 660
 661   /**
 662    * apply the given transform to all the nodes in the tree.
 663    *
 664    * @param nodeTransformI
 665    */
 666   public void applyToNodes(NodeTransformI nodeTransformI)
 667   {
 668     for (Enumeration<SequenceNode> nodes = node.elements(); nodes
 669             .hasMoreElements(); nodeTransformI
 670                     .transform(nodes.nextElement()))
 671     {
 672       ;
 673     }
 674   }
 675
 676   public AlignmentView getOriginalData()
 677   {
 678     return seqData;
 679   }
 680 }