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 static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 414         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 415         final Set<Long> encountered = new HashSet<Long>();
 416         if ( !node.isExternal() ) {
 417             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 418             for( PhylogenyNode current : exts ) {
 419                 descs.add( current );
 420                 while ( current != node ) {
 421                     current = current.getParent();
 422                     if ( encountered.contains( current.getId() ) ) {
 423                         continue;
 424                     }
 425                     descs.add( current );
 426                     encountered.add( current.getId() );
 427                 }
 428             }
 429         }
 430         return descs;
 431     }
 432
 433     /**
 434      *
 435      * Convenience method
 436      *
 437      * @param node
 438      * @return
 439      */
 440     public static Color getBranchColorValue( final PhylogenyNode node ) {
 441         if ( node.getBranchData().getBranchColor() == null ) {
 442             return null;
 443         }
 444         return node.getBranchData().getBranchColor().getValue();
 445     }
 446
 447     /**
 448      * Convenience method
 449      */
 450     public static double getBranchWidthValue( final PhylogenyNode node ) {
 451         if ( !node.getBranchData().isHasBranchWidth() ) {
 452             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 453         }
 454         return node.getBranchData().getBranchWidth().getValue();
 455     }
 456
 457     /**
 458      * Convenience method
 459      */
 460     public static double getConfidenceValue( final PhylogenyNode node ) {
 461         if ( !node.getBranchData().isHasConfidences() ) {
 462             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 463         }
 464         return node.getBranchData().getConfidence( 0 ).getValue();
 465     }
 466
 467     /**
 468      * Convenience method
 469      */
 470     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 471         if ( !node.getBranchData().isHasConfidences() ) {
 472             return new double[ 0 ];
 473         }
 474         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 475         int i = 0;
 476         for( final Confidence c : node.getBranchData().getConfidences() ) {
 477             values[ i++ ] = c.getValue();
 478         }
 479         return values;
 480     }
 481
 482     final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) {
 483         return calculateLCA( n1, n2 ).getNodeData().getEvent();
 484     }
 485
 486     /**
 487      * Returns taxonomy t if all external descendants have
 488      * the same taxonomy t, null otherwise.
 489      *
 490      */
 491     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 492         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 493         Taxonomy tax = null;
 494         for( final PhylogenyNode n : descs ) {
 495             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 496                 return null;
 497             }
 498             else if ( tax == null ) {
 499                 tax = n.getNodeData().getTaxonomy();
 500             }
 501             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 502                 return null;
 503             }
 504         }
 505         return tax;
 506     }
 507
 508     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 509         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 510         PhylogenyNode farthest = null;
 511         double longest = -Double.MAX_VALUE;
 512         for( final PhylogenyNode child : children ) {
 513             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 514                 farthest = child;
 515                 longest = PhylogenyMethods.getDistance( child, node );
 516             }
 517         }
 518         return farthest;
 519     }
 520
 521     // public static PhylogenyMethods getInstance() {
 522     //     if ( PhylogenyMethods._instance == null ) {
 523     //         PhylogenyMethods._instance = new PhylogenyMethods();
 524     //    }
 525     //    return PhylogenyMethods._instance;
 526     //  }
 527     /**
 528      * Returns the largest confidence value found on phy.
 529      */
 530     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 531         double max = -Double.MAX_VALUE;
 532         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 533             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 534             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 535                 max = s;
 536             }
 537         }
 538         return max;
 539     }
 540
 541     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 542         int min = Integer.MAX_VALUE;
 543         int d = 0;
 544         PhylogenyNode n;
 545         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 546             n = it.next();
 547             if ( n.isInternal() ) {
 548                 d = n.getNumberOfDescendants();
 549                 if ( d < min ) {
 550                     min = d;
 551                 }
 552             }
 553         }
 554         return min;
 555     }
 556
 557     /**
 558      * Convenience method for display purposes.
 559      * Not intended for algorithms.
 560      */
 561     public static String getSpecies( final PhylogenyNode node ) {
 562         if ( !node.getNodeData().isHasTaxonomy() ) {
 563             return "";
 564         }
 565         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
 566             return node.getNodeData().getTaxonomy().getScientificName();
 567         }
 568         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 569             return node.getNodeData().getTaxonomy().getTaxonomyCode();
 570         }
 571         else {
 572             return node.getNodeData().getTaxonomy().getCommonName();
 573         }
 574     }
 575
 576     /**
 577      * Convenience method for display purposes.
 578      * Not intended for algorithms.
 579      */
 580     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
 581         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
 582             return "";
 583         }
 584         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
 585     }
 586
 587     public final static boolean isAllDecendentsAreDuplications( final PhylogenyNode n ) {
 588         if ( n.isExternal() ) {
 589             return true;
 590         }
 591         else {
 592             if ( n.isDuplication() ) {
 593                 for( final PhylogenyNode desc : n.getDescendants() ) {
 594                     if ( !isAllDecendentsAreDuplications( desc ) ) {
 595                         return false;
 596                     }
 597                 }
 598                 return true;
 599             }
 600             else {
 601                 return false;
 602             }
 603         }
 604     }
 605
 606     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
 607         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 608             if ( node.getChildNode( i ).isExternal() ) {
 609                 return true;
 610             }
 611         }
 612         return false;
 613     }
 614
 615     /*
 616      * This is case insensitive.
 617      *
 618      */
 619     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
 620                                                                                final String[] providers ) {
 621         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
 622             final String my_tax_prov = tax.getIdentifier().getProvider();
 623             for( final String provider : providers ) {
 624                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
 625                     return true;
 626                 }
 627             }
 628             return false;
 629         }
 630         else {
 631             return false;
 632         }
 633     }
 634
 635     public static void midpointRoot( final Phylogeny phylogeny ) {
 636         if ( ( phylogeny.getNumberOfExternalNodes() < 2 ) || ( calculateMaxDistanceToRoot( phylogeny ) <= 0 ) ) {
 637             return;
 638         }
 639         int counter = 0;
 640         final int total_nodes = phylogeny.getNodeCount();
 641         while ( true ) {
 642             if ( ++counter > total_nodes ) {
 643                 throw new RuntimeException( "this should not have happened: midpoint rooting does not converge" );
 644             }
 645             PhylogenyNode a = null;
 646             double da = 0;
 647             double db = 0;
 648             for( int i = 0; i < phylogeny.getRoot().getNumberOfDescendants(); ++i ) {
 649                 final PhylogenyNode f = getFurthestDescendant( phylogeny.getRoot().getChildNode( i ) );
 650                 final double df = getDistance( f, phylogeny.getRoot() );
 651                 if ( df > 0 ) {
 652                     if ( df > da ) {
 653                         db = da;
 654                         da = df;
 655                         a = f;
 656                     }
 657                     else if ( df > db ) {
 658                         db = df;
 659                     }
 660                 }
 661             }
 662             final double diff = da - db;
 663             if ( diff < 0.000001 ) {
 664                 break;
 665             }
 666             double x = da - ( diff / 2.0 );
 667             while ( ( x > a.getDistanceToParent() ) && !a.isRoot() ) {
 668                 x -= ( a.getDistanceToParent() > 0 ? a.getDistanceToParent() : 0 );
 669                 a = a.getParent();
 670             }
 671             phylogeny.reRoot( a, x );
 672         }
 673         phylogeny.recalculateNumberOfExternalDescendants( true );
 674     }
 675
 676     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
 677                                                  final double max_bootstrap_value,
 678                                                  final double max_normalized_value ) {
 679         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
 680             final PhylogenyNode node = iter.next();
 681             if ( node.isInternal() ) {
 682                 final double confidence = getConfidenceValue( node );
 683                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 684                     if ( confidence >= max_bootstrap_value ) {
 685                         setBootstrapConfidence( node, max_normalized_value );
 686                     }
 687                     else {
 688                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
 689                     }
 690                 }
 691             }
 692         }
 693     }
 694
 695     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
 696         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 697         if ( phy.isEmpty() ) {
 698             return nodes;
 699         }
 700         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 701             nodes.add( iter.next() );
 702         }
 703         return nodes;
 704     }
 705
 706     /**
 707      * Returns a map of distinct taxonomies of
 708      * all external nodes of node.
 709      * If at least one of the external nodes has no taxonomy,
 710      * null is returned.
 711      *
 712      */
 713     public static Map<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 714         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 715         final Map<Taxonomy, Integer> tax_map = new HashMap<Taxonomy, Integer>();
 716         for( final PhylogenyNode n : descs ) {
 717             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 718                 return null;
 719             }
 720             final Taxonomy t = n.getNodeData().getTaxonomy();
 721             if ( tax_map.containsKey( t ) ) {
 722                 tax_map.put( t, tax_map.get( t ) + 1 );
 723             }
 724             else {
 725                 tax_map.put( t, 1 );
 726             }
 727         }
 728         return tax_map;
 729     }
 730
 731     /**
 732      * Arranges the order of childern for each node of this Phylogeny in such a
 733      * way that either the branch with more children is on top (right) or on
 734      * bottom (left), dependent on the value of boolean order.
 735      *
 736      * @param order
 737      *            decides in which direction to order
 738      * @param pri
 739      */
 740     public static void orderAppearance( final PhylogenyNode n,
 741                                         final boolean order,
 742                                         final boolean order_ext_alphabetically,
 743                                         final DESCENDANT_SORT_PRIORITY pri ) {
 744         if ( n.isExternal() ) {
 745             return;
 746         }
 747         else {
 748             PhylogenyNode temp = null;
 749             if ( ( n.getNumberOfDescendants() == 2 )
 750                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
 751                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
 752                 temp = n.getChildNode1();
 753                 n.setChild1( n.getChildNode2() );
 754                 n.setChild2( temp );
 755             }
 756             else if ( order_ext_alphabetically ) {
 757                 boolean all_ext = true;
 758                 for( final PhylogenyNode i : n.getDescendants() ) {
 759                     if ( !i.isExternal() ) {
 760                         all_ext = false;
 761                         break;
 762                     }
 763                 }
 764                 if ( all_ext ) {
 765                     PhylogenyMethods.sortNodeDescendents( n, pri );
 766                 }
 767             }
 768             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 769                 orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri );
 770             }
 771         }
 772     }
 773
 774     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
 775         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
 776             final PhylogenyNode node = iter.next();
 777             double red = 0.0;
 778             double green = 0.0;
 779             double blue = 0.0;
 780             int n = 0;
 781             if ( node.isInternal() ) {
 782                 //for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
 783                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 784                     final PhylogenyNode child_node = node.getChildNode( i );
 785                     final Color child_color = getBranchColorValue( child_node );
 786                     if ( child_color != null ) {
 787                         ++n;
 788                         red += child_color.getRed();
 789                         green += child_color.getGreen();
 790                         blue += child_color.getBlue();
 791                     }
 792                 }
 793                 setBranchColorValue( node,
 794                                      new Color( ForesterUtil.roundToInt( red / n ),
 795                                                 ForesterUtil.roundToInt( green / n ),
 796                                                 ForesterUtil.roundToInt( blue / n ) ) );
 797             }
 798         }
 799     }
 800
 801     public static final void preOrderReId( final Phylogeny phy ) {
 802         if ( phy.isEmpty() ) {
 803             return;
 804         }
 805         phy.setIdToNodeMap( null );
 806         long i = PhylogenyNode.getNodeCount();
 807         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 808             it.next().setId( i++ );
 809         }
 810         PhylogenyNode.setNodeCount( i );
 811     }
 812
 813     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException {
 814         final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 815         final Phylogeny[] trees = factory.create( file, parser );
 816         if ( ( trees == null ) || ( trees.length == 0 ) ) {
 817             throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 818         }
 819         return trees;
 820     }
 821
 822     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final List<File> files )
 823             throws IOException {
 824         final List<Phylogeny> tree_list = new ArrayList<Phylogeny>();
 825         for( final File file : files ) {
 826             final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 827             final Phylogeny[] trees = factory.create( file, parser );
 828             if ( ( trees == null ) || ( trees.length == 0 ) ) {
 829                 throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 830             }
 831             tree_list.addAll( Arrays.asList( trees ) );
 832         }
 833         return tree_list.toArray( new Phylogeny[ tree_list.size() ] );
 834     }
 835
 836     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
 837         if ( remove_me.isRoot() ) {
 838             if ( remove_me.getNumberOfDescendants() == 1 ) {
 839                 final PhylogenyNode desc = remove_me.getDescendants().get( 0 );
 840                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
 841                                                                  desc.getDistanceToParent() ) );
 842                 desc.setParent( null );
 843                 phylogeny.setRoot( desc );
 844                 phylogeny.clearHashIdToNodeMap();
 845             }
 846             else {
 847                 throw new IllegalArgumentException( "attempt to remove a root node with more than one descendants" );
 848             }
 849         }
 850         else if ( remove_me.isExternal() ) {
 851             phylogeny.deleteSubtree( remove_me, false );
 852             phylogeny.clearHashIdToNodeMap();
 853             phylogeny.externalNodesHaveChanged();
 854         }
 855         else {
 856             final PhylogenyNode parent = remove_me.getParent();
 857             final List<PhylogenyNode> descs = remove_me.getDescendants();
 858             parent.removeChildNode( remove_me );
 859             for( final PhylogenyNode desc : descs ) {
 860                 parent.addAsChild( desc );
 861                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
 862                                                                  desc.getDistanceToParent() ) );
 863             }
 864             remove_me.setParent( null );
 865             phylogeny.clearHashIdToNodeMap();
 866             phylogeny.externalNodesHaveChanged();
 867         }
 868     }
 869
 870     public static List<PhylogenyNode> searchData( final String query,
 871                                                   final Phylogeny phy,
 872                                                   final boolean case_sensitive,
 873                                                   final boolean partial,
 874                                                   final boolean search_domains ) {
 875         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 876         if ( phy.isEmpty() || ( query == null ) ) {
 877             return nodes;
 878         }
 879         if ( ForesterUtil.isEmpty( query ) ) {
 880             return nodes;
 881         }
 882         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 883             final PhylogenyNode node = iter.next();
 884             boolean match = false;
 885             if ( match( node.getName(), query, case_sensitive, partial ) ) {
 886                 match = true;
 887             }
 888             else if ( node.getNodeData().isHasTaxonomy()
 889                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 890                 match = true;
 891             }
 892             else if ( node.getNodeData().isHasTaxonomy()
 893                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
 894                 match = true;
 895             }
 896             else if ( node.getNodeData().isHasTaxonomy()
 897                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
 898                 match = true;
 899             }
 900             else if ( node.getNodeData().isHasTaxonomy()
 901                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
 902                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
 903                               query,
 904                               case_sensitive,
 905                               partial ) ) {
 906                 match = true;
 907             }
 908             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
 909                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
 910                 I: for( final String syn : syns ) {
 911                     if ( match( syn, query, case_sensitive, partial ) ) {
 912                         match = true;
 913                         break I;
 914                     }
 915                 }
 916             }
 917             if ( !match && node.getNodeData().isHasSequence()
 918                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
 919                 match = true;
 920             }
 921             if ( !match && node.getNodeData().isHasSequence()
 922                     && match( node.getNodeData().getSequence().getGeneName(), query, case_sensitive, partial ) ) {
 923                 match = true;
 924             }
 925             if ( !match && node.getNodeData().isHasSequence()
 926                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
 927                 match = true;
 928             }
 929             if ( !match
 930                     && node.getNodeData().isHasSequence()
 931                     && ( node.getNodeData().getSequence().getAccession() != null )
 932                     && match( node.getNodeData().getSequence().getAccession().getValue(),
 933                               query,
 934                               case_sensitive,
 935                               partial ) ) {
 936                 match = true;
 937             }
 938             if ( search_domains && !match && node.getNodeData().isHasSequence()
 939                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
 940                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
 941                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
 942                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
 943                         match = true;
 944                         break I;
 945                     }
 946                 }
 947             }
 948             //
 949             if ( !match && node.getNodeData().isHasSequence()
 950                     && ( node.getNodeData().getSequence().getAnnotations() != null ) ) {
 951                 for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) {
 952                     if ( match( ann.getDesc(), query, case_sensitive, partial ) ) {
 953                         match = true;
 954                         break;
 955                     }
 956                     if ( match( ann.getRef(), query, case_sensitive, partial ) ) {
 957                         match = true;
 958                         break;
 959                     }
 960                 }
 961             }
 962             if ( !match && node.getNodeData().isHasSequence()
 963                     && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) {
 964                 for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) {
 965                     if ( match( x.getComment(), query, case_sensitive, partial ) ) {
 966                         match = true;
 967                         break;
 968                     }
 969                     if ( match( x.getSource(), query, case_sensitive, partial ) ) {
 970                         match = true;
 971                         break;
 972                     }
 973                     if ( match( x.getValue(), query, case_sensitive, partial ) ) {
 974                         match = true;
 975                         break;
 976                     }
 977                 }
 978             }
 979             //
 980             if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
 981                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
 982                 I: while ( it.hasNext() ) {
 983                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 984                         match = true;
 985                         break I;
 986                     }
 987                 }
 988                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
 989                 I: while ( it.hasNext() ) {
 990                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 991                         match = true;
 992                         break I;
 993                     }
 994                 }
 995             }
 996             if ( match ) {
 997                 nodes.add( node );
 998             }
 999         }
1000         return nodes;
1001     }
1002
1003     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
1004                                                             final Phylogeny phy,
1005                                                             final boolean case_sensitive,
1006                                                             final boolean partial,
1007                                                             final boolean search_domains ) {
1008         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1009         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
1010             return nodes;
1011         }
1012         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1013             final PhylogenyNode node = iter.next();
1014             boolean all_matched = true;
1015             for( final String query : queries ) {
1016                 boolean match = false;
1017                 if ( ForesterUtil.isEmpty( query ) ) {
1018                     continue;
1019                 }
1020                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
1021                     match = true;
1022                 }
1023                 else if ( node.getNodeData().isHasTaxonomy()
1024                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1025                     match = true;
1026                 }
1027                 else if ( node.getNodeData().isHasTaxonomy()
1028                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1029                     match = true;
1030                 }
1031                 else if ( node.getNodeData().isHasTaxonomy()
1032                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1033                     match = true;
1034                 }
1035                 else if ( node.getNodeData().isHasTaxonomy()
1036                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1037                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1038                                   query,
1039                                   case_sensitive,
1040                                   partial ) ) {
1041                     match = true;
1042                 }
1043                 else if ( node.getNodeData().isHasTaxonomy()
1044                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1045                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1046                     I: for( final String syn : syns ) {
1047                         if ( match( syn, query, case_sensitive, partial ) ) {
1048                             match = true;
1049                             break I;
1050                         }
1051                     }
1052                 }
1053                 if ( !match && node.getNodeData().isHasSequence()
1054                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1055                     match = true;
1056                 }
1057                 if ( !match && node.getNodeData().isHasSequence()
1058                         && match( node.getNodeData().getSequence().getGeneName(), query, case_sensitive, partial ) ) {
1059                     match = true;
1060                 }
1061                 if ( !match && node.getNodeData().isHasSequence()
1062                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1063                     match = true;
1064                 }
1065                 if ( !match
1066                         && node.getNodeData().isHasSequence()
1067                         && ( node.getNodeData().getSequence().getAccession() != null )
1068                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1069                                   query,
1070                                   case_sensitive,
1071                                   partial ) ) {
1072                     match = true;
1073                 }
1074                 if ( search_domains && !match && node.getNodeData().isHasSequence()
1075                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1076                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1077                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1078                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1079                             match = true;
1080                             break I;
1081                         }
1082                     }
1083                 }
1084                 //
1085                 if ( !match && node.getNodeData().isHasSequence()
1086                         && ( node.getNodeData().getSequence().getAnnotations() != null ) ) {
1087                     for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) {
1088                         if ( match( ann.getDesc(), query, case_sensitive, partial ) ) {
1089                             match = true;
1090                             break;
1091                         }
1092                         if ( match( ann.getRef(), query, case_sensitive, partial ) ) {
1093                             match = true;
1094                             break;
1095                         }
1096                     }
1097                 }
1098                 if ( !match && node.getNodeData().isHasSequence()
1099                         && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) {
1100                     for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) {
1101                         if ( match( x.getComment(), query, case_sensitive, partial ) ) {
1102                             match = true;
1103                             break;
1104                         }
1105                         if ( match( x.getSource(), query, case_sensitive, partial ) ) {
1106                             match = true;
1107                             break;
1108                         }
1109                         if ( match( x.getValue(), query, case_sensitive, partial ) ) {
1110                             match = true;
1111                             break;
1112                         }
1113                     }
1114                 }
1115                 //
1116                 if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1117                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1118                     I: while ( it.hasNext() ) {
1119                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1120                             match = true;
1121                             break I;
1122                         }
1123                     }
1124                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1125                     I: while ( it.hasNext() ) {
1126                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1127                             match = true;
1128                             break I;
1129                         }
1130                     }
1131                 }
1132                 if ( !match ) {
1133                     all_matched = false;
1134                     break;
1135                 }
1136             }
1137             if ( all_matched ) {
1138                 nodes.add( node );
1139             }
1140         }
1141         return nodes;
1142     }
1143
1144     /**
1145      * Convenience method.
1146      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1147      */
1148     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1149         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1150     }
1151
1152     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1153         if ( node.getBranchData().getBranchColor() == null ) {
1154             node.getBranchData().setBranchColor( new BranchColor() );
1155         }
1156         node.getBranchData().getBranchColor().setValue( color );
1157     }
1158
1159     /**
1160      * Convenience method
1161      */
1162     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1163         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1164     }
1165
1166     /**
1167      * Convenience method.
1168      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1169      */
1170     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1171         setConfidence( node, confidence_value, "" );
1172     }
1173
1174     /**
1175      * Convenience method.
1176      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1177      */
1178     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1179         Confidence c = null;
1180         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1181             c = node.getBranchData().getConfidence( 0 );
1182         }
1183         else {
1184             c = new Confidence();
1185             node.getBranchData().addConfidence( c );
1186         }
1187         c.setType( type );
1188         c.setValue( confidence_value );
1189     }
1190
1191     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1192         if ( !node.getNodeData().isHasTaxonomy() ) {
1193             node.getNodeData().setTaxonomy( new Taxonomy() );
1194         }
1195         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1196     }
1197
1198     /**
1199      * Convenience method to set the taxonomy code of a phylogeny node.
1200      *
1201      *
1202      * @param node
1203      * @param taxonomy_code
1204      * @throws PhyloXmlDataFormatException
1205      */
1206     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code )
1207             throws PhyloXmlDataFormatException {
1208         if ( !node.getNodeData().isHasTaxonomy() ) {
1209             node.getNodeData().setTaxonomy( new Taxonomy() );
1210         }
1211         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1212     }
1213
1214     final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) {
1215         class PhylogenyNodeSortTaxonomyPriority implements Comparator<PhylogenyNode> {
1216
1217             @Override
1218             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1219                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1220                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1221                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1222                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1223                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1224                     }
1225                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1226                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1227                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1228                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1229                     }
1230                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1231                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1232                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1233                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1234                     }
1235                 }
1236                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1237                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1238                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1239                         return n1.getNodeData().getSequence().getName().toLowerCase()
1240                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1241                     }
1242                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1243                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1244                         return n1.getNodeData().getSequence().getSymbol()
1245                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1246                     }
1247                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )
1248                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {
1249                         return n1.getNodeData().getSequence().getGeneName()
1250                                 .compareTo( n2.getNodeData().getSequence().getGeneName() );
1251                     }
1252                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1253                             && ( n2.getNodeData().getSequence().getAccession() != null )
1254                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1255                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1256                         return n1.getNodeData().getSequence().getAccession().getValue()
1257                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1258                     }
1259                 }
1260                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1261                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1262                 }
1263                 return 0;
1264             }
1265         }
1266         class PhylogenyNodeSortSequencePriority implements Comparator<PhylogenyNode> {
1267
1268             @Override
1269             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1270                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1271                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1272                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1273                         return n1.getNodeData().getSequence().getName().toLowerCase()
1274                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1275                     }
1276                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1277                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1278                         return n1.getNodeData().getSequence().getSymbol()
1279                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1280                     }
1281                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )
1282                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {
1283                         return n1.getNodeData().getSequence().getGeneName()
1284                                 .compareTo( n2.getNodeData().getSequence().getGeneName() );
1285                     }
1286                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1287                             && ( n2.getNodeData().getSequence().getAccession() != null )
1288                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1289                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1290                         return n1.getNodeData().getSequence().getAccession().getValue()
1291                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1292                     }
1293                 }
1294                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1295                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1296                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1297                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1298                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1299                     }
1300                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1301                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1302                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1303                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1304                     }
1305                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1306                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1307                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1308                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1309                     }
1310                 }
1311                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1312                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1313                 }
1314                 return 0;
1315             }
1316         }
1317         class PhylogenyNodeSortNodeNamePriority implements Comparator<PhylogenyNode> {
1318
1319             @Override
1320             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1321                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1322                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1323                 }
1324                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1325                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1326                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1327                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1328                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1329                     }
1330                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1331                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1332                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1333                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1334                     }
1335                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1336                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1337                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1338                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1339                     }
1340                 }
1341                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1342                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1343                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1344                         return n1.getNodeData().getSequence().getName().toLowerCase()
1345                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1346                     }
1347                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1348                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1349                         return n1.getNodeData().getSequence().getSymbol()
1350                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1351                     }
1352                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )
1353                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {
1354                         return n1.getNodeData().getSequence().getGeneName()
1355                                 .compareTo( n2.getNodeData().getSequence().getGeneName() );
1356                     }
1357                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1358                             && ( n2.getNodeData().getSequence().getAccession() != null )
1359                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1360                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1361                         return n1.getNodeData().getSequence().getAccession().getValue()
1362                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1363                     }
1364                 }
1365                 return 0;
1366             }
1367         }
1368         Comparator<PhylogenyNode> c;
1369         switch ( pri ) {
1370             case SEQUENCE:
1371                 c = new PhylogenyNodeSortSequencePriority();
1372                 break;
1373             case NODE_NAME:
1374                 c = new PhylogenyNodeSortNodeNamePriority();
1375                 break;
1376             default:
1377                 c = new PhylogenyNodeSortTaxonomyPriority();
1378         }
1379         final List<PhylogenyNode> descs = node.getDescendants();
1380         Collections.sort( descs, c );
1381         int i = 0;
1382         for( final PhylogenyNode desc : descs ) {
1383             node.setChildNode( i++, desc );
1384         }
1385     }
1386
1387     /**
1388      * Removes from Phylogeny to_be_stripped all external Nodes which are
1389      * associated with a species NOT found in Phylogeny reference.
1390      *
1391      * @param reference
1392      *            a reference Phylogeny
1393      * @param to_be_stripped
1394      *            Phylogeny to be stripped
1395      * @return nodes removed from to_be_stripped
1396      */
1397     public static List<PhylogenyNode> taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference,
1398                                                                             final Phylogeny to_be_stripped ) {
1399         final Set<String> ref_ext_taxo = new HashSet<String>();
1400         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1401             final PhylogenyNode n = it.next();
1402             if ( !n.getNodeData().isHasTaxonomy() ) {
1403                 throw new IllegalArgumentException( "no taxonomic data in node: " + n );
1404             }
1405             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
1406                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() );
1407             }
1408             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1409                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() );
1410             }
1411             if ( ( n.getNodeData().getTaxonomy().getIdentifier() != null )
1412                     && !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getIdentifier().getValue() ) ) {
1413                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() );
1414             }
1415         }
1416         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1417         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1418             final PhylogenyNode n = it.next();
1419             if ( !n.getNodeData().isHasTaxonomy() ) {
1420                 nodes_to_delete.add( n );
1421             }
1422             else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) )
1423                     && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1424                     && !( ( n.getNodeData().getTaxonomy().getIdentifier() != null ) && ref_ext_taxo.contains( n
1425                             .getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() ) ) ) {
1426                 nodes_to_delete.add( n );
1427             }
1428         }
1429         for( final PhylogenyNode n : nodes_to_delete ) {
1430             to_be_stripped.deleteSubtree( n, true );
1431         }
1432         to_be_stripped.clearHashIdToNodeMap();
1433         to_be_stripped.externalNodesHaveChanged();
1434         return nodes_to_delete;
1435     }
1436
1437     final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) {
1438         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1439         while ( it.hasNext() ) {
1440             final PhylogenyNode n = it.next();
1441             if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) {
1442                 double value = -1;
1443                 try {
1444                     value = Double.parseDouble( n.getName() );
1445                 }
1446                 catch ( final NumberFormatException e ) {
1447                     throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: "
1448                             + e.getLocalizedMessage() );
1449                 }
1450                 if ( value >= 0.0 ) {
1451                     n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) );
1452                     n.setName( "" );
1453                 }
1454             }
1455         }
1456     }
1457
1458     final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) {
1459         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1460         while ( it.hasNext() ) {
1461             final PhylogenyNode n = it.next();
1462             if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) {
1463                 if ( !ForesterUtil.isEmpty( n.getName() ) ) {
1464                     double d = -1.0;
1465                     try {
1466                         d = Double.parseDouble( n.getName() );
1467                     }
1468                     catch ( final Exception e ) {
1469                         d = -1.0;
1470                     }
1471                     if ( d >= 0.0 ) {
1472                         n.getBranchData().addConfidence( new Confidence( d, "" ) );
1473                         n.setName( "" );
1474                     }
1475                 }
1476             }
1477         }
1478     }
1479
1480     final static public void transferNodeNameToField( final Phylogeny phy,
1481                                                       final PhylogenyNodeField field,
1482                                                       final boolean external_only ) throws PhyloXmlDataFormatException {
1483         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1484         while ( it.hasNext() ) {
1485             final PhylogenyNode n = it.next();
1486             if ( external_only && n.isInternal() ) {
1487                 continue;
1488             }
1489             final String name = n.getName().trim();
1490             if ( !ForesterUtil.isEmpty( name ) ) {
1491                 switch ( field ) {
1492                     case TAXONOMY_CODE:
1493                         n.setName( "" );
1494                         setTaxonomyCode( n, name );
1495                         break;
1496                     case TAXONOMY_SCIENTIFIC_NAME:
1497                         n.setName( "" );
1498                         if ( !n.getNodeData().isHasTaxonomy() ) {
1499                             n.getNodeData().setTaxonomy( new Taxonomy() );
1500                         }
1501                         n.getNodeData().getTaxonomy().setScientificName( name );
1502                         break;
1503                     case TAXONOMY_COMMON_NAME:
1504                         n.setName( "" );
1505                         if ( !n.getNodeData().isHasTaxonomy() ) {
1506                             n.getNodeData().setTaxonomy( new Taxonomy() );
1507                         }
1508                         n.getNodeData().getTaxonomy().setCommonName( name );
1509                         break;
1510                     case SEQUENCE_SYMBOL:
1511                         n.setName( "" );
1512                         if ( !n.getNodeData().isHasSequence() ) {
1513                             n.getNodeData().setSequence( new Sequence() );
1514                         }
1515                         n.getNodeData().getSequence().setSymbol( name );
1516                         break;
1517                     case SEQUENCE_NAME:
1518                         n.setName( "" );
1519                         if ( !n.getNodeData().isHasSequence() ) {
1520                             n.getNodeData().setSequence( new Sequence() );
1521                         }
1522                         n.getNodeData().getSequence().setName( name );
1523                         break;
1524                     case TAXONOMY_ID_UNIPROT_1: {
1525                         if ( !n.getNodeData().isHasTaxonomy() ) {
1526                             n.getNodeData().setTaxonomy( new Taxonomy() );
1527                         }
1528                         String id = name;
1529                         final int i = name.indexOf( '_' );
1530                         if ( i > 0 ) {
1531                             id = name.substring( 0, i );
1532                         }
1533                         else {
1534                             n.setName( "" );
1535                         }
1536                         n.getNodeData().getTaxonomy()
1537                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1538                         break;
1539                     }
1540                     case TAXONOMY_ID_UNIPROT_2: {
1541                         if ( !n.getNodeData().isHasTaxonomy() ) {
1542                             n.getNodeData().setTaxonomy( new Taxonomy() );
1543                         }
1544                         String id = name;
1545                         final int i = name.indexOf( '_' );
1546                         if ( i > 0 ) {
1547                             id = name.substring( i + 1, name.length() );
1548                         }
1549                         else {
1550                             n.setName( "" );
1551                         }
1552                         n.getNodeData().getTaxonomy()
1553                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1554                         break;
1555                     }
1556                     case TAXONOMY_ID: {
1557                         if ( !n.getNodeData().isHasTaxonomy() ) {
1558                             n.getNodeData().setTaxonomy( new Taxonomy() );
1559                         }
1560                         n.getNodeData().getTaxonomy().setIdentifier( new Identifier( name ) );
1561                         break;
1562                     }
1563                 }
1564             }
1565         }
1566     }
1567
1568     static double addPhylogenyDistances( final double a, final double b ) {
1569         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {
1570             return a + b;
1571         }
1572         else if ( a >= 0.0 ) {
1573             return a;
1574         }
1575         else if ( b >= 0.0 ) {
1576             return b;
1577         }
1578         return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
1579     }
1580
1581     static double calculateDistanceToAncestor( final PhylogenyNode anc, PhylogenyNode desc ) {
1582         double d = 0;
1583         boolean all_default = true;
1584         while ( anc != desc ) {
1585             if ( desc.getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
1586                 d += desc.getDistanceToParent();
1587                 if ( all_default ) {
1588                     all_default = false;
1589                 }
1590             }
1591             desc = desc.getParent();
1592         }
1593         if ( all_default ) {
1594             return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
1595         }
1596         return d;
1597     }
1598
1599     /**
1600      * Deep copies the phylogeny originating from this node.
1601      */
1602     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
1603         if ( source == null ) {
1604             return null;
1605         }
1606         else {
1607             final PhylogenyNode newnode = source.copyNodeData();
1608             if ( !source.isExternal() ) {
1609                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1610                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
1611                 }
1612             }
1613             return newnode;
1614         }
1615     }
1616
1617     /**
1618      * Shallow copies the phylogeny originating from this node.
1619      */
1620     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
1621         if ( source == null ) {
1622             return null;
1623         }
1624         else {
1625             final PhylogenyNode newnode = source.copyNodeDataShallow();
1626             if ( !source.isExternal() ) {
1627                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1628                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
1629                 }
1630             }
1631             return newnode;
1632         }
1633     }
1634
1635     /**
1636      * Calculates the distance between PhylogenyNodes n1 and n2.
1637      * PRECONDITION: n1 is a descendant of n2.
1638      *
1639      * @param n1
1640      *            a descendant of n2
1641      * @param n2
1642      * @return distance between n1 and n2
1643      */
1644     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
1645         double d = 0.0;
1646         while ( n1 != n2 ) {
1647             if ( n1.getDistanceToParent() > 0.0 ) {
1648                 d += n1.getDistanceToParent();
1649             }
1650             n1 = n1.getParent();
1651         }
1652         return d;
1653     }
1654
1655     private static boolean match( final String s,
1656                                   final String query,
1657                                   final boolean case_sensitive,
1658                                   final boolean partial ) {
1659         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
1660             return false;
1661         }
1662         String my_s = s.trim();
1663         String my_query = query.trim();
1664         if ( !case_sensitive ) {
1665             my_s = my_s.toLowerCase();
1666             my_query = my_query.toLowerCase();
1667         }
1668         if ( partial ) {
1669             return my_s.indexOf( my_query ) >= 0;
1670         }
1671         else {
1672             return my_s.equals( my_query );
1673         }
1674     }
1675
1676     public static enum DESCENDANT_SORT_PRIORITY {
1677         TAXONOMY, SEQUENCE, NODE_NAME;
1678     }
1679
1680     public static enum PhylogenyNodeField {
1681         CLADE_NAME,
1682         TAXONOMY_CODE,
1683         TAXONOMY_SCIENTIFIC_NAME,
1684         TAXONOMY_COMMON_NAME,
1685         SEQUENCE_SYMBOL,
1686         SEQUENCE_NAME,
1687         TAXONOMY_ID_UNIPROT_1,
1688         TAXONOMY_ID_UNIPROT_2,
1689         TAXONOMY_ID;
1690     }
1691 }