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

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