forester/java/src/org/forester/phylogeny/PhylogenyMethods.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.phylogeny;
  27
  28 import java.awt.Color;
  29 import java.util.ArrayList;
  30 import java.util.Arrays;
  31 import java.util.HashSet;
  32 import java.util.Iterator;
  33 import java.util.List;
  34 import java.util.Set;
  35 import java.util.SortedMap;
  36 import java.util.TreeMap;
  37
  38 import org.forester.phylogeny.data.BranchColor;
  39 import org.forester.phylogeny.data.BranchWidth;
  40 import org.forester.phylogeny.data.Confidence;
  41 import org.forester.phylogeny.data.DomainArchitecture;
  42 import org.forester.phylogeny.data.Taxonomy;
  43 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  44 import org.forester.util.BasicDescriptiveStatistics;
  45 import org.forester.util.DescriptiveStatistics;
  46 import org.forester.util.FailedConditionCheckException;
  47 import org.forester.util.ForesterUtil;
  48
  49 public class PhylogenyMethods {
  50
  51     private static PhylogenyMethods _instance      = null;
  52     private final Set<Integer>      _temp_hash_set = new HashSet<Integer>();
  53     private PhylogenyNode           _farthest_1    = null;
  54     private PhylogenyNode           _farthest_2    = null;
  55
  56     private PhylogenyMethods() {
  57         // Hidden constructor.
  58     }
  59
  60     /**
  61      * Calculates the distance between PhylogenyNodes node1 and node2.
  62      *
  63      *
  64      * @param node1
  65      * @param node2
  66      * @return distance between node1 and node2
  67      */
  68     public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) {
  69         final PhylogenyNode lca = obtainLCA( node1, node2 );
  70         final PhylogenyNode n1 = node1;
  71         final PhylogenyNode n2 = node2;
  72         return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) );
  73     }
  74
  75     public double calculateFurthestDistance( final Phylogeny phylogeny ) {
  76         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
  77             return 0.0;
  78         }
  79         _farthest_1 = null;
  80         _farthest_2 = null;
  81         PhylogenyNode node_1 = null;
  82         PhylogenyNode node_2 = null;
  83         double farthest_d = -Double.MAX_VALUE;
  84         final PhylogenyMethods methods = PhylogenyMethods.getInstance();
  85         final List<PhylogenyNode> ext_nodes = phylogeny.getRoot().getAllExternalDescendants();
  86         for( int i = 1; i < ext_nodes.size(); ++i ) {
  87             for( int j = 0; j < i; ++j ) {
  88                 final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) );
  89                 if ( d < 0.0 ) {
  90                     throw new RuntimeException( "distance cannot be negative" );
  91                 }
  92                 if ( d > farthest_d ) {
  93                     farthest_d = d;
  94                     node_1 = ext_nodes.get( i );
  95                     node_2 = ext_nodes.get( j );
  96                 }
  97             }
  98         }
  99         _farthest_1 = node_1;
 100         _farthest_2 = node_2;
 101         return farthest_d;
 102     }
 103
 104     @Override
 105     public Object clone() throws CloneNotSupportedException {
 106         throw new CloneNotSupportedException();
 107     }
 108
 109     public PhylogenyNode getFarthestNode1() {
 110         return _farthest_1;
 111     }
 112
 113     public PhylogenyNode getFarthestNode2() {
 114         return _farthest_2;
 115     }
 116
 117     /**
 118      * Returns the LCA of PhylogenyNodes node1 and node2.
 119      *
 120      *
 121      * @param node1
 122      * @param node2
 123      * @return LCA of node1 and node2
 124      */
 125     public PhylogenyNode obtainLCA( final PhylogenyNode node1, final PhylogenyNode node2 ) {
 126         _temp_hash_set.clear();
 127         PhylogenyNode n1 = node1;
 128         PhylogenyNode n2 = node2;
 129         _temp_hash_set.add( n1.getId() );
 130         while ( !n1.isRoot() ) {
 131             n1 = n1.getParent();
 132             _temp_hash_set.add( n1.getId() );
 133         }
 134         while ( !_temp_hash_set.contains( n2.getId() ) && !n2.isRoot() ) {
 135             n2 = n2.getParent();
 136         }
 137         if ( !_temp_hash_set.contains( n2.getId() ) ) {
 138             throw new IllegalArgumentException( "attempt to get LCA of two nodes which do not share a common root" );
 139         }
 140         return n2;
 141     }
 142
 143     /**
 144      * Returns all orthologs of the external PhylogenyNode n of this Phylogeny.
 145      * Orthologs are returned as List of node references.
 146      * <p>
 147      * PRECONDITION: This tree must be binary and rooted, and speciation -
 148      * duplication need to be assigned for each of its internal Nodes.
 149      * <p>
 150      * Returns null if this Phylogeny is empty or if n is internal.
 151      * @param n
 152      *            external PhylogenyNode whose orthologs are to be returned
 153      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 154      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 155      *         internal
 156      */
 157     public List<PhylogenyNode> getOrthologousNodes( final Phylogeny phy, final PhylogenyNode node ) {
 158         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 159         final PhylogenyNodeIterator it = phy.iteratorExternalForward();
 160         while ( it.hasNext() ) {
 161             final PhylogenyNode temp_node = it.next();
 162             if ( ( temp_node != node ) && isAreOrthologous( node, temp_node ) ) {
 163                 nodes.add( temp_node );
 164             }
 165         }
 166         return nodes;
 167     }
 168
 169     public boolean isAreOrthologous( final PhylogenyNode node1, final PhylogenyNode node2 ) {
 170         return !obtainLCA( node1, node2 ).isDuplication();
 171     }
 172
 173     static double addPhylogenyDistances( final double a, final double b ) {
 174         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {
 175             return a + b;
 176         }
 177         else if ( a >= 0.0 ) {
 178             return a;
 179         }
 180         else if ( b >= 0.0 ) {
 181             return b;
 182         }
 183         return PhylogenyNode.DISTANCE_DEFAULT;
 184     }
 185
 186     // Helper for getUltraParalogousNodes( PhylogenyNode ).
 187     public static boolean areAllChildrenDuplications( final PhylogenyNode n ) {
 188         if ( n.isExternal() ) {
 189             return false;
 190         }
 191         else {
 192             if ( n.isDuplication() ) {
 193                 //FIXME test me!
 194                 for( final PhylogenyNode desc : n.getDescendants() ) {
 195                     if ( !areAllChildrenDuplications( desc ) ) {
 196                         return false;
 197                     }
 198                 }
 199                 return true;
 200             }
 201             else {
 202                 return false;
 203             }
 204         }
 205     }
 206
 207     public static int calculateDepth( final PhylogenyNode node ) {
 208         PhylogenyNode n = node;
 209         int steps = 0;
 210         while ( !n.isRoot() ) {
 211             steps++;
 212             n = n.getParent();
 213         }
 214         return steps;
 215     }
 216
 217     public static double calculateDistanceToRoot( final PhylogenyNode node ) {
 218         PhylogenyNode n = node;
 219         double d = 0.0;
 220         while ( !n.isRoot() ) {
 221             if ( n.getDistanceToParent() > 0.0 ) {
 222                 d += n.getDistanceToParent();
 223             }
 224             n = n.getParent();
 225         }
 226         return d;
 227     }
 228
 229     public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) {
 230         if ( node.isExternal() ) {
 231             return 0;
 232         }
 233         short max = 0;
 234         for( PhylogenyNode d : node.getAllExternalDescendants() ) {
 235             short steps = 0;
 236             while ( d != node ) {
 237                 if ( d.isCollapse() ) {
 238                     steps = 0;
 239                 }
 240                 else {
 241                     steps++;
 242                 }
 243                 d = d.getParent();
 244             }
 245             if ( max < steps ) {
 246                 max = steps;
 247             }
 248         }
 249         return max;
 250     }
 251
 252     public static int calculateMaxDepth( final Phylogeny phy ) {
 253         int max = 0;
 254         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 255             final PhylogenyNode node = iter.next();
 256             final int steps = calculateDepth( node );
 257             if ( steps > max ) {
 258                 max = steps;
 259             }
 260         }
 261         return max;
 262     }
 263
 264     public static double calculateMaxDistanceToRoot( final Phylogeny phy ) {
 265         double max = 0.0;
 266         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 267             final PhylogenyNode node = iter.next();
 268             final double d = calculateDistanceToRoot( node );
 269             if ( d > max ) {
 270                 max = d;
 271             }
 272         }
 273         return max;
 274     }
 275
 276     public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) {
 277         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 278         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 279             final PhylogenyNode n = iter.next();
 280             if ( !n.isExternal() ) {
 281                 stats.addValue( n.getNumberOfDescendants() );
 282             }
 283         }
 284         return stats;
 285     }
 286
 287     public static DescriptiveStatistics calculatConfidenceStatistics( final Phylogeny phy ) {
 288         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 289         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 290             final PhylogenyNode n = iter.next();
 291             if ( !n.isExternal() ) {
 292                 if ( n.getBranchData().isHasConfidences() ) {
 293                     stats.addValue( n.getBranchData().getConfidence( 0 ).getValue() );
 294                 }
 295             }
 296         }
 297         return stats;
 298     }
 299
 300     /**
 301      * Returns the set of distinct taxonomies of
 302      * all external nodes of node.
 303      * If at least one the external nodes has no taxonomy,
 304      * null is returned.
 305      *
 306      */
 307     public static Set<Taxonomy> obtainDistinctTaxonomies( final PhylogenyNode node ) {
 308         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 309         final Set<Taxonomy> tax_set = new HashSet<Taxonomy>();
 310         for( final PhylogenyNode n : descs ) {
 311             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 312                 return null;
 313             }
 314             tax_set.add( n.getNodeData().getTaxonomy() );
 315         }
 316         return tax_set;
 317     }
 318
 319     /**
 320      * Returns a map of distinct taxonomies of
 321      * all external nodes of node.
 322      * If at least one of the external nodes has no taxonomy,
 323      * null is returned.
 324      *
 325      */
 326     public static SortedMap<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 327         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 328         final SortedMap<Taxonomy, Integer> tax_map = new TreeMap<Taxonomy, Integer>();
 329         for( final PhylogenyNode n : descs ) {
 330             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 331                 return null;
 332             }
 333             final Taxonomy t = n.getNodeData().getTaxonomy();
 334             if ( tax_map.containsKey( t ) ) {
 335                 tax_map.put( t, tax_map.get( t ) + 1 );
 336             }
 337             else {
 338                 tax_map.put( t, 1 );
 339             }
 340         }
 341         return tax_map;
 342     }
 343
 344     public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) {
 345         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 346         int x = 0;
 347         for( final PhylogenyNode n : descs ) {
 348             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 349                 x++;
 350             }
 351         }
 352         return x;
 353     }
 354
 355     /**
 356      * Deep copies the phylogeny originating from this node.
 357      */
 358     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
 359         if ( source == null ) {
 360             return null;
 361         }
 362         else {
 363             final PhylogenyNode newnode = source.copyNodeData();
 364             if ( !source.isExternal() ) {
 365                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 366                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
 367                 }
 368             }
 369             return newnode;
 370         }
 371     }
 372
 373     /**
 374      * Shallow copies the phylogeny originating from this node.
 375      */
 376     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
 377         if ( source == null ) {
 378             return null;
 379         }
 380         else {
 381             final PhylogenyNode newnode = source.copyNodeDataShallow();
 382             if ( !source.isExternal() ) {
 383                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 384                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
 385                 }
 386             }
 387             return newnode;
 388         }
 389     }
 390
 391     public static void deleteExternalNodesNegativeSelection( final Set<Integer> to_delete, final Phylogeny phy ) {
 392         phy.hashIDs();
 393         for( final Integer id : to_delete ) {
 394             phy.deleteSubtree( phy.getNode( id ), true );
 395         }
 396         phy.hashIDs();
 397     }
 398
 399     public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p )
 400             throws IllegalArgumentException {
 401         for( int i = 0; i < node_names_to_delete.length; ++i ) {
 402             if ( ForesterUtil.isEmpty( node_names_to_delete[ i ] ) ) {
 403                 continue;
 404             }
 405             List<PhylogenyNode> nodes = null;
 406             nodes = p.getNodes( node_names_to_delete[ i ] );
 407             final Iterator<PhylogenyNode> it = nodes.iterator();
 408             while ( it.hasNext() ) {
 409                 final PhylogenyNode n = it.next();
 410                 if ( !n.isExternal() ) {
 411                     throw new IllegalArgumentException( "attempt to delete non-external node \""
 412                             + node_names_to_delete[ i ] + "\"" );
 413                 }
 414                 p.deleteSubtree( n, true );
 415             }
 416         }
 417     }
 418
 419     public static void deleteExternalNodesPositiveSelection( final Set<Taxonomy> species_to_keep, final Phylogeny phy ) {
 420         //   final Set<Integer> to_delete = new HashSet<Integer>();
 421         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 422             final PhylogenyNode n = it.next();
 423             if ( n.getNodeData().isHasTaxonomy() ) {
 424                 if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) {
 425                     //to_delete.add( n.getNodeId() );
 426                     phy.deleteSubtree( n, true );
 427                 }
 428             }
 429             else {
 430                 throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" );
 431             }
 432         }
 433         phy.hashIDs();
 434         phy.externalNodesHaveChanged();
 435         //  deleteExternalNodesNegativeSelection( to_delete, phy );
 436     }
 437
 438     public static List<String> deleteExternalNodesPositiveSelection( final String[] node_names_to_keep,
 439                                                                      final Phylogeny p ) {
 440         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 441         final String[] to_delete = new String[ p.getNumberOfExternalNodes() ];
 442         int i = 0;
 443         Arrays.sort( node_names_to_keep );
 444         while ( it.hasNext() ) {
 445             final String curent_name = it.next().getName();
 446             if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) {
 447                 to_delete[ i++ ] = curent_name;
 448             }
 449         }
 450         PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p );
 451         final List<String> deleted = new ArrayList<String>();
 452         for( final String n : to_delete ) {
 453             if ( !ForesterUtil.isEmpty( n ) ) {
 454                 deleted.add( n );
 455             }
 456         }
 457         return deleted;
 458     }
 459
 460     public static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 461         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 462         final Set<Integer> encountered = new HashSet<Integer>();
 463         if ( !node.isExternal() ) {
 464             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 465             for( PhylogenyNode current : exts ) {
 466                 descs.add( current );
 467                 while ( current != node ) {
 468                     current = current.getParent();
 469                     if ( encountered.contains( current.getId() ) ) {
 470                         continue;
 471                     }
 472                     descs.add( current );
 473                     encountered.add( current.getId() );
 474                 }
 475             }
 476         }
 477         return descs;
 478     }
 479
 480     /**
 481      *
 482      * Convenience method
 483      *
 484      * @param node
 485      * @return
 486      */
 487     public static Color getBranchColorValue( final PhylogenyNode node ) {
 488         if ( node.getBranchData().getBranchColor() == null ) {
 489             return null;
 490         }
 491         return node.getBranchData().getBranchColor().getValue();
 492     }
 493
 494     /**
 495      * Convenience method
 496      */
 497     public static double getBranchWidthValue( final PhylogenyNode node ) {
 498         if ( !node.getBranchData().isHasBranchWidth() ) {
 499             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 500         }
 501         return node.getBranchData().getBranchWidth().getValue();
 502     }
 503
 504     /**
 505      * Convenience method
 506      */
 507     public static double getConfidenceValue( final PhylogenyNode node ) {
 508         if ( !node.getBranchData().isHasConfidences() ) {
 509             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 510         }
 511         return node.getBranchData().getConfidence( 0 ).getValue();
 512     }
 513
 514     /**
 515      * Convenience method
 516      */
 517     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 518         if ( !node.getBranchData().isHasConfidences() ) {
 519             return new double[ 0 ];
 520         }
 521         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 522         int i = 0;
 523         for( final Confidence c : node.getBranchData().getConfidences() ) {
 524             values[ i++ ] = c.getValue();
 525         }
 526         return values;
 527     }
 528
 529     /**
 530      * Calculates the distance between PhylogenyNodes n1 and n2.
 531      * PRECONDITION: n1 is a descendant of n2.
 532      *
 533      * @param n1
 534      *            a descendant of n2
 535      * @param n2
 536      * @return distance between n1 and n2
 537      */
 538     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
 539         double d = 0.0;
 540         while ( n1 != n2 ) {
 541             if ( n1.getDistanceToParent() > 0.0 ) {
 542                 d += n1.getDistanceToParent();
 543             }
 544             n1 = n1.getParent();
 545         }
 546         return d;
 547     }
 548
 549     /**
 550      * Returns taxonomy t if all external descendants have
 551      * the same taxonomy t, null otherwise.
 552      *
 553      */
 554     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 555         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 556         Taxonomy tax = null;
 557         for( final PhylogenyNode n : descs ) {
 558             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 559                 return null;
 560             }
 561             else if ( tax == null ) {
 562                 tax = n.getNodeData().getTaxonomy();
 563             }
 564             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 565                 return null;
 566             }
 567         }
 568         return tax;
 569     }
 570
 571     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 572         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 573         PhylogenyNode farthest = null;
 574         double longest = -Double.MAX_VALUE;
 575         for( final PhylogenyNode child : children ) {
 576             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 577                 farthest = child;
 578                 longest = PhylogenyMethods.getDistance( child, node );
 579             }
 580         }
 581         return farthest;
 582     }
 583
 584     public static PhylogenyMethods getInstance() {
 585         if ( PhylogenyMethods._instance == null ) {
 586             PhylogenyMethods._instance = new PhylogenyMethods();
 587         }
 588         return PhylogenyMethods._instance;
 589     }
 590
 591     /**
 592      * Returns the largest confidence value found on phy.
 593      */
 594     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 595         double max = -Double.MAX_VALUE;
 596         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 597             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 598             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 599                 max = s;
 600             }
 601         }
 602         return max;
 603     }
 604
 605     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 606         int min = Integer.MAX_VALUE;
 607         int d = 0;
 608         PhylogenyNode n;
 609         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 610             n = it.next();
 611             if ( n.isInternal() ) {
 612                 d = n.getNumberOfDescendants();
 613                 if ( d < min ) {
 614                     min = d;
 615                 }
 616             }
 617         }
 618         return min;
 619     }
 620
 621     /**
 622      * Convenience method for display purposes.
 623      * Not intended for algorithms.
 624      */
 625     public static String getSpecies( final PhylogenyNode node ) {
 626         if ( !node.getNodeData().isHasTaxonomy() ) {
 627             return "";
 628         }
 629         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 630             return node.getNodeData().getTaxonomy().getTaxonomyCode();
 631         }
 632         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
 633             return node.getNodeData().getTaxonomy().getScientificName();
 634         }
 635         else {
 636             return node.getNodeData().getTaxonomy().getCommonName();
 637         }
 638     }
 639
 640     /**
 641      * Returns all Nodes which are connected to external PhylogenyNode n of this
 642      * Phylogeny by a path containing only speciation events. We call these
 643      * "super orthologs". Nodes are returned as Vector of references to Nodes.
 644      * <p>
 645      * PRECONDITION: This tree must be binary and rooted, and speciation -
 646      * duplication need to be assigned for each of its internal Nodes.
 647      * <p>
 648      * Returns null if this Phylogeny is empty or if n is internal.
 649      * @param n
 650      *            external PhylogenyNode whose strictly speciation related Nodes
 651      *            are to be returned
 652      * @return Vector of references to all strictly speciation related Nodes of
 653      *         PhylogenyNode n of this Phylogeny, null if this Phylogeny is
 654      *         empty or if n is internal
 655      */
 656     public static List<PhylogenyNode> getSuperOrthologousNodes( final PhylogenyNode n ) {
 657         // FIXME
 658         PhylogenyNode node = n, deepest = null;
 659         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
 660         if ( !node.isExternal() ) {
 661             return null;
 662         }
 663         while ( !node.isRoot() && !node.getParent().isDuplication() ) {
 664             node = node.getParent();
 665         }
 666         deepest = node;
 667         deepest.setIndicatorsToZero();
 668         do {
 669             if ( !node.isExternal() ) {
 670                 if ( node.getIndicator() == 0 ) {
 671                     node.setIndicator( ( byte ) 1 );
 672                     if ( !node.isDuplication() ) {
 673                         node = node.getChildNode1();
 674                     }
 675                 }
 676                 if ( node.getIndicator() == 1 ) {
 677                     node.setIndicator( ( byte ) 2 );
 678                     if ( !node.isDuplication() ) {
 679                         node = node.getChildNode2();
 680                     }
 681                 }
 682                 if ( ( node != deepest ) && ( node.getIndicator() == 2 ) ) {
 683                     node = node.getParent();
 684                 }
 685             }
 686             else {
 687                 if ( node != n ) {
 688                     v.add( node );
 689                 }
 690                 if ( node != deepest ) {
 691                     node = node.getParent();
 692                 }
 693                 else {
 694                     node.setIndicator( ( byte ) 2 );
 695                 }
 696             }
 697         } while ( ( node != deepest ) || ( deepest.getIndicator() != 2 ) );
 698         return v;
 699     }
 700
 701     /**
 702      * Convenience method for display purposes.
 703      * Not intended for algorithms.
 704      */
 705     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
 706         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
 707             return "";
 708         }
 709         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
 710     }
 711
 712     /**
 713      * Returns all Nodes which are connected to external PhylogenyNode n of this
 714      * Phylogeny by a path containing, and leading to, only duplication events.
 715      * We call these "ultra paralogs". Nodes are returned as Vector of
 716      * references to Nodes.
 717      * <p>
 718      * PRECONDITION: This tree must be binary and rooted, and speciation -
 719      * duplication need to be assigned for each of its internal Nodes.
 720      * <p>
 721      * Returns null if this Phylogeny is empty or if n is internal.
 722      * <p>
 723      * (Last modified: 10/06/01)
 724      *
 725      * @param n
 726      *            external PhylogenyNode whose ultra paralogs are to be returned
 727      * @return Vector of references to all ultra paralogs of PhylogenyNode n of
 728      *         this Phylogeny, null if this Phylogeny is empty or if n is
 729      *         internal
 730      */
 731     public static List<PhylogenyNode> getUltraParalogousNodes( final PhylogenyNode n ) {
 732         // FIXME test me
 733         PhylogenyNode node = n;
 734         if ( !node.isExternal() ) {
 735             return null;
 736         }
 737         while ( !node.isRoot() && node.getParent().isDuplication() && areAllChildrenDuplications( node.getParent() ) ) {
 738             node = node.getParent();
 739         }
 740         final List<PhylogenyNode> nodes = node.getAllExternalDescendants();
 741         nodes.remove( n );
 742         return nodes;
 743     }
 744
 745     public static String inferCommonPartOfScientificNameOfDescendants( final PhylogenyNode node ) {
 746         final List<PhylogenyNode> descs = node.getDescendants();
 747         String sn = null;
 748         for( final PhylogenyNode n : descs ) {
 749             if ( !n.getNodeData().isHasTaxonomy()
 750                     || ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
 751                 return null;
 752             }
 753             else if ( sn == null ) {
 754                 sn = n.getNodeData().getTaxonomy().getScientificName().trim();
 755             }
 756             else {
 757                 String sn_current = n.getNodeData().getTaxonomy().getScientificName().trim();
 758                 if ( !sn.equals( sn_current ) ) {
 759                     boolean overlap = false;
 760                     while ( ( sn.indexOf( ' ' ) >= 0 ) || ( sn_current.indexOf( ' ' ) >= 0 ) ) {
 761                         if ( ForesterUtil.countChars( sn, ' ' ) > ForesterUtil.countChars( sn_current, ' ' ) ) {
 762                             sn = sn.substring( 0, sn.lastIndexOf( ' ' ) ).trim();
 763                         }
 764                         else {
 765                             sn_current = sn_current.substring( 0, sn_current.lastIndexOf( ' ' ) ).trim();
 766                         }
 767                         if ( sn.equals( sn_current ) ) {
 768                             overlap = true;
 769                             break;
 770                         }
 771                     }
 772                     if ( !overlap ) {
 773                         return null;
 774                     }
 775                 }
 776             }
 777         }
 778         return sn;
 779     }
 780
 781     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
 782         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 783             if ( node.getChildNode( i ).isExternal() ) {
 784                 return true;
 785             }
 786         }
 787         return false;
 788     }
 789
 790     /*
 791      * This is case insensitive.
 792      *
 793      */
 794     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
 795                                                                                final String[] providers ) {
 796         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
 797             final String my_tax_prov = tax.getIdentifier().getProvider();
 798             for( final String provider : providers ) {
 799                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
 800                     return true;
 801                 }
 802             }
 803             return false;
 804         }
 805         else {
 806             return false;
 807         }
 808     }
 809
 810     private static boolean match( final String s,
 811                                   final String query,
 812                                   final boolean case_sensitive,
 813                                   final boolean partial ) {
 814         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
 815             return false;
 816         }
 817         String my_s = s.trim();
 818         String my_query = query.trim();
 819         if ( !case_sensitive ) {
 820             my_s = my_s.toLowerCase();
 821             my_query = my_query.toLowerCase();
 822         }
 823         if ( partial ) {
 824             return my_s.indexOf( my_query ) >= 0;
 825         }
 826         else {
 827             return my_s.equals( my_query );
 828         }
 829     }
 830
 831     public static void midpointRoot( final Phylogeny phylogeny ) {
 832         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
 833             return;
 834         }
 835         final PhylogenyMethods methods = getInstance();
 836         final double farthest_d = methods.calculateFurthestDistance( phylogeny );
 837         final PhylogenyNode f1 = methods.getFarthestNode1();
 838         final PhylogenyNode f2 = methods.getFarthestNode2();
 839         if ( farthest_d <= 0.0 ) {
 840             return;
 841         }
 842         double x = farthest_d / 2.0;
 843         PhylogenyNode n = f1;
 844         if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny
 845                 .getRoot() ) ) {
 846             n = f2;
 847         }
 848         while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) {
 849             x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
 850             n = n.getParent();
 851         }
 852         phylogeny.reRoot( n, x );
 853         phylogeny.recalculateNumberOfExternalDescendants( true );
 854         final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() );
 855         final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() );
 856         final double da = getDistance( a, phylogeny.getRoot() );
 857         final double db = getDistance( b, phylogeny.getRoot() );
 858         if ( Math.abs( da - db ) > 0.000001 ) {
 859             throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed:  da="
 860                     + da + ",  db=" + db + ",  diff=" + Math.abs( da - db ) );
 861         }
 862     }
 863
 864     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
 865                                                  final double max_bootstrap_value,
 866                                                  final double max_normalized_value ) {
 867         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
 868             final PhylogenyNode node = iter.next();
 869             if ( node.isInternal() ) {
 870                 final double confidence = getConfidenceValue( node );
 871                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 872                     if ( confidence >= max_bootstrap_value ) {
 873                         setBootstrapConfidence( node, max_normalized_value );
 874                     }
 875                     else {
 876                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
 877                     }
 878                 }
 879             }
 880         }
 881     }
 882
 883     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
 884         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 885         if ( phy.isEmpty() ) {
 886             return nodes;
 887         }
 888         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 889             nodes.add( iter.next() );
 890         }
 891         return nodes;
 892     }
 893
 894     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
 895         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
 896             final PhylogenyNode node = iter.next();
 897             double red = 0.0;
 898             double green = 0.0;
 899             double blue = 0.0;
 900             int n = 0;
 901             if ( node.isInternal() ) {
 902                 for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
 903                     final PhylogenyNode child_node = iterator.next();
 904                     final Color child_color = getBranchColorValue( child_node );
 905                     if ( child_color != null ) {
 906                         ++n;
 907                         red += child_color.getRed();
 908                         green += child_color.getGreen();
 909                         blue += child_color.getBlue();
 910                     }
 911                 }
 912                 setBranchColorValue( node,
 913                                      new Color( ForesterUtil.roundToInt( red / n ),
 914                                                 ForesterUtil.roundToInt( green / n ),
 915                                                 ForesterUtil.roundToInt( blue / n ) ) );
 916             }
 917         }
 918     }
 919
 920     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
 921         if ( remove_me.isRoot() ) {
 922             throw new IllegalArgumentException( "ill advised attempt to remove root node" );
 923         }
 924         if ( remove_me.isExternal() ) {
 925             phylogeny.deleteSubtree( remove_me, false );
 926         }
 927         else {
 928             final PhylogenyNode parent = remove_me.getParent();
 929             final List<PhylogenyNode> descs = remove_me.getDescendants();
 930             parent.removeChildNode( remove_me );
 931             for( final PhylogenyNode desc : descs ) {
 932                 parent.addAsChild( desc );
 933                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
 934                                                                  desc.getDistanceToParent() ) );
 935             }
 936             remove_me.setParent( null );
 937             phylogeny.setIdHash( null );
 938             phylogeny.externalNodesHaveChanged();
 939         }
 940     }
 941
 942     public static List<PhylogenyNode> searchData( final String query,
 943                                                   final Phylogeny phy,
 944                                                   final boolean case_sensitive,
 945                                                   final boolean partial ) {
 946         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 947         if ( phy.isEmpty() || ( query == null ) ) {
 948             return nodes;
 949         }
 950         if ( ForesterUtil.isEmpty( query ) ) {
 951             return nodes;
 952         }
 953         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 954             final PhylogenyNode node = iter.next();
 955             boolean match = false;
 956             if ( match( node.getName(), query, case_sensitive, partial ) ) {
 957                 match = true;
 958             }
 959             else if ( node.getNodeData().isHasTaxonomy()
 960                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 961                 match = true;
 962             }
 963             else if ( node.getNodeData().isHasTaxonomy()
 964                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
 965                 match = true;
 966             }
 967             else if ( node.getNodeData().isHasTaxonomy()
 968                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
 969                 match = true;
 970             }
 971             else if ( node.getNodeData().isHasTaxonomy()
 972                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
 973                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
 974                               query,
 975                               case_sensitive,
 976                               partial ) ) {
 977                 match = true;
 978             }
 979             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
 980                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
 981                 I: for( final String syn : syns ) {
 982                     if ( match( syn, query, case_sensitive, partial ) ) {
 983                         match = true;
 984                         break I;
 985                     }
 986                 }
 987             }
 988             if ( !match && node.getNodeData().isHasSequence()
 989                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
 990                 match = true;
 991             }
 992             if ( !match && node.getNodeData().isHasSequence()
 993                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
 994                 match = true;
 995             }
 996             if ( !match
 997                     && node.getNodeData().isHasSequence()
 998                     && ( node.getNodeData().getSequence().getAccession() != null )
 999                     && match( node.getNodeData().getSequence().getAccession().getValue(),
1000                               query,
1001                               case_sensitive,
1002                               partial ) ) {
1003                 match = true;
1004             }
1005             if ( !match && node.getNodeData().isHasSequence()
1006                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1007                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1008                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1009                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1010                         match = true;
1011                         break I;
1012                     }
1013                 }
1014             }
1015             if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1016                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1017                 I: while ( it.hasNext() ) {
1018                     if ( match( it.next(), query, case_sensitive, partial ) ) {
1019                         match = true;
1020                         break I;
1021                     }
1022                 }
1023                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1024                 I: while ( it.hasNext() ) {
1025                     if ( match( it.next(), query, case_sensitive, partial ) ) {
1026                         match = true;
1027                         break I;
1028                     }
1029                 }
1030             }
1031             if ( match ) {
1032                 nodes.add( node );
1033             }
1034         }
1035         return nodes;
1036     }
1037
1038     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
1039                                                             final Phylogeny phy,
1040                                                             final boolean case_sensitive,
1041                                                             final boolean partial ) {
1042         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1043         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
1044             return nodes;
1045         }
1046         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1047             final PhylogenyNode node = iter.next();
1048             boolean all_matched = true;
1049             for( final String query : queries ) {
1050                 boolean match = false;
1051                 if ( ForesterUtil.isEmpty( query ) ) {
1052                     continue;
1053                 }
1054                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
1055                     match = true;
1056                 }
1057                 else if ( node.getNodeData().isHasTaxonomy()
1058                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1059                     match = true;
1060                 }
1061                 else if ( node.getNodeData().isHasTaxonomy()
1062                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1063                     match = true;
1064                 }
1065                 else if ( node.getNodeData().isHasTaxonomy()
1066                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1067                     match = true;
1068                 }
1069                 else if ( node.getNodeData().isHasTaxonomy()
1070                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1071                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1072                                   query,
1073                                   case_sensitive,
1074                                   partial ) ) {
1075                     match = true;
1076                 }
1077                 else if ( node.getNodeData().isHasTaxonomy()
1078                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1079                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1080                     I: for( final String syn : syns ) {
1081                         if ( match( syn, query, case_sensitive, partial ) ) {
1082                             match = true;
1083                             break I;
1084                         }
1085                     }
1086                 }
1087                 if ( !match && node.getNodeData().isHasSequence()
1088                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1089                     match = true;
1090                 }
1091                 if ( !match && node.getNodeData().isHasSequence()
1092                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1093                     match = true;
1094                 }
1095                 if ( !match
1096                         && node.getNodeData().isHasSequence()
1097                         && ( node.getNodeData().getSequence().getAccession() != null )
1098                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1099                                   query,
1100                                   case_sensitive,
1101                                   partial ) ) {
1102                     match = true;
1103                 }
1104                 if ( !match && node.getNodeData().isHasSequence()
1105                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1106                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1107                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1108                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1109                             match = true;
1110                             break I;
1111                         }
1112                     }
1113                 }
1114                 if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1115                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1116                     I: while ( it.hasNext() ) {
1117                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1118                             match = true;
1119                             break I;
1120                         }
1121                     }
1122                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1123                     I: while ( it.hasNext() ) {
1124                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1125                             match = true;
1126                             break I;
1127                         }
1128                     }
1129                     //                    final String[] bcp_ary = node.getNodeData().getBinaryCharacters()
1130                     //                            .getPresentCharactersAsStringArray();
1131                     //                    I: for( final String bc : bcp_ary ) {
1132                     //                        if ( match( bc, query, case_sensitive, partial ) ) {
1133                     //                            match = true;
1134                     //                            break I;
1135                     //                        }
1136                     //                    }
1137                     //                    final String[] bcg_ary = node.getNodeData().getBinaryCharacters()
1138                     //                            .getGainedCharactersAsStringArray();
1139                     //                    I: for( final String bc : bcg_ary ) {
1140                     //                        if ( match( bc, query, case_sensitive, partial ) ) {
1141                     //                            match = true;
1142                     //                            break I;
1143                     //                        }
1144                     //                    }
1145                 }
1146                 if ( !match ) {
1147                     all_matched = false;
1148                     break;
1149                 }
1150             }
1151             if ( all_matched ) {
1152                 nodes.add( node );
1153             }
1154         }
1155         return nodes;
1156     }
1157
1158     /**
1159      * Convenience method.
1160      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1161      */
1162     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1163         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1164     }
1165
1166     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1167         if ( node.getBranchData().getBranchColor() == null ) {
1168             node.getBranchData().setBranchColor( new BranchColor() );
1169         }
1170         node.getBranchData().getBranchColor().setValue( color );
1171     }
1172
1173     /**
1174      * Convenience method
1175      */
1176     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1177         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1178     }
1179
1180     /**
1181      * Convenience method.
1182      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1183      */
1184     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1185         setConfidence( node, confidence_value, "" );
1186     }
1187
1188     /**
1189      * Convenience method.
1190      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1191      */
1192     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1193         Confidence c = null;
1194         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1195             c = node.getBranchData().getConfidence( 0 );
1196         }
1197         else {
1198             c = new Confidence();
1199             node.getBranchData().addConfidence( c );
1200         }
1201         c.setType( type );
1202         c.setValue( confidence_value );
1203     }
1204
1205     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1206         if ( !node.getNodeData().isHasTaxonomy() ) {
1207             node.getNodeData().setTaxonomy( new Taxonomy() );
1208         }
1209         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1210     }
1211
1212     /**
1213      * Convenience method to set the taxonomy code of a phylogeny node.
1214      *
1215      *
1216      * @param node
1217      * @param taxonomy_code
1218      */
1219     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code ) {
1220         if ( !node.getNodeData().isHasTaxonomy() ) {
1221             node.getNodeData().setTaxonomy( new Taxonomy() );
1222         }
1223         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1224     }
1225
1226     /**
1227      * Removes from Phylogeny to_be_stripped all external Nodes which are
1228      * associated with a species NOT found in Phylogeny reference.
1229      *
1230      * @param reference
1231      *            a reference Phylogeny
1232      * @param to_be_stripped
1233      *            Phylogeny to be stripped
1234      * @return number of external nodes removed from to_be_stripped
1235      */
1236     public static int taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference, final Phylogeny to_be_stripped ) {
1237         final Set<String> ref_ext_taxo = new HashSet<String>();
1238         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1239         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1240             ref_ext_taxo.add( getSpecies( it.next() ) );
1241         }
1242         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1243             final PhylogenyNode n = it.next();
1244             if ( !ref_ext_taxo.contains( getSpecies( n ) ) ) {
1245                 nodes_to_delete.add( n );
1246             }
1247         }
1248         for( final PhylogenyNode phylogenyNode : nodes_to_delete ) {
1249             to_be_stripped.deleteSubtree( phylogenyNode, true );
1250         }
1251         return nodes_to_delete.size();
1252     }
1253 }