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