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