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