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