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