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