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