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