forester/java/src/org/forester/phylogeny/PhylogenyMethods.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.phylogeny;
  27
  28 import java.awt.Color;
  29 import java.io.File;
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collections;
  34 import java.util.Comparator;
  35 import java.util.HashSet;
  36 import java.util.Iterator;
  37 import java.util.List;
  38 import java.util.Set;
  39 import java.util.SortedMap;
  40 import java.util.TreeMap;
  41
  42 import org.forester.io.parsers.PhylogenyParser;
  43 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  44 import org.forester.io.parsers.phyloxml.PhyloXmlUtil;
  45 import org.forester.io.parsers.util.PhylogenyParserException;
  46 import org.forester.phylogeny.data.BranchColor;
  47 import org.forester.phylogeny.data.BranchWidth;
  48 import org.forester.phylogeny.data.Confidence;
  49 import org.forester.phylogeny.data.DomainArchitecture;
  50 import org.forester.phylogeny.data.Event;
  51 import org.forester.phylogeny.data.Identifier;
  52 import org.forester.phylogeny.data.PhylogenyDataUtil;
  53 import org.forester.phylogeny.data.Sequence;
  54 import org.forester.phylogeny.data.Taxonomy;
  55 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  56 import org.forester.phylogeny.factories.PhylogenyFactory;
  57 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  58 import org.forester.util.BasicDescriptiveStatistics;
  59 import org.forester.util.DescriptiveStatistics;
  60 import org.forester.util.FailedConditionCheckException;
  61 import org.forester.util.ForesterUtil;
  62
  63 public class PhylogenyMethods {
  64
  65     private static PhylogenyMethods _instance   = null;
  66     private PhylogenyNode           _farthest_1 = null;
  67     private PhylogenyNode           _farthest_2 = null;
  68
  69     private PhylogenyMethods() {
  70         // Hidden constructor.
  71     }
  72
  73     /**
  74      * Calculates the distance between PhylogenyNodes node1 and node2.
  75      *
  76      *
  77      * @param node1
  78      * @param node2
  79      * @return distance between node1 and node2
  80      */
  81     public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) {
  82         final PhylogenyNode lca =calculateLCA( node1, node2 );
  83         final PhylogenyNode n1 = node1;
  84         final PhylogenyNode n2 = node2;
  85         return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) );
  86     }
  87
  88     public double calculateFurthestDistance( final Phylogeny phylogeny ) {
  89         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
  90             return 0.0;
  91         }
  92         _farthest_1 = null;
  93         _farthest_2 = null;
  94         PhylogenyNode node_1 = null;
  95         PhylogenyNode node_2 = null;
  96         double farthest_d = -Double.MAX_VALUE;
  97         final PhylogenyMethods methods = PhylogenyMethods.getInstance();
  98         final List<PhylogenyNode> ext_nodes = phylogeny.getRoot().getAllExternalDescendants();
  99         for( int i = 1; i < ext_nodes.size(); ++i ) {
 100             for( int j = 0; j < i; ++j ) {
 101                 final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) );
 102                 if ( d < 0.0 ) {
 103                     throw new RuntimeException( "distance cannot be negative" );
 104                 }
 105                 if ( d > farthest_d ) {
 106                     farthest_d = d;
 107                     node_1 = ext_nodes.get( i );
 108                     node_2 = ext_nodes.get( j );
 109                 }
 110             }
 111         }
 112         _farthest_1 = node_1;
 113         _farthest_2 = node_2;
 114         return farthest_d;
 115     }
 116
 117     final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) {
 118         return calculateLCA( n1, n2 ).getNodeData().getEvent();
 119     }
 120
 121     @Override
 122     public Object clone() throws CloneNotSupportedException {
 123         throw new CloneNotSupportedException();
 124     }
 125
 126     public PhylogenyNode getFarthestNode1() {
 127         return _farthest_1;
 128     }
 129
 130     public PhylogenyNode getFarthestNode2() {
 131         return _farthest_2;
 132     }
 133
 134     final public static void deleteNonOrthologousExternalNodes( final Phylogeny phy, final PhylogenyNode n ) {
 135         if ( n.isInternal() ) {
 136             throw new IllegalArgumentException( "node is not external" );
 137         }
 138         final ArrayList<PhylogenyNode> to_delete = new ArrayList<PhylogenyNode>();
 139         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 140             final PhylogenyNode i = it.next();
 141             if ( !PhylogenyMethods.getEventAtLCA( n, i ).isSpeciation() ) {
 142                 to_delete.add( i );
 143             }
 144         }
 145         for( final PhylogenyNode d : to_delete ) {
 146             phy.deleteSubtree( d, true );
 147         }
 148         phy.clearHashIdToNodeMap();
 149         phy.externalNodesHaveChanged();
 150     }
 151
 152     /**
 153      * Returns the LCA of PhylogenyNodes node1 and node2.
 154      *
 155      *
 156      * @param node1
 157      * @param node2
 158      * @return LCA of node1 and node2
 159      */
 160     public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) {
 161         if ( node1 == node2 ) {
 162             return node1;
 163         }
 164         if (( node1.getParent() == node2.getParent() ) /*&& node1.getParent() != null */ ) {
 165             return node1.getParent();
 166         }
 167         int depth1 = node1.calculateDepth() ;
 168         int depth2 = node2.calculateDepth() ;
 169         while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) {
 170             if ( depth1 > depth2 ) {
 171                 node1 = node1.getParent();
 172                 depth1--;
 173             }
 174             else if ( depth2 > depth1 ) {
 175                 node2 = node2.getParent();
 176                 depth2--;
 177             }
 178             else {
 179                 if ( node1 == node2 ) {
 180                     return node1;
 181                 }
 182                 node1 = node1.getParent();
 183                 node2 = node2.getParent();
 184                 depth1--;
 185                 depth2--;
 186             }
 187         }
 188         throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" );
 189     }
 190
 191     /**
 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 static boolean isAreOrthologous( final PhylogenyNode node1, final PhylogenyNode node2 ) {
 218         return !calculateLCA( 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 short calculateMaxBranchesToLeaf( final PhylogenyNode node ) {
 568         if ( node.isExternal() ) {
 569             return 0;
 570         }
 571         short max = 0;
 572         for( PhylogenyNode d : node.getAllExternalDescendants() ) {
 573             short steps = 0;
 574             while ( d != node ) {
 575                 if ( d.isCollapse() ) {
 576                     steps = 0;
 577                 }
 578                 else {
 579                     steps++;
 580                 }
 581                 d = d.getParent();
 582             }
 583             if ( max < steps ) {
 584                 max = steps;
 585             }
 586         }
 587         return max;
 588     }
 589
 590     public static int calculateMaxDepth( final Phylogeny phy ) {
 591         int max = 0;
 592         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 593             final PhylogenyNode node = iter.next();
 594             final int steps = node.calculateDepth();
 595             if ( steps > max ) {
 596                 max = steps;
 597             }
 598         }
 599         return max;
 600     }
 601
 602     public static double calculateMaxDistanceToRoot( final Phylogeny phy ) {
 603         double max = 0.0;
 604         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 605             final PhylogenyNode node = iter.next();
 606             final double d = node.calculateDistanceToRoot();
 607             if ( d > max ) {
 608                 max = d;
 609             }
 610         }
 611         return max;
 612     }
 613
 614     public static int countNumberOfPolytomies( final Phylogeny phy ) {
 615         int count = 0;
 616         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 617             final PhylogenyNode n = iter.next();
 618             if ( !n.isExternal() && ( n.getNumberOfDescendants() > 2 ) ) {
 619                 count++;
 620             }
 621         }
 622         return count;
 623     }
 624
 625     public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) {
 626         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 627         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 628             final PhylogenyNode n = iter.next();
 629             if ( !n.isExternal() ) {
 630                 stats.addValue( n.getNumberOfDescendants() );
 631             }
 632         }
 633         return stats;
 634     }
 635
 636     public static DescriptiveStatistics calculatBranchLengthStatistics( final Phylogeny phy ) {
 637         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 638         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 639             final PhylogenyNode n = iter.next();
 640             if ( !n.isRoot() && ( n.getDistanceToParent() >= 0.0 ) ) {
 641                 stats.addValue( n.getDistanceToParent() );
 642             }
 643         }
 644         return stats;
 645     }
 646
 647     public static List<DescriptiveStatistics> calculatConfidenceStatistics( final Phylogeny phy ) {
 648         final List<DescriptiveStatistics> stats = new ArrayList<DescriptiveStatistics>();
 649         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 650             final PhylogenyNode n = iter.next();
 651             if ( !n.isExternal() && !n.isRoot() ) {
 652                 if ( n.getBranchData().isHasConfidences() ) {
 653                     for( int i = 0; i < n.getBranchData().getConfidences().size(); ++i ) {
 654                         final Confidence c = n.getBranchData().getConfidences().get( i );
 655                         if ( ( i > ( stats.size() - 1 ) ) || ( stats.get( i ) == null ) ) {
 656                             stats.add( i, new BasicDescriptiveStatistics() );
 657                         }
 658                         if ( !ForesterUtil.isEmpty( c.getType() ) ) {
 659                             if ( !ForesterUtil.isEmpty( stats.get( i ).getDescription() ) ) {
 660                                 if ( !stats.get( i ).getDescription().equalsIgnoreCase( c.getType() ) ) {
 661                                     throw new IllegalArgumentException( "support values in node [" + n.toString()
 662                                             + "] appear inconsistently ordered" );
 663                                 }
 664                             }
 665                             stats.get( i ).setDescription( c.getType() );
 666                         }
 667                         stats.get( i ).addValue( ( ( c != null ) && ( c.getValue() >= 0 ) ) ? c.getValue() : 0 );
 668                     }
 669                 }
 670             }
 671         }
 672         return stats;
 673     }
 674
 675     /**
 676      * Returns the set of distinct taxonomies of
 677      * all external nodes of node.
 678      * If at least one the external nodes has no taxonomy,
 679      * null is returned.
 680      *
 681      */
 682     public static Set<Taxonomy> obtainDistinctTaxonomies( final PhylogenyNode node ) {
 683         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 684         final Set<Taxonomy> tax_set = new HashSet<Taxonomy>();
 685         for( final PhylogenyNode n : descs ) {
 686             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 687                 return null;
 688             }
 689             tax_set.add( n.getNodeData().getTaxonomy() );
 690         }
 691         return tax_set;
 692     }
 693
 694     /**
 695      * Returns a map of distinct taxonomies of
 696      * all external nodes of node.
 697      * If at least one of the external nodes has no taxonomy,
 698      * null is returned.
 699      *
 700      */
 701     public static SortedMap<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 702         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 703         final SortedMap<Taxonomy, Integer> tax_map = new TreeMap<Taxonomy, Integer>();
 704         for( final PhylogenyNode n : descs ) {
 705             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 706                 return null;
 707             }
 708             final Taxonomy t = n.getNodeData().getTaxonomy();
 709             if ( tax_map.containsKey( t ) ) {
 710                 tax_map.put( t, tax_map.get( t ) + 1 );
 711             }
 712             else {
 713                 tax_map.put( t, 1 );
 714             }
 715         }
 716         return tax_map;
 717     }
 718
 719     public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) {
 720         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 721         int x = 0;
 722         for( final PhylogenyNode n : descs ) {
 723             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 724                 x++;
 725             }
 726         }
 727         return x;
 728     }
 729
 730     /**
 731      * Deep copies the phylogeny originating from this node.
 732      */
 733     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
 734         if ( source == null ) {
 735             return null;
 736         }
 737         else {
 738             final PhylogenyNode newnode = source.copyNodeData();
 739             if ( !source.isExternal() ) {
 740                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 741                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
 742                 }
 743             }
 744             return newnode;
 745         }
 746     }
 747
 748     /**
 749      * Shallow copies the phylogeny originating from this node.
 750      */
 751     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
 752         if ( source == null ) {
 753             return null;
 754         }
 755         else {
 756             final PhylogenyNode newnode = source.copyNodeDataShallow();
 757             if ( !source.isExternal() ) {
 758                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 759                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
 760                 }
 761             }
 762             return newnode;
 763         }
 764     }
 765
 766     public static void deleteExternalNodesNegativeSelection( final Set<Integer> to_delete, final Phylogeny phy ) {
 767         phy.clearHashIdToNodeMap();
 768         for( final Integer id : to_delete ) {
 769             phy.deleteSubtree( phy.getNode( id ), true );
 770         }
 771         phy.clearHashIdToNodeMap();
 772         phy.externalNodesHaveChanged();
 773     }
 774
 775     public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p )
 776             throws IllegalArgumentException {
 777         for( final String element : node_names_to_delete ) {
 778             if ( ForesterUtil.isEmpty( element ) ) {
 779                 continue;
 780             }
 781             List<PhylogenyNode> nodes = null;
 782             nodes = p.getNodes( element );
 783             final Iterator<PhylogenyNode> it = nodes.iterator();
 784             while ( it.hasNext() ) {
 785                 final PhylogenyNode n = it.next();
 786                 if ( !n.isExternal() ) {
 787                     throw new IllegalArgumentException( "attempt to delete non-external node \"" + element + "\"" );
 788                 }
 789                 p.deleteSubtree( n, true );
 790             }
 791         }
 792         p.clearHashIdToNodeMap();
 793         p.externalNodesHaveChanged();
 794     }
 795
 796     public static void deleteExternalNodesPositiveSelection( final Set<Taxonomy> species_to_keep, final Phylogeny phy ) {
 797         //   final Set<Integer> to_delete = new HashSet<Integer>();
 798         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 799             final PhylogenyNode n = it.next();
 800             if ( n.getNodeData().isHasTaxonomy() ) {
 801                 if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) {
 802                     //to_delete.add( n.getNodeId() );
 803                     phy.deleteSubtree( n, true );
 804                 }
 805             }
 806             else {
 807                 throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" );
 808             }
 809         }
 810         phy.clearHashIdToNodeMap();
 811         phy.externalNodesHaveChanged();
 812     }
 813
 814     public static List<String> deleteExternalNodesPositiveSelection( final String[] node_names_to_keep,
 815                                                                      final Phylogeny p ) {
 816         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 817         final String[] to_delete = new String[ p.getNumberOfExternalNodes() ];
 818         int i = 0;
 819         Arrays.sort( node_names_to_keep );
 820         while ( it.hasNext() ) {
 821             final String curent_name = it.next().getName();
 822             if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) {
 823                 to_delete[ i++ ] = curent_name;
 824             }
 825         }
 826         PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p );
 827         final List<String> deleted = new ArrayList<String>();
 828         for( final String n : to_delete ) {
 829             if ( !ForesterUtil.isEmpty( n ) ) {
 830                 deleted.add( n );
 831             }
 832         }
 833         return deleted;
 834     }
 835
 836     public static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 837         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 838         final Set<Integer> encountered = new HashSet<Integer>();
 839         if ( !node.isExternal() ) {
 840             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 841             for( PhylogenyNode current : exts ) {
 842                 descs.add( current );
 843                 while ( current != node ) {
 844                     current = current.getParent();
 845                     if ( encountered.contains( current.getId() ) ) {
 846                         continue;
 847                     }
 848                     descs.add( current );
 849                     encountered.add( current.getId() );
 850                 }
 851             }
 852         }
 853         return descs;
 854     }
 855
 856     /**
 857      *
 858      * Convenience method
 859      *
 860      * @param node
 861      * @return
 862      */
 863     public static Color getBranchColorValue( final PhylogenyNode node ) {
 864         if ( node.getBranchData().getBranchColor() == null ) {
 865             return null;
 866         }
 867         return node.getBranchData().getBranchColor().getValue();
 868     }
 869
 870     /**
 871      * Convenience method
 872      */
 873     public static double getBranchWidthValue( final PhylogenyNode node ) {
 874         if ( !node.getBranchData().isHasBranchWidth() ) {
 875             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 876         }
 877         return node.getBranchData().getBranchWidth().getValue();
 878     }
 879
 880     /**
 881      * Convenience method
 882      */
 883     public static double getConfidenceValue( final PhylogenyNode node ) {
 884         if ( !node.getBranchData().isHasConfidences() ) {
 885             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 886         }
 887         return node.getBranchData().getConfidence( 0 ).getValue();
 888     }
 889
 890     /**
 891      * Convenience method
 892      */
 893     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 894         if ( !node.getBranchData().isHasConfidences() ) {
 895             return new double[ 0 ];
 896         }
 897         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 898         int i = 0;
 899         for( final Confidence c : node.getBranchData().getConfidences() ) {
 900             values[ i++ ] = c.getValue();
 901         }
 902         return values;
 903     }
 904
 905     /**
 906      * Calculates the distance between PhylogenyNodes n1 and n2.
 907      * PRECONDITION: n1 is a descendant of n2.
 908      *
 909      * @param n1
 910      *            a descendant of n2
 911      * @param n2
 912      * @return distance between n1 and n2
 913      */
 914     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
 915         double d = 0.0;
 916         while ( n1 != n2 ) {
 917             if ( n1.getDistanceToParent() > 0.0 ) {
 918                 d += n1.getDistanceToParent();
 919             }
 920             n1 = n1.getParent();
 921         }
 922         return d;
 923     }
 924
 925     /**
 926      * Returns taxonomy t if all external descendants have
 927      * the same taxonomy t, null otherwise.
 928      *
 929      */
 930     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 931         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 932         Taxonomy tax = null;
 933         for( final PhylogenyNode n : descs ) {
 934             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 935                 return null;
 936             }
 937             else if ( tax == null ) {
 938                 tax = n.getNodeData().getTaxonomy();
 939             }
 940             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 941                 return null;
 942             }
 943         }
 944         return tax;
 945     }
 946
 947     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 948         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 949         PhylogenyNode farthest = null;
 950         double longest = -Double.MAX_VALUE;
 951         for( final PhylogenyNode child : children ) {
 952             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 953                 farthest = child;
 954                 longest = PhylogenyMethods.getDistance( child, node );
 955             }
 956         }
 957         return farthest;
 958     }
 959
 960     public static PhylogenyMethods getInstance() {
 961         if ( PhylogenyMethods._instance == null ) {
 962             PhylogenyMethods._instance = new PhylogenyMethods();
 963         }
 964         return PhylogenyMethods._instance;
 965     }
 966
 967     /**
 968      * Returns the largest confidence value found on phy.
 969      */
 970     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 971         double max = -Double.MAX_VALUE;
 972         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 973             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 974             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 975                 max = s;
 976             }
 977         }
 978         return max;
 979     }
 980
 981     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 982         int min = Integer.MAX_VALUE;
 983         int d = 0;
 984         PhylogenyNode n;
 985         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 986             n = it.next();
 987             if ( n.isInternal() ) {
 988                 d = n.getNumberOfDescendants();
 989                 if ( d < min ) {
 990                     min = d;
 991                 }
 992             }
 993         }
 994         return min;
 995     }
 996
 997     /**
 998      * Convenience method for display purposes.
 999      * Not intended for algorithms.
1000      */
1001     public static String getSpecies( final PhylogenyNode node ) {
1002         if ( !node.getNodeData().isHasTaxonomy() ) {
1003             return "";
1004         }
1005         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
1006             return node.getNodeData().getTaxonomy().getScientificName();
1007         }
1008         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1009             return node.getNodeData().getTaxonomy().getTaxonomyCode();
1010         }
1011         else {
1012             return node.getNodeData().getTaxonomy().getCommonName();
1013         }
1014     }
1015
1016     /**
1017      * Returns all Nodes which are connected to external PhylogenyNode n of this
1018      * Phylogeny by a path containing only speciation events. We call these
1019      * "super orthologs". Nodes are returned as Vector of references to Nodes.
1020      * <p>
1021      * PRECONDITION: This tree must be binary and rooted, and speciation -
1022      * duplication need to be assigned for each of its internal Nodes.
1023      * <p>
1024      * Returns null if this Phylogeny is empty or if n is internal.
1025      * @param n
1026      *            external PhylogenyNode whose strictly speciation related Nodes
1027      *            are to be returned
1028      * @return Vector of references to all strictly speciation related Nodes of
1029      *         PhylogenyNode n of this Phylogeny, null if this Phylogeny is
1030      *         empty or if n is internal
1031      */
1032     public static List<PhylogenyNode> getSuperOrthologousNodes( final PhylogenyNode n ) {
1033         // FIXME
1034         PhylogenyNode node = n, deepest = null;
1035         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
1036         if ( !node.isExternal() ) {
1037             return null;
1038         }
1039         while ( !node.isRoot() && !node.getParent().isDuplication() ) {
1040             node = node.getParent();
1041         }
1042         deepest = node;
1043         deepest.setIndicatorsToZero();
1044         do {
1045             if ( !node.isExternal() ) {
1046                 if ( node.getIndicator() == 0 ) {
1047                     node.setIndicator( ( byte ) 1 );
1048                     if ( !node.isDuplication() ) {
1049                         node = node.getChildNode1();
1050                     }
1051                 }
1052                 if ( node.getIndicator() == 1 ) {
1053                     node.setIndicator( ( byte ) 2 );
1054                     if ( !node.isDuplication() ) {
1055                         node = node.getChildNode2();
1056                     }
1057                 }
1058                 if ( ( node != deepest ) && ( node.getIndicator() == 2 ) ) {
1059                     node = node.getParent();
1060                 }
1061             }
1062             else {
1063                 if ( node != n ) {
1064                     v.add( node );
1065                 }
1066                 if ( node != deepest ) {
1067                     node = node.getParent();
1068                 }
1069                 else {
1070                     node.setIndicator( ( byte ) 2 );
1071                 }
1072             }
1073         } while ( ( node != deepest ) || ( deepest.getIndicator() != 2 ) );
1074         return v;
1075     }
1076
1077     /**
1078      * Convenience method for display purposes.
1079      * Not intended for algorithms.
1080      */
1081     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
1082         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
1083             return "";
1084         }
1085         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
1086     }
1087
1088     /**
1089      * Returns all Nodes which are connected to external PhylogenyNode n of this
1090      * Phylogeny by a path containing, and leading to, only duplication events.
1091      * We call these "ultra paralogs". Nodes are returned as Vector of
1092      * references to Nodes.
1093      * <p>
1094      * PRECONDITION: This tree must be binary and rooted, and speciation -
1095      * duplication need to be assigned for each of its internal Nodes.
1096      * <p>
1097      * Returns null if this Phylogeny is empty or if n is internal.
1098      * <p>
1099      * (Last modified: 10/06/01)
1100      *
1101      * @param n
1102      *            external PhylogenyNode whose ultra paralogs are to be returned
1103      * @return Vector of references to all ultra paralogs of PhylogenyNode n of
1104      *         this Phylogeny, null if this Phylogeny is empty or if n is
1105      *         internal
1106      */
1107     public static List<PhylogenyNode> getUltraParalogousNodes( final PhylogenyNode n ) {
1108         // FIXME test me
1109         PhylogenyNode node = n;
1110         if ( !node.isExternal() ) {
1111             return null;
1112         }
1113         while ( !node.isRoot() && node.getParent().isDuplication() && areAllChildrenDuplications( node.getParent() ) ) {
1114             node = node.getParent();
1115         }
1116         final List<PhylogenyNode> nodes = node.getAllExternalDescendants();
1117         nodes.remove( n );
1118         return nodes;
1119     }
1120
1121     public static String inferCommonPartOfScientificNameOfDescendants( final PhylogenyNode node ) {
1122         final List<PhylogenyNode> descs = node.getDescendants();
1123         String sn = null;
1124         for( final PhylogenyNode n : descs ) {
1125             if ( !n.getNodeData().isHasTaxonomy()
1126                     || ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
1127                 return null;
1128             }
1129             else if ( sn == null ) {
1130                 sn = n.getNodeData().getTaxonomy().getScientificName().trim();
1131             }
1132             else {
1133                 String sn_current = n.getNodeData().getTaxonomy().getScientificName().trim();
1134                 if ( !sn.equals( sn_current ) ) {
1135                     boolean overlap = false;
1136                     while ( ( sn.indexOf( ' ' ) >= 0 ) || ( sn_current.indexOf( ' ' ) >= 0 ) ) {
1137                         if ( ForesterUtil.countChars( sn, ' ' ) > ForesterUtil.countChars( sn_current, ' ' ) ) {
1138                             sn = sn.substring( 0, sn.lastIndexOf( ' ' ) ).trim();
1139                         }
1140                         else {
1141                             sn_current = sn_current.substring( 0, sn_current.lastIndexOf( ' ' ) ).trim();
1142                         }
1143                         if ( sn.equals( sn_current ) ) {
1144                             overlap = true;
1145                             break;
1146                         }
1147                     }
1148                     if ( !overlap ) {
1149                         return null;
1150                     }
1151                 }
1152             }
1153         }
1154         return sn;
1155     }
1156
1157     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
1158         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
1159             if ( node.getChildNode( i ).isExternal() ) {
1160                 return true;
1161             }
1162         }
1163         return false;
1164     }
1165
1166     /*
1167      * This is case insensitive.
1168      *
1169      */
1170     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
1171                                                                                final String[] providers ) {
1172         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
1173             final String my_tax_prov = tax.getIdentifier().getProvider();
1174             for( final String provider : providers ) {
1175                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
1176                     return true;
1177                 }
1178             }
1179             return false;
1180         }
1181         else {
1182             return false;
1183         }
1184     }
1185
1186     private static boolean match( final String s,
1187                                   final String query,
1188                                   final boolean case_sensitive,
1189                                   final boolean partial ) {
1190         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
1191             return false;
1192         }
1193         String my_s = s.trim();
1194         String my_query = query.trim();
1195         if ( !case_sensitive ) {
1196             my_s = my_s.toLowerCase();
1197             my_query = my_query.toLowerCase();
1198         }
1199         if ( partial ) {
1200             return my_s.indexOf( my_query ) >= 0;
1201         }
1202         else {
1203             return my_s.equals( my_query );
1204         }
1205     }
1206
1207     public static void midpointRoot( final Phylogeny phylogeny ) {
1208         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
1209             return;
1210         }
1211         final PhylogenyMethods methods = getInstance();
1212         final double farthest_d = methods.calculateFurthestDistance( phylogeny );
1213         final PhylogenyNode f1 = methods.getFarthestNode1();
1214         final PhylogenyNode f2 = methods.getFarthestNode2();
1215         if ( farthest_d <= 0.0 ) {
1216             return;
1217         }
1218         double x = farthest_d / 2.0;
1219         PhylogenyNode n = f1;
1220         if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny
1221                 .getRoot() ) ) {
1222             n = f2;
1223         }
1224         while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) {
1225             x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
1226             n = n.getParent();
1227         }
1228         phylogeny.reRoot( n, x );
1229         phylogeny.recalculateNumberOfExternalDescendants( true );
1230         final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() );
1231         final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() );
1232         final double da = getDistance( a, phylogeny.getRoot() );
1233         final double db = getDistance( b, phylogeny.getRoot() );
1234         if ( Math.abs( da - db ) > 0.000001 ) {
1235             throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed:  da="
1236                     + da + ",  db=" + db + ",  diff=" + Math.abs( da - db ) );
1237         }
1238     }
1239
1240     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
1241                                                  final double max_bootstrap_value,
1242                                                  final double max_normalized_value ) {
1243         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
1244             final PhylogenyNode node = iter.next();
1245             if ( node.isInternal() ) {
1246                 final double confidence = getConfidenceValue( node );
1247                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
1248                     if ( confidence >= max_bootstrap_value ) {
1249                         setBootstrapConfidence( node, max_normalized_value );
1250                     }
1251                     else {
1252                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
1253                     }
1254                 }
1255             }
1256         }
1257     }
1258
1259     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
1260         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1261         if ( phy.isEmpty() ) {
1262             return nodes;
1263         }
1264         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1265             nodes.add( iter.next() );
1266         }
1267         return nodes;
1268     }
1269
1270     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
1271         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
1272             final PhylogenyNode node = iter.next();
1273             double red = 0.0;
1274             double green = 0.0;
1275             double blue = 0.0;
1276             int n = 0;
1277             if ( node.isInternal() ) {
1278                 //for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
1279                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
1280                     final PhylogenyNode child_node = node.getChildNode( i );
1281                     final Color child_color = getBranchColorValue( child_node );
1282                     if ( child_color != null ) {
1283                         ++n;
1284                         red += child_color.getRed();
1285                         green += child_color.getGreen();
1286                         blue += child_color.getBlue();
1287                     }
1288                 }
1289                 setBranchColorValue( node,
1290                                      new Color( ForesterUtil.roundToInt( red / n ),
1291                                                 ForesterUtil.roundToInt( green / n ),
1292                                                 ForesterUtil.roundToInt( blue / n ) ) );
1293             }
1294         }
1295     }
1296
1297     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
1298         if ( remove_me.isRoot() ) {
1299             throw new IllegalArgumentException( "ill advised attempt to remove root node" );
1300         }
1301         if ( remove_me.isExternal() ) {
1302             phylogeny.deleteSubtree( remove_me, false );
1303             phylogeny.clearHashIdToNodeMap();
1304             phylogeny.externalNodesHaveChanged();
1305         }
1306         else {
1307             final PhylogenyNode parent = remove_me.getParent();
1308             final List<PhylogenyNode> descs = remove_me.getDescendants();
1309             parent.removeChildNode( remove_me );
1310             for( final PhylogenyNode desc : descs ) {
1311                 parent.addAsChild( desc );
1312                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
1313                                                                  desc.getDistanceToParent() ) );
1314             }
1315             remove_me.setParent( null );
1316             phylogeny.clearHashIdToNodeMap();
1317             phylogeny.externalNodesHaveChanged();
1318         }
1319     }
1320
1321     public static List<PhylogenyNode> searchData( final String query,
1322                                                   final Phylogeny phy,
1323                                                   final boolean case_sensitive,
1324                                                   final boolean partial,
1325                                                   final boolean search_domains ) {
1326         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1327         if ( phy.isEmpty() || ( query == null ) ) {
1328             return nodes;
1329         }
1330         if ( ForesterUtil.isEmpty( query ) ) {
1331             return nodes;
1332         }
1333         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1334             final PhylogenyNode node = iter.next();
1335             boolean match = false;
1336             if ( match( node.getName(), query, case_sensitive, partial ) ) {
1337                 match = true;
1338             }
1339             else if ( node.getNodeData().isHasTaxonomy()
1340                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1341                 match = true;
1342             }
1343             else if ( node.getNodeData().isHasTaxonomy()
1344                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1345                 match = true;
1346             }
1347             else if ( node.getNodeData().isHasTaxonomy()
1348                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1349                 match = true;
1350             }
1351             else if ( node.getNodeData().isHasTaxonomy()
1352                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1353                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1354                               query,
1355                               case_sensitive,
1356                               partial ) ) {
1357                 match = true;
1358             }
1359             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1360                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1361                 I: for( final String syn : syns ) {
1362                     if ( match( syn, query, case_sensitive, partial ) ) {
1363                         match = true;
1364                         break I;
1365                     }
1366                 }
1367             }
1368             if ( !match && node.getNodeData().isHasSequence()
1369                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1370                 match = true;
1371             }
1372             if ( !match && node.getNodeData().isHasSequence()
1373                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1374                 match = true;
1375             }
1376             if ( !match
1377                     && node.getNodeData().isHasSequence()
1378                     && ( node.getNodeData().getSequence().getAccession() != null )
1379                     && match( node.getNodeData().getSequence().getAccession().getValue(),
1380                               query,
1381                               case_sensitive,
1382                               partial ) ) {
1383                 match = true;
1384             }
1385             if ( search_domains && !match && node.getNodeData().isHasSequence()
1386                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1387                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1388                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1389                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1390                         match = true;
1391                         break I;
1392                     }
1393                 }
1394             }
1395             if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1396                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1397                 I: while ( it.hasNext() ) {
1398                     if ( match( it.next(), query, case_sensitive, partial ) ) {
1399                         match = true;
1400                         break I;
1401                     }
1402                 }
1403                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1404                 I: while ( it.hasNext() ) {
1405                     if ( match( it.next(), query, case_sensitive, partial ) ) {
1406                         match = true;
1407                         break I;
1408                     }
1409                 }
1410             }
1411             if ( match ) {
1412                 nodes.add( node );
1413             }
1414         }
1415         return nodes;
1416     }
1417
1418     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
1419                                                             final Phylogeny phy,
1420                                                             final boolean case_sensitive,
1421                                                             final boolean partial,
1422                                                             final boolean search_domains ) {
1423         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1424         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
1425             return nodes;
1426         }
1427         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1428             final PhylogenyNode node = iter.next();
1429             boolean all_matched = true;
1430             for( final String query : queries ) {
1431                 boolean match = false;
1432                 if ( ForesterUtil.isEmpty( query ) ) {
1433                     continue;
1434                 }
1435                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
1436                     match = true;
1437                 }
1438                 else if ( node.getNodeData().isHasTaxonomy()
1439                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1440                     match = true;
1441                 }
1442                 else if ( node.getNodeData().isHasTaxonomy()
1443                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1444                     match = true;
1445                 }
1446                 else if ( node.getNodeData().isHasTaxonomy()
1447                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1448                     match = true;
1449                 }
1450                 else if ( node.getNodeData().isHasTaxonomy()
1451                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1452                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1453                                   query,
1454                                   case_sensitive,
1455                                   partial ) ) {
1456                     match = true;
1457                 }
1458                 else if ( node.getNodeData().isHasTaxonomy()
1459                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1460                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1461                     I: for( final String syn : syns ) {
1462                         if ( match( syn, query, case_sensitive, partial ) ) {
1463                             match = true;
1464                             break I;
1465                         }
1466                     }
1467                 }
1468                 if ( !match && node.getNodeData().isHasSequence()
1469                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1470                     match = true;
1471                 }
1472                 if ( !match && node.getNodeData().isHasSequence()
1473                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1474                     match = true;
1475                 }
1476                 if ( !match
1477                         && node.getNodeData().isHasSequence()
1478                         && ( node.getNodeData().getSequence().getAccession() != null )
1479                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1480                                   query,
1481                                   case_sensitive,
1482                                   partial ) ) {
1483                     match = true;
1484                 }
1485                 if ( search_domains && !match && node.getNodeData().isHasSequence()
1486                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1487                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1488                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1489                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1490                             match = true;
1491                             break I;
1492                         }
1493                     }
1494                 }
1495                 if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1496                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1497                     I: while ( it.hasNext() ) {
1498                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1499                             match = true;
1500                             break I;
1501                         }
1502                     }
1503                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1504                     I: while ( it.hasNext() ) {
1505                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1506                             match = true;
1507                             break I;
1508                         }
1509                     }
1510                 }
1511                 if ( !match ) {
1512                     all_matched = false;
1513                     break;
1514                 }
1515             }
1516             if ( all_matched ) {
1517                 nodes.add( node );
1518             }
1519         }
1520         return nodes;
1521     }
1522
1523     /**
1524      * Convenience method.
1525      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1526      */
1527     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1528         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1529     }
1530
1531     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1532         if ( node.getBranchData().getBranchColor() == null ) {
1533             node.getBranchData().setBranchColor( new BranchColor() );
1534         }
1535         node.getBranchData().getBranchColor().setValue( color );
1536     }
1537
1538     /**
1539      * Convenience method
1540      */
1541     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1542         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1543     }
1544
1545     /**
1546      * Convenience method.
1547      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1548      */
1549     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1550         setConfidence( node, confidence_value, "" );
1551     }
1552
1553     /**
1554      * Convenience method.
1555      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1556      */
1557     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1558         Confidence c = null;
1559         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1560             c = node.getBranchData().getConfidence( 0 );
1561         }
1562         else {
1563             c = new Confidence();
1564             node.getBranchData().addConfidence( c );
1565         }
1566         c.setType( type );
1567         c.setValue( confidence_value );
1568     }
1569
1570     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1571         if ( !node.getNodeData().isHasTaxonomy() ) {
1572             node.getNodeData().setTaxonomy( new Taxonomy() );
1573         }
1574         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1575     }
1576
1577     /**
1578      * Convenience method to set the taxonomy code of a phylogeny node.
1579      *
1580      *
1581      * @param node
1582      * @param taxonomy_code
1583      * @throws PhyloXmlDataFormatException
1584      */
1585     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code )
1586             throws PhyloXmlDataFormatException {
1587         if ( !node.getNodeData().isHasTaxonomy() ) {
1588             node.getNodeData().setTaxonomy( new Taxonomy() );
1589         }
1590         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1591     }
1592
1593     /**
1594      * Removes from Phylogeny to_be_stripped all external Nodes which are
1595      * associated with a species NOT found in Phylogeny reference.
1596      *
1597      * @param reference
1598      *            a reference Phylogeny
1599      * @param to_be_stripped
1600      *            Phylogeny to be stripped
1601      * @return number of external nodes removed from to_be_stripped
1602      */
1603     public static int taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference, final Phylogeny to_be_stripped ) {
1604         final Set<String> ref_ext_taxo = new HashSet<String>();
1605         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1606             final PhylogenyNode n = it.next();
1607             if ( !n.getNodeData().isHasTaxonomy() ) {
1608                 throw new IllegalArgumentException( "no taxonomic data in node: " + n );
1609             }
1610             //  ref_ext_taxo.add( getSpecies( n ) );
1611             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
1612                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() );
1613             }
1614             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1615                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() );
1616             }
1617         }
1618         System.out.println( "  ref_ext_tax:" );
1619         for( final String string : ref_ext_taxo ) {
1620             System.out.println( string );
1621         }
1622         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1623         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1624             final PhylogenyNode n = it.next();
1625             if ( !n.getNodeData().isHasTaxonomy() ) {
1626                 nodes_to_delete.add( n );
1627             }
1628             else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) )
1629                     && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1630                 nodes_to_delete.add( n );
1631             }
1632         }
1633         System.out.println( "  to delete:" );
1634         for( final PhylogenyNode string : nodes_to_delete ) {
1635             System.out.println( string.getNodeData().getTaxonomy().getTaxonomyCode() );
1636         }
1637         for( final PhylogenyNode phylogenyNode : nodes_to_delete ) {
1638             to_be_stripped.deleteSubtree( phylogenyNode, true );
1639         }
1640         to_be_stripped.clearHashIdToNodeMap();
1641         to_be_stripped.externalNodesHaveChanged();
1642         return nodes_to_delete.size();
1643     }
1644
1645     /**
1646      * Arranges the order of childern for each node of this Phylogeny in such a
1647      * way that either the branch with more children is on top (right) or on
1648      * bottom (left), dependent on the value of boolean order.
1649      *
1650      * @param order
1651      *            decides in which direction to order
1652      * @param pri
1653      */
1654     public static void orderAppearance( final PhylogenyNode n,
1655                                         final boolean order,
1656                                         final boolean order_ext_alphabetically,
1657                                         final DESCENDANT_SORT_PRIORITY pri ) {
1658         if ( n.isExternal() ) {
1659             return;
1660         }
1661         else {
1662             PhylogenyNode temp = null;
1663             if ( ( n.getNumberOfDescendants() == 2 )
1664                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
1665                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
1666                 temp = n.getChildNode1();
1667                 n.setChild1( n.getChildNode2() );
1668                 n.setChild2( temp );
1669             }
1670             else if ( order_ext_alphabetically ) {
1671                 boolean all_ext = true;
1672                 for( final PhylogenyNode i : n.getDescendants() ) {
1673                     if ( !i.isExternal() ) {
1674                         all_ext = false;
1675                         break;
1676                     }
1677                 }
1678                 if ( all_ext ) {
1679                     PhylogenyMethods.sortNodeDescendents( n, pri );
1680                 }
1681             }
1682             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
1683                 orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri );
1684             }
1685         }
1686     }
1687
1688     public static enum PhylogenyNodeField {
1689         CLADE_NAME,
1690         TAXONOMY_CODE,
1691         TAXONOMY_SCIENTIFIC_NAME,
1692         TAXONOMY_COMMON_NAME,
1693         SEQUENCE_SYMBOL,
1694         SEQUENCE_NAME,
1695         TAXONOMY_ID_UNIPROT_1,
1696         TAXONOMY_ID_UNIPROT_2,
1697         TAXONOMY_ID;
1698     }
1699
1700     public static enum TAXONOMY_EXTRACTION {
1701         NO, YES, PFAM_STYLE_ONLY;
1702     }
1703
1704     public static enum DESCENDANT_SORT_PRIORITY {
1705         TAXONOMY, SEQUENCE, NODE_NAME;
1706     }
1707 }