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