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