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