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