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