forester/java/src/org/forester/phylogeny/PhylogenyMethods.java

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