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