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.io.File;
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collections;
  34 import java.util.Comparator;
  35 import java.util.HashMap;
  36 import java.util.HashSet;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.Set;
  40 import java.util.SortedMap;
  41 import java.util.TreeMap;
  42
  43 import org.forester.io.parsers.PhylogenyParser;
  44 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  45 import org.forester.io.parsers.phyloxml.PhyloXmlUtil;
  46 import org.forester.io.parsers.util.PhylogenyParserException;
  47 import org.forester.phylogeny.data.BranchColor;
  48 import org.forester.phylogeny.data.BranchWidth;
  49 import org.forester.phylogeny.data.Confidence;
  50 import org.forester.phylogeny.data.DomainArchitecture;
  51 import org.forester.phylogeny.data.Event;
  52 import org.forester.phylogeny.data.Identifier;
  53 import org.forester.phylogeny.data.PhylogenyDataUtil;
  54 import org.forester.phylogeny.data.Sequence;
  55 import org.forester.phylogeny.data.Taxonomy;
  56 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  57 import org.forester.phylogeny.factories.PhylogenyFactory;
  58 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  59 import org.forester.util.BasicDescriptiveStatistics;
  60 import org.forester.util.DescriptiveStatistics;
  61 import org.forester.util.FailedConditionCheckException;
  62 import org.forester.util.ForesterUtil;
  63
  64 public class PhylogenyMethods {
  65
  66     private static PhylogenyMethods _instance   = null;
  67     private PhylogenyNode           _farthest_1 = null;
  68     private PhylogenyNode           _farthest_2 = null;
  69
  70     private PhylogenyMethods() {
  71         // Hidden constructor.
  72     }
  73
  74     /**
  75      * Calculates the distance between PhylogenyNodes node1 and node2.
  76      *
  77      *
  78      * @param node1
  79      * @param node2
  80      * @return distance between node1 and node2
  81      */
  82     public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) {
  83         final PhylogenyNode lca = calculateLCA( node1, node2 );
  84         final PhylogenyNode n1 = node1;
  85         final PhylogenyNode n2 = node2;
  86         return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) );
  87     }
  88
  89     public double calculateFurthestDistance( final Phylogeny phylogeny ) {
  90         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
  91             return 0.0;
  92         }
  93         _farthest_1 = null;
  94         _farthest_2 = null;
  95         PhylogenyNode node_1 = null;
  96         PhylogenyNode node_2 = null;
  97         double farthest_d = -Double.MAX_VALUE;
  98         final PhylogenyMethods methods = PhylogenyMethods.getInstance();
  99         final List<PhylogenyNode> ext_nodes = phylogeny.getRoot().getAllExternalDescendants();
 100         for( int i = 1; i < ext_nodes.size(); ++i ) {
 101             for( int j = 0; j < i; ++j ) {
 102                 final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) );
 103                 if ( d < 0.0 ) {
 104                     throw new RuntimeException( "distance cannot be negative" );
 105                 }
 106                 if ( d > farthest_d ) {
 107                     farthest_d = d;
 108                     node_1 = ext_nodes.get( i );
 109                     node_2 = ext_nodes.get( j );
 110                 }
 111             }
 112         }
 113         _farthest_1 = node_1;
 114         _farthest_2 = node_2;
 115         return farthest_d;
 116     }
 117
 118     @Override
 119     public Object clone() throws CloneNotSupportedException {
 120         throw new CloneNotSupportedException();
 121     }
 122
 123     public PhylogenyNode getFarthestNode1() {
 124         return _farthest_1;
 125     }
 126
 127     public PhylogenyNode getFarthestNode2() {
 128         return _farthest_2;
 129     }
 130
 131     public static DescriptiveStatistics calculatBranchLengthStatistics( final Phylogeny phy ) {
 132         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 133         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 134             final PhylogenyNode n = iter.next();
 135             if ( !n.isRoot() && ( n.getDistanceToParent() >= 0.0 ) ) {
 136                 stats.addValue( n.getDistanceToParent() );
 137             }
 138         }
 139         return stats;
 140     }
 141
 142     public static List<DescriptiveStatistics> calculatConfidenceStatistics( final Phylogeny phy ) {
 143         final List<DescriptiveStatistics> stats = new ArrayList<DescriptiveStatistics>();
 144         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 145             final PhylogenyNode n = iter.next();
 146             if ( !n.isExternal() && !n.isRoot() ) {
 147                 if ( n.getBranchData().isHasConfidences() ) {
 148                     for( int i = 0; i < n.getBranchData().getConfidences().size(); ++i ) {
 149                         final Confidence c = n.getBranchData().getConfidences().get( i );
 150                         if ( ( i > ( stats.size() - 1 ) ) || ( stats.get( i ) == null ) ) {
 151                             stats.add( i, new BasicDescriptiveStatistics() );
 152                         }
 153                         if ( !ForesterUtil.isEmpty( c.getType() ) ) {
 154                             if ( !ForesterUtil.isEmpty( stats.get( i ).getDescription() ) ) {
 155                                 if ( !stats.get( i ).getDescription().equalsIgnoreCase( c.getType() ) ) {
 156                                     throw new IllegalArgumentException( "support values in node [" + n.toString()
 157                                             + "] appear inconsistently ordered" );
 158                                 }
 159                             }
 160                             stats.get( i ).setDescription( c.getType() );
 161                         }
 162                         stats.get( i ).addValue( ( ( c != null ) && ( c.getValue() >= 0 ) ) ? c.getValue() : 0 );
 163                     }
 164                 }
 165             }
 166         }
 167         return stats;
 168     }
 169
 170     /**
 171      * Returns the LCA of PhylogenyNodes node1 and node2.
 172      *
 173      *
 174      * @param node1
 175      * @param node2
 176      * @return LCA of node1 and node2
 177      */
 178     public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) {
 179         if ( node1 == null ) {
 180             throw new IllegalArgumentException( "first argument (node) is null" );
 181         }
 182         if ( node2 == null ) {
 183             throw new IllegalArgumentException( "second argument (node) is null" );
 184         }
 185         if ( node1 == node2 ) {
 186             return node1;
 187         }
 188         if ( ( node1.getParent() == node2.getParent() ) ) {
 189             return node1.getParent();
 190         }
 191         int depth1 = node1.calculateDepth();
 192         int depth2 = node2.calculateDepth();
 193         while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) {
 194             if ( depth1 > depth2 ) {
 195                 node1 = node1.getParent();
 196                 depth1--;
 197             }
 198             else if ( depth2 > depth1 ) {
 199                 node2 = node2.getParent();
 200                 depth2--;
 201             }
 202             else {
 203                 if ( node1 == node2 ) {
 204                     return node1;
 205                 }
 206                 node1 = node1.getParent();
 207                 node2 = node2.getParent();
 208                 depth1--;
 209                 depth2--;
 210             }
 211         }
 212         throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" );
 213     }
 214
 215     /**
 216      * Returns the LCA of PhylogenyNodes node1 and node2.
 217      * Precondition: ids are in pre-order (or level-order).
 218      *
 219      *
 220      * @param node1
 221      * @param node2
 222      * @return LCA of node1 and node2
 223      */
 224     public final static PhylogenyNode calculateLCAonTreeWithIdsInPreOrder( PhylogenyNode node1, PhylogenyNode node2 ) {
 225         if ( node1 == null ) {
 226             throw new IllegalArgumentException( "first argument (node) is null" );
 227         }
 228         if ( node2 == null ) {
 229             throw new IllegalArgumentException( "second argument (node) is null" );
 230         }
 231         while ( node1 != node2 ) {
 232             if ( node1.getId() > node2.getId() ) {
 233                 node1 = node1.getParent();
 234             }
 235             else {
 236                 node2 = node2.getParent();
 237             }
 238         }
 239         return node1;
 240     }
 241
 242     public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) {
 243         if ( node.isExternal() ) {
 244             return 0;
 245         }
 246         short max = 0;
 247         for( PhylogenyNode d : node.getAllExternalDescendants() ) {
 248             short steps = 0;
 249             while ( d != node ) {
 250                 if ( d.isCollapse() ) {
 251                     steps = 0;
 252                 }
 253                 else {
 254                     steps++;
 255                 }
 256                 d = d.getParent();
 257             }
 258             if ( max < steps ) {
 259                 max = steps;
 260             }
 261         }
 262         return max;
 263     }
 264
 265     public static int calculateMaxDepth( final Phylogeny phy ) {
 266         int max = 0;
 267         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 268             final PhylogenyNode node = iter.next();
 269             final int steps = node.calculateDepth();
 270             if ( steps > max ) {
 271                 max = steps;
 272             }
 273         }
 274         return max;
 275     }
 276
 277     public static double calculateMaxDistanceToRoot( final Phylogeny phy ) {
 278         double max = 0.0;
 279         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 280             final PhylogenyNode node = iter.next();
 281             final double d = node.calculateDistanceToRoot();
 282             if ( d > max ) {
 283                 max = d;
 284             }
 285         }
 286         return max;
 287     }
 288
 289     public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) {
 290         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 291         int x = 0;
 292         for( final PhylogenyNode n : descs ) {
 293             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 294                 x++;
 295             }
 296         }
 297         return x;
 298     }
 299
 300     public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) {
 301         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 302         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 303             final PhylogenyNode n = iter.next();
 304             if ( !n.isExternal() ) {
 305                 stats.addValue( n.getNumberOfDescendants() );
 306             }
 307         }
 308         return stats;
 309     }
 310
 311     public static int countNumberOfOneDescendantNodes( final Phylogeny phy ) {
 312         int count = 0;
 313         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 314             final PhylogenyNode n = iter.next();
 315             if ( !n.isExternal() && ( n.getNumberOfDescendants() == 1 ) ) {
 316                 count++;
 317             }
 318         }
 319         return count;
 320     }
 321
 322     public static int countNumberOfPolytomies( final Phylogeny phy ) {
 323         int count = 0;
 324         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 325             final PhylogenyNode n = iter.next();
 326             if ( !n.isExternal() && ( n.getNumberOfDescendants() > 2 ) ) {
 327                 count++;
 328             }
 329         }
 330         return count;
 331     }
 332
 333     public static final HashMap<String, PhylogenyNode> createNameToExtNodeMap( final Phylogeny phy ) {
 334         final HashMap<String, PhylogenyNode> nodes = new HashMap<String, PhylogenyNode>();
 335         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 336             final PhylogenyNode n = iter.next();
 337             nodes.put( n.getName(), n );
 338         }
 339         return nodes;
 340     }
 341
 342     public static void deleteExternalNodesNegativeSelection( final Set<Integer> to_delete, final Phylogeny phy ) {
 343         phy.clearHashIdToNodeMap();
 344         for( final Integer id : to_delete ) {
 345             phy.deleteSubtree( phy.getNode( id ), true );
 346         }
 347         phy.clearHashIdToNodeMap();
 348         phy.externalNodesHaveChanged();
 349     }
 350
 351     public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p )
 352             throws IllegalArgumentException {
 353         for( final String element : node_names_to_delete ) {
 354             if ( ForesterUtil.isEmpty( element ) ) {
 355                 continue;
 356             }
 357             List<PhylogenyNode> nodes = null;
 358             nodes = p.getNodes( element );
 359             final Iterator<PhylogenyNode> it = nodes.iterator();
 360             while ( it.hasNext() ) {
 361                 final PhylogenyNode n = it.next();
 362                 if ( !n.isExternal() ) {
 363                     throw new IllegalArgumentException( "attempt to delete non-external node \"" + element + "\"" );
 364                 }
 365                 p.deleteSubtree( n, true );
 366             }
 367         }
 368         p.clearHashIdToNodeMap();
 369         p.externalNodesHaveChanged();
 370     }
 371
 372     public static void deleteExternalNodesPositiveSelection( final Set<Taxonomy> species_to_keep, final Phylogeny phy ) {
 373         //   final Set<Integer> to_delete = new HashSet<Integer>();
 374         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 375             final PhylogenyNode n = it.next();
 376             if ( n.getNodeData().isHasTaxonomy() ) {
 377                 if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) {
 378                     //to_delete.add( n.getNodeId() );
 379                     phy.deleteSubtree( n, true );
 380                 }
 381             }
 382             else {
 383                 throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" );
 384             }
 385         }
 386         phy.clearHashIdToNodeMap();
 387         phy.externalNodesHaveChanged();
 388     }
 389
 390     public static List<String> deleteExternalNodesPositiveSelection( final String[] node_names_to_keep,
 391                                                                      final Phylogeny p ) {
 392         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 393         final String[] to_delete = new String[ p.getNumberOfExternalNodes() ];
 394         int i = 0;
 395         Arrays.sort( node_names_to_keep );
 396         while ( it.hasNext() ) {
 397             final String curent_name = it.next().getName();
 398             if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) {
 399                 to_delete[ i++ ] = curent_name;
 400             }
 401         }
 402         PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p );
 403         final List<String> deleted = new ArrayList<String>();
 404         for( final String n : to_delete ) {
 405             if ( !ForesterUtil.isEmpty( n ) ) {
 406                 deleted.add( n );
 407             }
 408         }
 409         return deleted;
 410     }
 411
 412     final public static void deleteInternalNodesWithOnlyOneDescendent( final Phylogeny phy ) {
 413         final ArrayList<PhylogenyNode> to_delete = new ArrayList<PhylogenyNode>();
 414         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
 415             final PhylogenyNode n = iter.next();
 416             if ( !n.isExternal() && ( n.getNumberOfDescendants() == 1 ) ) {
 417                 to_delete.add( n );
 418             }
 419         }
 420         for( final PhylogenyNode d : to_delete ) {
 421             PhylogenyMethods.removeNode( d, phy );
 422         }
 423         phy.clearHashIdToNodeMap();
 424         phy.externalNodesHaveChanged();
 425     }
 426
 427     final public static void deleteNonOrthologousExternalNodes( final Phylogeny phy, final PhylogenyNode n ) {
 428         if ( n.isInternal() ) {
 429             throw new IllegalArgumentException( "node is not external" );
 430         }
 431         final ArrayList<PhylogenyNode> to_delete = new ArrayList<PhylogenyNode>();
 432         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 433             final PhylogenyNode i = it.next();
 434             if ( !PhylogenyMethods.getEventAtLCA( n, i ).isSpeciation() ) {
 435                 to_delete.add( i );
 436             }
 437         }
 438         for( final PhylogenyNode d : to_delete ) {
 439             phy.deleteSubtree( d, true );
 440         }
 441         phy.clearHashIdToNodeMap();
 442         phy.externalNodesHaveChanged();
 443     }
 444
 445     public static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 446         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 447         final Set<Integer> encountered = new HashSet<Integer>();
 448         if ( !node.isExternal() ) {
 449             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 450             for( PhylogenyNode current : exts ) {
 451                 descs.add( current );
 452                 while ( current != node ) {
 453                     current = current.getParent();
 454                     if ( encountered.contains( current.getId() ) ) {
 455                         continue;
 456                     }
 457                     descs.add( current );
 458                     encountered.add( current.getId() );
 459                 }
 460             }
 461         }
 462         return descs;
 463     }
 464
 465     /**
 466      *
 467      * Convenience method
 468      *
 469      * @param node
 470      * @return
 471      */
 472     public static Color getBranchColorValue( final PhylogenyNode node ) {
 473         if ( node.getBranchData().getBranchColor() == null ) {
 474             return null;
 475         }
 476         return node.getBranchData().getBranchColor().getValue();
 477     }
 478
 479     /**
 480      * Convenience method
 481      */
 482     public static double getBranchWidthValue( final PhylogenyNode node ) {
 483         if ( !node.getBranchData().isHasBranchWidth() ) {
 484             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 485         }
 486         return node.getBranchData().getBranchWidth().getValue();
 487     }
 488
 489     /**
 490      * Convenience method
 491      */
 492     public static double getConfidenceValue( final PhylogenyNode node ) {
 493         if ( !node.getBranchData().isHasConfidences() ) {
 494             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 495         }
 496         return node.getBranchData().getConfidence( 0 ).getValue();
 497     }
 498
 499     /**
 500      * Convenience method
 501      */
 502     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 503         if ( !node.getBranchData().isHasConfidences() ) {
 504             return new double[ 0 ];
 505         }
 506         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 507         int i = 0;
 508         for( final Confidence c : node.getBranchData().getConfidences() ) {
 509             values[ i++ ] = c.getValue();
 510         }
 511         return values;
 512     }
 513
 514     final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) {
 515         return calculateLCA( n1, n2 ).getNodeData().getEvent();
 516     }
 517
 518     /**
 519      * Returns taxonomy t if all external descendants have
 520      * the same taxonomy t, null otherwise.
 521      *
 522      */
 523     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 524         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 525         Taxonomy tax = null;
 526         for( final PhylogenyNode n : descs ) {
 527             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 528                 return null;
 529             }
 530             else if ( tax == null ) {
 531                 tax = n.getNodeData().getTaxonomy();
 532             }
 533             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 534                 return null;
 535             }
 536         }
 537         return tax;
 538     }
 539
 540     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 541         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 542         PhylogenyNode farthest = null;
 543         double longest = -Double.MAX_VALUE;
 544         for( final PhylogenyNode child : children ) {
 545             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 546                 farthest = child;
 547                 longest = PhylogenyMethods.getDistance( child, node );
 548             }
 549         }
 550         return farthest;
 551     }
 552
 553     public static PhylogenyMethods getInstance() {
 554         if ( PhylogenyMethods._instance == null ) {
 555             PhylogenyMethods._instance = new PhylogenyMethods();
 556         }
 557         return PhylogenyMethods._instance;
 558     }
 559
 560     /**
 561      * Returns the largest confidence value found on phy.
 562      */
 563     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 564         double max = -Double.MAX_VALUE;
 565         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 566             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 567             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 568                 max = s;
 569             }
 570         }
 571         return max;
 572     }
 573
 574     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 575         int min = Integer.MAX_VALUE;
 576         int d = 0;
 577         PhylogenyNode n;
 578         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 579             n = it.next();
 580             if ( n.isInternal() ) {
 581                 d = n.getNumberOfDescendants();
 582                 if ( d < min ) {
 583                     min = d;
 584                 }
 585             }
 586         }
 587         return min;
 588     }
 589
 590     /**
 591      * Convenience method for display purposes.
 592      * Not intended for algorithms.
 593      */
 594     public static String getSpecies( final PhylogenyNode node ) {
 595         if ( !node.getNodeData().isHasTaxonomy() ) {
 596             return "";
 597         }
 598         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
 599             return node.getNodeData().getTaxonomy().getScientificName();
 600         }
 601         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 602             return node.getNodeData().getTaxonomy().getTaxonomyCode();
 603         }
 604         else {
 605             return node.getNodeData().getTaxonomy().getCommonName();
 606         }
 607     }
 608
 609     /**
 610      * Convenience method for display purposes.
 611      * Not intended for algorithms.
 612      */
 613     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
 614         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
 615             return "";
 616         }
 617         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
 618     }
 619
 620     public final static boolean isAllDecendentsAreDuplications( final PhylogenyNode n ) {
 621         if ( n.isExternal() ) {
 622             return true;
 623         }
 624         else {
 625             if ( n.isDuplication() ) {
 626                 for( final PhylogenyNode desc : n.getDescendants() ) {
 627                     if ( !isAllDecendentsAreDuplications( desc ) ) {
 628                         return false;
 629                     }
 630                 }
 631                 return true;
 632             }
 633             else {
 634                 return false;
 635             }
 636         }
 637     }
 638
 639     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
 640         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 641             if ( node.getChildNode( i ).isExternal() ) {
 642                 return true;
 643             }
 644         }
 645         return false;
 646     }
 647
 648     /*
 649      * This is case insensitive.
 650      *
 651      */
 652     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
 653                                                                                final String[] providers ) {
 654         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
 655             final String my_tax_prov = tax.getIdentifier().getProvider();
 656             for( final String provider : providers ) {
 657                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
 658                     return true;
 659                 }
 660             }
 661             return false;
 662         }
 663         else {
 664             return false;
 665         }
 666     }
 667
 668     public static void midpointRoot( final Phylogeny phylogeny ) {
 669         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
 670             return;
 671         }
 672         final PhylogenyMethods methods = getInstance();
 673         final double farthest_d = methods.calculateFurthestDistance( phylogeny );
 674         final PhylogenyNode f1 = methods.getFarthestNode1();
 675         final PhylogenyNode f2 = methods.getFarthestNode2();
 676         if ( farthest_d <= 0.0 ) {
 677             return;
 678         }
 679         double x = farthest_d / 2.0;
 680         PhylogenyNode n = f1;
 681         if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny
 682                 .getRoot() ) ) {
 683             n = f2;
 684         }
 685         while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) {
 686             x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
 687             n = n.getParent();
 688         }
 689         phylogeny.reRoot( n, x );
 690         phylogeny.recalculateNumberOfExternalDescendants( true );
 691         final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() );
 692         final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() );
 693         final double da = getDistance( a, phylogeny.getRoot() );
 694         final double db = getDistance( b, phylogeny.getRoot() );
 695         if ( Math.abs( da - db ) > 0.000001 ) {
 696             throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed:  da="
 697                     + da + ",  db=" + db + ",  diff=" + Math.abs( da - db ) );
 698         }
 699     }
 700
 701     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
 702                                                  final double max_bootstrap_value,
 703                                                  final double max_normalized_value ) {
 704         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
 705             final PhylogenyNode node = iter.next();
 706             if ( node.isInternal() ) {
 707                 final double confidence = getConfidenceValue( node );
 708                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 709                     if ( confidence >= max_bootstrap_value ) {
 710                         setBootstrapConfidence( node, max_normalized_value );
 711                     }
 712                     else {
 713                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
 714                     }
 715                 }
 716             }
 717         }
 718     }
 719
 720     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
 721         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 722         if ( phy.isEmpty() ) {
 723             return nodes;
 724         }
 725         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 726             nodes.add( iter.next() );
 727         }
 728         return nodes;
 729     }
 730
 731     /**
 732      * Returns the set of distinct taxonomies of
 733      * all external nodes of node.
 734      * If at least one the external nodes has no taxonomy,
 735      * null is returned.
 736      *
 737      */
 738     public static Set<Taxonomy> obtainDistinctTaxonomies( final PhylogenyNode node ) {
 739         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 740         final Set<Taxonomy> tax_set = new HashSet<Taxonomy>();
 741         for( final PhylogenyNode n : descs ) {
 742             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 743                 return null;
 744             }
 745             tax_set.add( n.getNodeData().getTaxonomy() );
 746         }
 747         return tax_set;
 748     }
 749
 750     /**
 751      * Returns a map of distinct taxonomies of
 752      * all external nodes of node.
 753      * If at least one of the external nodes has no taxonomy,
 754      * null is returned.
 755      *
 756      */
 757     public static SortedMap<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 758         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 759         final SortedMap<Taxonomy, Integer> tax_map = new TreeMap<Taxonomy, Integer>();
 760         for( final PhylogenyNode n : descs ) {
 761             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 762                 return null;
 763             }
 764             final Taxonomy t = n.getNodeData().getTaxonomy();
 765             if ( tax_map.containsKey( t ) ) {
 766                 tax_map.put( t, tax_map.get( t ) + 1 );
 767             }
 768             else {
 769                 tax_map.put( t, 1 );
 770             }
 771         }
 772         return tax_map;
 773     }
 774
 775     /**
 776      * Arranges the order of childern for each node of this Phylogeny in such a
 777      * way that either the branch with more children is on top (right) or on
 778      * bottom (left), dependent on the value of boolean order.
 779      *
 780      * @param order
 781      *            decides in which direction to order
 782      * @param pri
 783      */
 784     public static void orderAppearance( final PhylogenyNode n,
 785                                         final boolean order,
 786                                         final boolean order_ext_alphabetically,
 787                                         final DESCENDANT_SORT_PRIORITY pri ) {
 788         if ( n.isExternal() ) {
 789             return;
 790         }
 791         else {
 792             PhylogenyNode temp = null;
 793             if ( ( n.getNumberOfDescendants() == 2 )
 794                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
 795                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
 796                 temp = n.getChildNode1();
 797                 n.setChild1( n.getChildNode2() );
 798                 n.setChild2( temp );
 799             }
 800             else if ( order_ext_alphabetically ) {
 801                 boolean all_ext = true;
 802                 for( final PhylogenyNode i : n.getDescendants() ) {
 803                     if ( !i.isExternal() ) {
 804                         all_ext = false;
 805                         break;
 806                     }
 807                 }
 808                 if ( all_ext ) {
 809                     PhylogenyMethods.sortNodeDescendents( n, pri );
 810                 }
 811             }
 812             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 813                 orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri );
 814             }
 815         }
 816     }
 817
 818     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
 819         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
 820             final PhylogenyNode node = iter.next();
 821             double red = 0.0;
 822             double green = 0.0;
 823             double blue = 0.0;
 824             int n = 0;
 825             if ( node.isInternal() ) {
 826                 //for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
 827                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 828                     final PhylogenyNode child_node = node.getChildNode( i );
 829                     final Color child_color = getBranchColorValue( child_node );
 830                     if ( child_color != null ) {
 831                         ++n;
 832                         red += child_color.getRed();
 833                         green += child_color.getGreen();
 834                         blue += child_color.getBlue();
 835                     }
 836                 }
 837                 setBranchColorValue( node,
 838                                      new Color( ForesterUtil.roundToInt( red / n ),
 839                                                 ForesterUtil.roundToInt( green / n ),
 840                                                 ForesterUtil.roundToInt( blue / n ) ) );
 841             }
 842         }
 843     }
 844
 845     public static final void preOrderReId( final Phylogeny phy ) {
 846         if ( phy.isEmpty() ) {
 847             return;
 848         }
 849         phy.setIdToNodeMap( null );
 850         int i = PhylogenyNode.getNodeCount();
 851         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 852             it.next().setId( i++ );
 853         }
 854         PhylogenyNode.setNodeCount( i );
 855     }
 856
 857     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException {
 858         final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 859         final Phylogeny[] trees = factory.create( file, parser );
 860         if ( ( trees == null ) || ( trees.length == 0 ) ) {
 861             throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 862         }
 863         return trees;
 864     }
 865
 866     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final List<File> files )
 867             throws IOException {
 868         final List<Phylogeny> tree_list = new ArrayList<Phylogeny>();
 869         for( final File file : files ) {
 870             final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 871             final Phylogeny[] trees = factory.create( file, parser );
 872             if ( ( trees == null ) || ( trees.length == 0 ) ) {
 873                 throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 874             }
 875             tree_list.addAll( Arrays.asList( trees ) );
 876         }
 877         return tree_list.toArray( new Phylogeny[ tree_list.size() ] );
 878     }
 879
 880     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
 881         if ( remove_me.isRoot() ) {
 882             throw new IllegalArgumentException( "ill advised attempt to remove root node" );
 883         }
 884         if ( remove_me.isExternal() ) {
 885             phylogeny.deleteSubtree( remove_me, false );
 886             phylogeny.clearHashIdToNodeMap();
 887             phylogeny.externalNodesHaveChanged();
 888         }
 889         else {
 890             final PhylogenyNode parent = remove_me.getParent();
 891             final List<PhylogenyNode> descs = remove_me.getDescendants();
 892             parent.removeChildNode( remove_me );
 893             for( final PhylogenyNode desc : descs ) {
 894                 parent.addAsChild( desc );
 895                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
 896                                                                  desc.getDistanceToParent() ) );
 897             }
 898             remove_me.setParent( null );
 899             phylogeny.clearHashIdToNodeMap();
 900             phylogeny.externalNodesHaveChanged();
 901         }
 902     }
 903
 904     public static List<PhylogenyNode> searchData( final String query,
 905                                                   final Phylogeny phy,
 906                                                   final boolean case_sensitive,
 907                                                   final boolean partial,
 908                                                   final boolean search_domains ) {
 909         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 910         if ( phy.isEmpty() || ( query == null ) ) {
 911             return nodes;
 912         }
 913         if ( ForesterUtil.isEmpty( query ) ) {
 914             return nodes;
 915         }
 916         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 917             final PhylogenyNode node = iter.next();
 918             boolean match = false;
 919             if ( match( node.getName(), query, case_sensitive, partial ) ) {
 920                 match = true;
 921             }
 922             else if ( node.getNodeData().isHasTaxonomy()
 923                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 924                 match = true;
 925             }
 926             else if ( node.getNodeData().isHasTaxonomy()
 927                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
 928                 match = true;
 929             }
 930             else if ( node.getNodeData().isHasTaxonomy()
 931                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
 932                 match = true;
 933             }
 934             else if ( node.getNodeData().isHasTaxonomy()
 935                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
 936                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
 937                               query,
 938                               case_sensitive,
 939                               partial ) ) {
 940                 match = true;
 941             }
 942             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
 943                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
 944                 I: for( final String syn : syns ) {
 945                     if ( match( syn, query, case_sensitive, partial ) ) {
 946                         match = true;
 947                         break I;
 948                     }
 949                 }
 950             }
 951             if ( !match && node.getNodeData().isHasSequence()
 952                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
 953                 match = true;
 954             }
 955             if ( !match && node.getNodeData().isHasSequence()
 956                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
 957                 match = true;
 958             }
 959             if ( !match
 960                     && node.getNodeData().isHasSequence()
 961                     && ( node.getNodeData().getSequence().getAccession() != null )
 962                     && match( node.getNodeData().getSequence().getAccession().getValue(),
 963                               query,
 964                               case_sensitive,
 965                               partial ) ) {
 966                 match = true;
 967             }
 968             if ( search_domains && !match && node.getNodeData().isHasSequence()
 969                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
 970                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
 971                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
 972                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
 973                         match = true;
 974                         break I;
 975                     }
 976                 }
 977             }
 978             if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
 979                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
 980                 I: while ( it.hasNext() ) {
 981                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 982                         match = true;
 983                         break I;
 984                     }
 985                 }
 986                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
 987                 I: while ( it.hasNext() ) {
 988                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 989                         match = true;
 990                         break I;
 991                     }
 992                 }
 993             }
 994             if ( match ) {
 995                 nodes.add( node );
 996             }
 997         }
 998         return nodes;
 999     }
1000
1001     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
1002                                                             final Phylogeny phy,
1003                                                             final boolean case_sensitive,
1004                                                             final boolean partial,
1005                                                             final boolean search_domains ) {
1006         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1007         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
1008             return nodes;
1009         }
1010         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1011             final PhylogenyNode node = iter.next();
1012             boolean all_matched = true;
1013             for( final String query : queries ) {
1014                 boolean match = false;
1015                 if ( ForesterUtil.isEmpty( query ) ) {
1016                     continue;
1017                 }
1018                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
1019                     match = true;
1020                 }
1021                 else if ( node.getNodeData().isHasTaxonomy()
1022                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1023                     match = true;
1024                 }
1025                 else if ( node.getNodeData().isHasTaxonomy()
1026                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1027                     match = true;
1028                 }
1029                 else if ( node.getNodeData().isHasTaxonomy()
1030                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1031                     match = true;
1032                 }
1033                 else if ( node.getNodeData().isHasTaxonomy()
1034                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1035                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1036                                   query,
1037                                   case_sensitive,
1038                                   partial ) ) {
1039                     match = true;
1040                 }
1041                 else if ( node.getNodeData().isHasTaxonomy()
1042                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1043                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1044                     I: for( final String syn : syns ) {
1045                         if ( match( syn, query, case_sensitive, partial ) ) {
1046                             match = true;
1047                             break I;
1048                         }
1049                     }
1050                 }
1051                 if ( !match && node.getNodeData().isHasSequence()
1052                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1053                     match = true;
1054                 }
1055                 if ( !match && node.getNodeData().isHasSequence()
1056                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1057                     match = true;
1058                 }
1059                 if ( !match
1060                         && node.getNodeData().isHasSequence()
1061                         && ( node.getNodeData().getSequence().getAccession() != null )
1062                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1063                                   query,
1064                                   case_sensitive,
1065                                   partial ) ) {
1066                     match = true;
1067                 }
1068                 if ( search_domains && !match && node.getNodeData().isHasSequence()
1069                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1070                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1071                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1072                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1073                             match = true;
1074                             break I;
1075                         }
1076                     }
1077                 }
1078                 if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1079                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1080                     I: while ( it.hasNext() ) {
1081                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1082                             match = true;
1083                             break I;
1084                         }
1085                     }
1086                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1087                     I: while ( it.hasNext() ) {
1088                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1089                             match = true;
1090                             break I;
1091                         }
1092                     }
1093                 }
1094                 if ( !match ) {
1095                     all_matched = false;
1096                     break;
1097                 }
1098             }
1099             if ( all_matched ) {
1100                 nodes.add( node );
1101             }
1102         }
1103         return nodes;
1104     }
1105
1106     /**
1107      * Convenience method.
1108      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1109      */
1110     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1111         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1112     }
1113
1114     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1115         if ( node.getBranchData().getBranchColor() == null ) {
1116             node.getBranchData().setBranchColor( new BranchColor() );
1117         }
1118         node.getBranchData().getBranchColor().setValue( color );
1119     }
1120
1121     /**
1122      * Convenience method
1123      */
1124     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1125         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1126     }
1127
1128     /**
1129      * Convenience method.
1130      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1131      */
1132     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1133         setConfidence( node, confidence_value, "" );
1134     }
1135
1136     /**
1137      * Convenience method.
1138      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1139      */
1140     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1141         Confidence c = null;
1142         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1143             c = node.getBranchData().getConfidence( 0 );
1144         }
1145         else {
1146             c = new Confidence();
1147             node.getBranchData().addConfidence( c );
1148         }
1149         c.setType( type );
1150         c.setValue( confidence_value );
1151     }
1152
1153     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1154         if ( !node.getNodeData().isHasTaxonomy() ) {
1155             node.getNodeData().setTaxonomy( new Taxonomy() );
1156         }
1157         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1158     }
1159
1160     /**
1161      * Convenience method to set the taxonomy code of a phylogeny node.
1162      *
1163      *
1164      * @param node
1165      * @param taxonomy_code
1166      * @throws PhyloXmlDataFormatException
1167      */
1168     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code )
1169             throws PhyloXmlDataFormatException {
1170         if ( !node.getNodeData().isHasTaxonomy() ) {
1171             node.getNodeData().setTaxonomy( new Taxonomy() );
1172         }
1173         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1174     }
1175
1176     final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) {
1177         class PhylogenyNodeSortTaxonomyPriority implements Comparator<PhylogenyNode> {
1178
1179             @Override
1180             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1181                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1182                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1183                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1184                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1185                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1186                     }
1187                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1188                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1189                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1190                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1191                     }
1192                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1193                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1194                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1195                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1196                     }
1197                 }
1198                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1199                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1200                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1201                         return n1.getNodeData().getSequence().getName().toLowerCase()
1202                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1203                     }
1204                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1205                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1206                         return n1.getNodeData().getSequence().getSymbol()
1207                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1208                     }
1209                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1210                             && ( n2.getNodeData().getSequence().getAccession() != null )
1211                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1212                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1213                         return n1.getNodeData().getSequence().getAccession().getValue()
1214                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1215                     }
1216                 }
1217                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1218                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1219                 }
1220                 return 0;
1221             }
1222         }
1223         class PhylogenyNodeSortSequencePriority implements Comparator<PhylogenyNode> {
1224
1225             @Override
1226             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1227                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1228                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1229                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1230                         return n1.getNodeData().getSequence().getName().toLowerCase()
1231                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1232                     }
1233                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1234                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1235                         return n1.getNodeData().getSequence().getSymbol()
1236                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1237                     }
1238                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1239                             && ( n2.getNodeData().getSequence().getAccession() != null )
1240                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1241                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1242                         return n1.getNodeData().getSequence().getAccession().getValue()
1243                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1244                     }
1245                 }
1246                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1247                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1248                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1249                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1250                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1251                     }
1252                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1253                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1254                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1255                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1256                     }
1257                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1258                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1259                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1260                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1261                     }
1262                 }
1263                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1264                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1265                 }
1266                 return 0;
1267             }
1268         }
1269         class PhylogenyNodeSortNodeNamePriority implements Comparator<PhylogenyNode> {
1270
1271             @Override
1272             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1273                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1274                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1275                 }
1276                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1277                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1278                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1279                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1280                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1281                     }
1282                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1283                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1284                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1285                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1286                     }
1287                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1288                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1289                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1290                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1291                     }
1292                 }
1293                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1294                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1295                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1296                         return n1.getNodeData().getSequence().getName().toLowerCase()
1297                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1298                     }
1299                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1300                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1301                         return n1.getNodeData().getSequence().getSymbol()
1302                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1303                     }
1304                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1305                             && ( n2.getNodeData().getSequence().getAccession() != null )
1306                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1307                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1308                         return n1.getNodeData().getSequence().getAccession().getValue()
1309                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1310                     }
1311                 }
1312                 return 0;
1313             }
1314         }
1315         Comparator<PhylogenyNode> c;
1316         switch ( pri ) {
1317             case SEQUENCE:
1318                 c = new PhylogenyNodeSortSequencePriority();
1319                 break;
1320             case NODE_NAME:
1321                 c = new PhylogenyNodeSortNodeNamePriority();
1322                 break;
1323             default:
1324                 c = new PhylogenyNodeSortTaxonomyPriority();
1325         }
1326         final List<PhylogenyNode> descs = node.getDescendants();
1327         Collections.sort( descs, c );
1328         int i = 0;
1329         for( final PhylogenyNode desc : descs ) {
1330             node.setChildNode( i++, desc );
1331         }
1332     }
1333
1334     /**
1335      * Removes from Phylogeny to_be_stripped all external Nodes which are
1336      * associated with a species NOT found in Phylogeny reference.
1337      *
1338      * @param reference
1339      *            a reference Phylogeny
1340      * @param to_be_stripped
1341      *            Phylogeny to be stripped
1342      * @return nodes removed from to_be_stripped
1343      */
1344     public static List<PhylogenyNode> taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference,
1345                                                                             final Phylogeny to_be_stripped ) {
1346         final Set<String> ref_ext_taxo = new HashSet<String>();
1347         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1348             final PhylogenyNode n = it.next();
1349             if ( !n.getNodeData().isHasTaxonomy() ) {
1350                 throw new IllegalArgumentException( "no taxonomic data in node: " + n );
1351             }
1352             //  ref_ext_taxo.add( getSpecies( n ) );
1353             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
1354                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() );
1355             }
1356             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1357                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() );
1358             }
1359         }
1360         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1361         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1362             final PhylogenyNode n = it.next();
1363             if ( !n.getNodeData().isHasTaxonomy() ) {
1364                 nodes_to_delete.add( n );
1365             }
1366             else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) )
1367                     && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1368                 nodes_to_delete.add( n );
1369             }
1370         }
1371         for( final PhylogenyNode n : nodes_to_delete ) {
1372             to_be_stripped.deleteSubtree( n, true );
1373         }
1374         to_be_stripped.clearHashIdToNodeMap();
1375         to_be_stripped.externalNodesHaveChanged();
1376         return nodes_to_delete;
1377     }
1378
1379     final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) {
1380         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1381         while ( it.hasNext() ) {
1382             final PhylogenyNode n = it.next();
1383             if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) {
1384                 double value = -1;
1385                 try {
1386                     value = Double.parseDouble( n.getName() );
1387                 }
1388                 catch ( final NumberFormatException e ) {
1389                     throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: "
1390                             + e.getLocalizedMessage() );
1391                 }
1392                 if ( value >= 0.0 ) {
1393                     n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) );
1394                     n.setName( "" );
1395                 }
1396             }
1397         }
1398     }
1399
1400     final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) {
1401         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1402         while ( it.hasNext() ) {
1403             final PhylogenyNode n = it.next();
1404             if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) {
1405                 if ( !ForesterUtil.isEmpty( n.getName() ) ) {
1406                     double d = -1.0;
1407                     try {
1408                         d = Double.parseDouble( n.getName() );
1409                     }
1410                     catch ( final Exception e ) {
1411                         d = -1.0;
1412                     }
1413                     if ( d >= 0.0 ) {
1414                         n.getBranchData().addConfidence( new Confidence( d, "" ) );
1415                         n.setName( "" );
1416                     }
1417                 }
1418             }
1419         }
1420     }
1421
1422     final static public void transferNodeNameToField( final Phylogeny phy,
1423                                                       final PhylogenyNodeField field,
1424                                                       final boolean external_only ) throws PhyloXmlDataFormatException {
1425         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1426         while ( it.hasNext() ) {
1427             final PhylogenyNode n = it.next();
1428             if ( external_only && n.isInternal() ) {
1429                 continue;
1430             }
1431             final String name = n.getName().trim();
1432             if ( !ForesterUtil.isEmpty( name ) ) {
1433                 switch ( field ) {
1434                     case TAXONOMY_CODE:
1435                         n.setName( "" );
1436                         setTaxonomyCode( n, name );
1437                         break;
1438                     case TAXONOMY_SCIENTIFIC_NAME:
1439                         n.setName( "" );
1440                         if ( !n.getNodeData().isHasTaxonomy() ) {
1441                             n.getNodeData().setTaxonomy( new Taxonomy() );
1442                         }
1443                         n.getNodeData().getTaxonomy().setScientificName( name );
1444                         break;
1445                     case TAXONOMY_COMMON_NAME:
1446                         n.setName( "" );
1447                         if ( !n.getNodeData().isHasTaxonomy() ) {
1448                             n.getNodeData().setTaxonomy( new Taxonomy() );
1449                         }
1450                         n.getNodeData().getTaxonomy().setCommonName( name );
1451                         break;
1452                     case SEQUENCE_SYMBOL:
1453                         n.setName( "" );
1454                         if ( !n.getNodeData().isHasSequence() ) {
1455                             n.getNodeData().setSequence( new Sequence() );
1456                         }
1457                         n.getNodeData().getSequence().setSymbol( name );
1458                         break;
1459                     case SEQUENCE_NAME:
1460                         n.setName( "" );
1461                         if ( !n.getNodeData().isHasSequence() ) {
1462                             n.getNodeData().setSequence( new Sequence() );
1463                         }
1464                         n.getNodeData().getSequence().setName( name );
1465                         break;
1466                     case TAXONOMY_ID_UNIPROT_1: {
1467                         if ( !n.getNodeData().isHasTaxonomy() ) {
1468                             n.getNodeData().setTaxonomy( new Taxonomy() );
1469                         }
1470                         String id = name;
1471                         final int i = name.indexOf( '_' );
1472                         if ( i > 0 ) {
1473                             id = name.substring( 0, i );
1474                         }
1475                         else {
1476                             n.setName( "" );
1477                         }
1478                         n.getNodeData().getTaxonomy()
1479                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1480                         break;
1481                     }
1482                     case TAXONOMY_ID_UNIPROT_2: {
1483                         if ( !n.getNodeData().isHasTaxonomy() ) {
1484                             n.getNodeData().setTaxonomy( new Taxonomy() );
1485                         }
1486                         String id = name;
1487                         final int i = name.indexOf( '_' );
1488                         if ( i > 0 ) {
1489                             id = name.substring( i + 1, name.length() );
1490                         }
1491                         else {
1492                             n.setName( "" );
1493                         }
1494                         n.getNodeData().getTaxonomy()
1495                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1496                         break;
1497                     }
1498                     case TAXONOMY_ID: {
1499                         if ( !n.getNodeData().isHasTaxonomy() ) {
1500                             n.getNodeData().setTaxonomy( new Taxonomy() );
1501                         }
1502                         n.getNodeData().getTaxonomy().setIdentifier( new Identifier( name ) );
1503                         break;
1504                     }
1505                 }
1506             }
1507         }
1508     }
1509
1510     static double addPhylogenyDistances( final double a, final double b ) {
1511         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {
1512             return a + b;
1513         }
1514         else if ( a >= 0.0 ) {
1515             return a;
1516         }
1517         else if ( b >= 0.0 ) {
1518             return b;
1519         }
1520         return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
1521     }
1522
1523     /**
1524      * Deep copies the phylogeny originating from this node.
1525      */
1526     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
1527         if ( source == null ) {
1528             return null;
1529         }
1530         else {
1531             final PhylogenyNode newnode = source.copyNodeData();
1532             if ( !source.isExternal() ) {
1533                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1534                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
1535                 }
1536             }
1537             return newnode;
1538         }
1539     }
1540
1541     /**
1542      * Shallow copies the phylogeny originating from this node.
1543      */
1544     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
1545         if ( source == null ) {
1546             return null;
1547         }
1548         else {
1549             final PhylogenyNode newnode = source.copyNodeDataShallow();
1550             if ( !source.isExternal() ) {
1551                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1552                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
1553                 }
1554             }
1555             return newnode;
1556         }
1557     }
1558
1559     /**
1560      * Calculates the distance between PhylogenyNodes n1 and n2.
1561      * PRECONDITION: n1 is a descendant of n2.
1562      *
1563      * @param n1
1564      *            a descendant of n2
1565      * @param n2
1566      * @return distance between n1 and n2
1567      */
1568     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
1569         double d = 0.0;
1570         while ( n1 != n2 ) {
1571             if ( n1.getDistanceToParent() > 0.0 ) {
1572                 d += n1.getDistanceToParent();
1573             }
1574             n1 = n1.getParent();
1575         }
1576         return d;
1577     }
1578
1579     private static boolean match( final String s,
1580                                   final String query,
1581                                   final boolean case_sensitive,
1582                                   final boolean partial ) {
1583         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
1584             return false;
1585         }
1586         String my_s = s.trim();
1587         String my_query = query.trim();
1588         if ( !case_sensitive ) {
1589             my_s = my_s.toLowerCase();
1590             my_query = my_query.toLowerCase();
1591         }
1592         if ( partial ) {
1593             return my_s.indexOf( my_query ) >= 0;
1594         }
1595         else {
1596             return my_s.equals( my_query );
1597         }
1598     }
1599
1600     public static enum DESCENDANT_SORT_PRIORITY {
1601         TAXONOMY, SEQUENCE, NODE_NAME;
1602     }
1603
1604     public static enum PhylogenyNodeField {
1605         CLADE_NAME,
1606         TAXONOMY_CODE,
1607         TAXONOMY_SCIENTIFIC_NAME,
1608         TAXONOMY_COMMON_NAME,
1609         SEQUENCE_SYMBOL,
1610         SEQUENCE_NAME,
1611         TAXONOMY_ID_UNIPROT_1,
1612         TAXONOMY_ID_UNIPROT_2,
1613         TAXONOMY_ID;
1614     }
1615 }