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