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