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