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