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