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