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