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