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