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.util.ArrayList;
  30 import java.util.Arrays;
  31 import java.util.HashSet;
  32 import java.util.Iterator;
  33 import java.util.List;
  34 import java.util.Set;
  35 import java.util.SortedMap;
  36 import java.util.TreeMap;
  37
  38 import org.forester.phylogeny.data.BranchColor;
  39 import org.forester.phylogeny.data.BranchWidth;
  40 import org.forester.phylogeny.data.Confidence;
  41 import org.forester.phylogeny.data.DomainArchitecture;
  42 import org.forester.phylogeny.data.Taxonomy;
  43 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  44 import org.forester.util.FailedConditionCheckException;
  45 import org.forester.util.ForesterUtil;
  46
  47 public class PhylogenyMethods {
  48
  49     private static PhylogenyMethods _instance      = null;
  50     private final Set<Integer>      _temp_hash_set = new HashSet<Integer>();
  51     private PhylogenyNode           _farthest_1    = null;
  52     private PhylogenyNode           _farthest_2    = null;
  53
  54     private PhylogenyMethods() {
  55         // Hidden constructor.
  56     }
  57
  58     /**
  59      * Calculates the distance between PhylogenyNodes node1 and node2.
  60      *
  61      *
  62      * @param node1
  63      * @param node2
  64      * @return distance between node1 and node2
  65      */
  66     public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) {
  67         final PhylogenyNode lca = obtainLCA( node1, node2 );
  68         final PhylogenyNode n1 = node1;
  69         final PhylogenyNode n2 = node2;
  70         return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) );
  71     }
  72
  73     public double calculateFurthestDistance( final Phylogeny phylogeny ) {
  74         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
  75             return 0.0;
  76         }
  77         _farthest_1 = null;
  78         _farthest_2 = null;
  79         PhylogenyNode node_1 = null;
  80         PhylogenyNode node_2 = null;
  81         double farthest_d = -Double.MAX_VALUE;
  82         final PhylogenyMethods methods = PhylogenyMethods.getInstance();
  83         final List<PhylogenyNode> ext_nodes = phylogeny.getRoot().getAllExternalDescendants();
  84         for( int i = 1; i < ext_nodes.size(); ++i ) {
  85             for( int j = 0; j < i; ++j ) {
  86                 final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) );
  87                 if ( d < 0.0 ) {
  88                     throw new RuntimeException( "distance cannot be negative" );
  89                 }
  90                 if ( d > farthest_d ) {
  91                     farthest_d = d;
  92                     node_1 = ext_nodes.get( i );
  93                     node_2 = ext_nodes.get( j );
  94                 }
  95             }
  96         }
  97         _farthest_1 = node_1;
  98         _farthest_2 = node_2;
  99         return farthest_d;
 100     }
 101
 102     @Override
 103     public Object clone() throws CloneNotSupportedException {
 104         throw new CloneNotSupportedException();
 105     }
 106
 107     public PhylogenyNode getFarthestNode1() {
 108         return _farthest_1;
 109     }
 110
 111     public PhylogenyNode getFarthestNode2() {
 112         return _farthest_2;
 113     }
 114
 115     /**
 116      * Returns the LCA of PhylogenyNodes node1 and node2.
 117      *
 118      *
 119      * @param node1
 120      * @param node2
 121      * @return LCA of node1 and node2
 122      */
 123     public PhylogenyNode obtainLCA( final PhylogenyNode node1, final PhylogenyNode node2 ) {
 124         _temp_hash_set.clear();
 125         PhylogenyNode n1 = node1;
 126         PhylogenyNode n2 = node2;
 127         _temp_hash_set.add( n1.getId() );
 128         while ( !n1.isRoot() ) {
 129             n1 = n1.getParent();
 130             _temp_hash_set.add( n1.getId() );
 131         }
 132         while ( !_temp_hash_set.contains( n2.getId() ) && !n2.isRoot() ) {
 133             n2 = n2.getParent();
 134         }
 135         if ( !_temp_hash_set.contains( n2.getId() ) ) {
 136             throw new IllegalArgumentException( "attempt to get LCA of two nodes which do not share a common root" );
 137         }
 138         return n2;
 139     }
 140
 141     /**
 142      * Returns all orthologs of the external PhylogenyNode n of this Phylogeny.
 143      * Orthologs are returned as List of node references.
 144      * <p>
 145      * PRECONDITION: This tree must be binary and rooted, and speciation -
 146      * duplication need to be assigned for each of its internal Nodes.
 147      * <p>
 148      * Returns null if this Phylogeny is empty or if n is internal.
 149      * @param n
 150      *            external PhylogenyNode whose orthologs are to be returned
 151      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 152      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 153      *         internal
 154      */
 155     public List<PhylogenyNode> getOrthologousNodes( final Phylogeny phy, final PhylogenyNode node ) {
 156         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 157         final PhylogenyNodeIterator it = phy.iteratorExternalForward();
 158         while ( it.hasNext() ) {
 159             final PhylogenyNode temp_node = it.next();
 160             if ( ( temp_node != node ) && isAreOrthologous( node, temp_node ) ) {
 161                 nodes.add( temp_node );
 162             }
 163         }
 164         return nodes;
 165     }
 166
 167     public boolean isAreOrthologous( final PhylogenyNode node1, final PhylogenyNode node2 ) {
 168         return !obtainLCA( node1, node2 ).isDuplication();
 169     }
 170
 171     static double addPhylogenyDistances( final double a, final double b ) {
 172         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {
 173             return a + b;
 174         }
 175         else if ( a >= 0.0 ) {
 176             return a;
 177         }
 178         else if ( b >= 0.0 ) {
 179             return b;
 180         }
 181         return PhylogenyNode.DISTANCE_DEFAULT;
 182     }
 183
 184     // Helper for getUltraParalogousNodes( PhylogenyNode ).
 185     public static boolean areAllChildrenDuplications( final PhylogenyNode n ) {
 186         if ( n.isExternal() ) {
 187             return false;
 188         }
 189         else {
 190             if ( n.isDuplication() ) {
 191                 //FIXME test me!
 192                 for( final PhylogenyNode desc : n.getDescendants() ) {
 193                     if ( !areAllChildrenDuplications( desc ) ) {
 194                         return false;
 195                     }
 196                 }
 197                 return true;
 198             }
 199             else {
 200                 return false;
 201             }
 202         }
 203     }
 204
 205     public static int calculateDepth( final PhylogenyNode node ) {
 206         PhylogenyNode n = node;
 207         int steps = 0;
 208         while ( !n.isRoot() ) {
 209             steps++;
 210             n = n.getParent();
 211         }
 212         return steps;
 213     }
 214
 215     public static double calculateDistanceToRoot( final PhylogenyNode node ) {
 216         PhylogenyNode n = node;
 217         double d = 0.0;
 218         while ( !n.isRoot() ) {
 219             if ( n.getDistanceToParent() > 0.0 ) {
 220                 d += n.getDistanceToParent();
 221             }
 222             n = n.getParent();
 223         }
 224         return d;
 225     }
 226
 227     public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) {
 228         if ( node.isExternal() ) {
 229             return 0;
 230         }
 231         short max = 0;
 232         for( PhylogenyNode d : node.getAllExternalDescendants() ) {
 233             short steps = 0;
 234             while ( d != node ) {
 235                 if ( d.isCollapse() ) {
 236                     steps = 0;
 237                 }
 238                 else {
 239                     steps++;
 240                 }
 241                 d = d.getParent();
 242             }
 243             if ( max < steps ) {
 244                 max = steps;
 245             }
 246         }
 247         return max;
 248     }
 249
 250     public static int calculateMaxDepth( final Phylogeny phy ) {
 251         int max = 0;
 252         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 253             final PhylogenyNode node = iter.next();
 254             final int steps = calculateDepth( node );
 255             if ( steps > max ) {
 256                 max = steps;
 257             }
 258         }
 259         return max;
 260     }
 261
 262     public static double calculateMaxDistanceToRoot( final Phylogeny phy ) {
 263         double max = 0.0;
 264         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 265             final PhylogenyNode node = iter.next();
 266             final double d = calculateDistanceToRoot( node );
 267             if ( d > max ) {
 268                 max = d;
 269             }
 270         }
 271         return max;
 272     }
 273
 274     public static int calculateMaximumNumberOfDescendantsPerNode( final Phylogeny phy ) {
 275         int max = 0;
 276         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 277             final PhylogenyNode node = iter.next();
 278             if ( node.getNumberOfDescendants() > max ) {
 279                 max = node.getNumberOfDescendants();
 280             }
 281         }
 282         return max;
 283     }
 284
 285     /**
 286      * Returns the set of distinct taxonomies of
 287      * all external nodes of node.
 288      * If at least one the external nodes has no taxonomy,
 289      * null is returned.
 290      *
 291      */
 292     public static Set<Taxonomy> obtainDistinctTaxonomies( final PhylogenyNode node ) {
 293         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 294         final Set<Taxonomy> tax_set = new HashSet<Taxonomy>();
 295         for( final PhylogenyNode n : descs ) {
 296             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 297                 return null;
 298             }
 299             tax_set.add( n.getNodeData().getTaxonomy() );
 300         }
 301         return tax_set;
 302     }
 303
 304     /**
 305      * Returns a map of distinct taxonomies of
 306      * all external nodes of node.
 307      * If at least one of the external nodes has no taxonomy,
 308      * null is returned.
 309      *
 310      */
 311     public static SortedMap<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 312         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 313         final SortedMap<Taxonomy, Integer> tax_map = new TreeMap<Taxonomy, Integer>();
 314         for( final PhylogenyNode n : descs ) {
 315             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 316                 return null;
 317             }
 318             final Taxonomy t = n.getNodeData().getTaxonomy();
 319             if ( tax_map.containsKey( t ) ) {
 320                 tax_map.put( t, tax_map.get( t ) + 1 );
 321             }
 322             else {
 323                 tax_map.put( t, 1 );
 324             }
 325         }
 326         return tax_map;
 327     }
 328
 329     public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) {
 330         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 331         int x = 0;
 332         for( final PhylogenyNode n : descs ) {
 333             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 334                 x++;
 335             }
 336         }
 337         return x;
 338     }
 339
 340     /**
 341      * Deep copies the phylogeny originating from this node.
 342      */
 343     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
 344         if ( source == null ) {
 345             return null;
 346         }
 347         else {
 348             final PhylogenyNode newnode = source.copyNodeData();
 349             if ( !source.isExternal() ) {
 350                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 351                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
 352                 }
 353             }
 354             return newnode;
 355         }
 356     }
 357
 358     /**
 359      * Shallow copies the phylogeny originating from this node.
 360      */
 361     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
 362         if ( source == null ) {
 363             return null;
 364         }
 365         else {
 366             final PhylogenyNode newnode = source.copyNodeDataShallow();
 367             if ( !source.isExternal() ) {
 368                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
 369                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
 370                 }
 371             }
 372             return newnode;
 373         }
 374     }
 375
 376     public static void deleteExternalNodesNegativeSelection( final Set<Integer> to_delete, final Phylogeny phy ) {
 377         phy.hashIDs();
 378         for( final Integer id : to_delete ) {
 379             phy.deleteSubtree( phy.getNode( id ), true );
 380         }
 381         phy.hashIDs();
 382     }
 383
 384     public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p )
 385             throws IllegalArgumentException {
 386         for( int i = 0; i < node_names_to_delete.length; ++i ) {
 387             if ( ForesterUtil.isEmpty( node_names_to_delete[ i ] ) ) {
 388                 continue;
 389             }
 390             List<PhylogenyNode> nodes = null;
 391             nodes = p.getNodes( node_names_to_delete[ i ] );
 392             final Iterator<PhylogenyNode> it = nodes.iterator();
 393             while ( it.hasNext() ) {
 394                 final PhylogenyNode n = it.next();
 395                 if ( !n.isExternal() ) {
 396                     throw new IllegalArgumentException( "attempt to delete non-external node \""
 397                             + node_names_to_delete[ i ] + "\"" );
 398                 }
 399                 p.deleteSubtree( n, true );
 400             }
 401         }
 402     }
 403
 404     public static void deleteExternalNodesPositiveSelection( final Set<Taxonomy> species_to_keep, final Phylogeny phy ) {
 405         //   final Set<Integer> to_delete = new HashSet<Integer>();
 406         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 407             final PhylogenyNode n = it.next();
 408             if ( n.getNodeData().isHasTaxonomy() ) {
 409                 if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) {
 410                     //to_delete.add( n.getNodeId() );
 411                     phy.deleteSubtree( n, true );
 412                 }
 413             }
 414             else {
 415                 throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" );
 416             }
 417         }
 418         phy.hashIDs();
 419         phy.externalNodesHaveChanged();
 420         //  deleteExternalNodesNegativeSelection( to_delete, phy );
 421     }
 422
 423     public static List<String> deleteExternalNodesPositiveSelection( final String[] node_names_to_keep,
 424                                                                      final Phylogeny p ) {
 425         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 426         final String[] to_delete = new String[ p.getNumberOfExternalNodes() ];
 427         int i = 0;
 428         Arrays.sort( node_names_to_keep );
 429         while ( it.hasNext() ) {
 430             final String curent_name = it.next().getName();
 431             if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) {
 432                 to_delete[ i++ ] = curent_name;
 433             }
 434         }
 435         PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p );
 436         final List<String> deleted = new ArrayList<String>();
 437         for( final String n : to_delete ) {
 438             if ( !ForesterUtil.isEmpty( n ) ) {
 439                 deleted.add( n );
 440             }
 441         }
 442         return deleted;
 443     }
 444
 445     public static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 446         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 447         final Set<Integer> encountered = new HashSet<Integer>();
 448         if ( !node.isExternal() ) {
 449             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 450             for( PhylogenyNode current : exts ) {
 451                 descs.add( current );
 452                 while ( current != node ) {
 453                     current = current.getParent();
 454                     if ( encountered.contains( current.getId() ) ) {
 455                         continue;
 456                     }
 457                     descs.add( current );
 458                     encountered.add( current.getId() );
 459                 }
 460             }
 461         }
 462         return descs;
 463     }
 464
 465     /**
 466      *
 467      * Convenience method
 468      *
 469      * @param node
 470      * @return
 471      */
 472     public static Color getBranchColorValue( final PhylogenyNode node ) {
 473         if ( node.getBranchData().getBranchColor() == null ) {
 474             return null;
 475         }
 476         return node.getBranchData().getBranchColor().getValue();
 477     }
 478
 479     /**
 480      * Convenience method
 481      */
 482     public static double getBranchWidthValue( final PhylogenyNode node ) {
 483         if ( !node.getBranchData().isHasBranchWidth() ) {
 484             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 485         }
 486         return node.getBranchData().getBranchWidth().getValue();
 487     }
 488
 489     /**
 490      * Convenience method
 491      */
 492     public static double getConfidenceValue( final PhylogenyNode node ) {
 493         if ( !node.getBranchData().isHasConfidences() ) {
 494             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 495         }
 496         return node.getBranchData().getConfidence( 0 ).getValue();
 497     }
 498
 499     /**
 500      * Convenience method
 501      */
 502     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 503         if ( !node.getBranchData().isHasConfidences() ) {
 504             return new double[ 0 ];
 505         }
 506         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 507         int i = 0;
 508         for( final Confidence c : node.getBranchData().getConfidences() ) {
 509             values[ i++ ] = c.getValue();
 510         }
 511         return values;
 512     }
 513
 514     /**
 515      * Calculates the distance between PhylogenyNodes n1 and n2.
 516      * PRECONDITION: n1 is a descendant of n2.
 517      *
 518      * @param n1
 519      *            a descendant of n2
 520      * @param n2
 521      * @return distance between n1 and n2
 522      */
 523     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
 524         double d = 0.0;
 525         while ( n1 != n2 ) {
 526             if ( n1.getDistanceToParent() > 0.0 ) {
 527                 d += n1.getDistanceToParent();
 528             }
 529             n1 = n1.getParent();
 530         }
 531         return d;
 532     }
 533
 534     /**
 535      * Returns taxonomy t if all external descendants have
 536      * the same taxonomy t, null otherwise.
 537      *
 538      */
 539     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 540         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 541         Taxonomy tax = null;
 542         for( final PhylogenyNode n : descs ) {
 543             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 544                 return null;
 545             }
 546             else if ( tax == null ) {
 547                 tax = n.getNodeData().getTaxonomy();
 548             }
 549             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 550                 return null;
 551             }
 552         }
 553         return tax;
 554     }
 555
 556     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 557         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 558         PhylogenyNode farthest = null;
 559         double longest = -Double.MAX_VALUE;
 560         for( final PhylogenyNode child : children ) {
 561             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 562                 farthest = child;
 563                 longest = PhylogenyMethods.getDistance( child, node );
 564             }
 565         }
 566         return farthest;
 567     }
 568
 569     public static PhylogenyMethods getInstance() {
 570         if ( PhylogenyMethods._instance == null ) {
 571             PhylogenyMethods._instance = new PhylogenyMethods();
 572         }
 573         return PhylogenyMethods._instance;
 574     }
 575
 576     /**
 577      * Returns the largest confidence value found on phy.
 578      */
 579     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 580         double max = -Double.MAX_VALUE;
 581         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 582             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 583             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 584                 max = s;
 585             }
 586         }
 587         return max;
 588     }
 589
 590     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 591         int min = Integer.MAX_VALUE;
 592         int d = 0;
 593         PhylogenyNode n;
 594         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 595             n = it.next();
 596             if ( n.isInternal() ) {
 597                 d = n.getNumberOfDescendants();
 598                 if ( d < min ) {
 599                     min = d;
 600                 }
 601             }
 602         }
 603         return min;
 604     }
 605
 606     /**
 607      * Convenience method for display purposes.
 608      * Not intended for algorithms.
 609      */
 610     public static String getSpecies( final PhylogenyNode node ) {
 611         if ( !node.getNodeData().isHasTaxonomy() ) {
 612             return "";
 613         }
 614         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 615             return node.getNodeData().getTaxonomy().getTaxonomyCode();
 616         }
 617         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
 618             return node.getNodeData().getTaxonomy().getScientificName();
 619         }
 620         else {
 621             return node.getNodeData().getTaxonomy().getCommonName();
 622         }
 623     }
 624
 625     /**
 626      * Returns all Nodes which are connected to external PhylogenyNode n of this
 627      * Phylogeny by a path containing only speciation events. We call these
 628      * "super orthologs". Nodes are returned as Vector of references to Nodes.
 629      * <p>
 630      * PRECONDITION: This tree must be binary and rooted, and speciation -
 631      * duplication need to be assigned for each of its internal Nodes.
 632      * <p>
 633      * Returns null if this Phylogeny is empty or if n is internal.
 634      * @param n
 635      *            external PhylogenyNode whose strictly speciation related Nodes
 636      *            are to be returned
 637      * @return Vector of references to all strictly speciation related Nodes of
 638      *         PhylogenyNode n of this Phylogeny, null if this Phylogeny is
 639      *         empty or if n is internal
 640      */
 641     public static List<PhylogenyNode> getSuperOrthologousNodes( final PhylogenyNode n ) {
 642         // FIXME
 643         PhylogenyNode node = n, deepest = null;
 644         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
 645         if ( !node.isExternal() ) {
 646             return null;
 647         }
 648         while ( !node.isRoot() && !node.getParent().isDuplication() ) {
 649             node = node.getParent();
 650         }
 651         deepest = node;
 652         deepest.setIndicatorsToZero();
 653         do {
 654             if ( !node.isExternal() ) {
 655                 if ( node.getIndicator() == 0 ) {
 656                     node.setIndicator( ( byte ) 1 );
 657                     if ( !node.isDuplication() ) {
 658                         node = node.getChildNode1();
 659                     }
 660                 }
 661                 if ( node.getIndicator() == 1 ) {
 662                     node.setIndicator( ( byte ) 2 );
 663                     if ( !node.isDuplication() ) {
 664                         node = node.getChildNode2();
 665                     }
 666                 }
 667                 if ( ( node != deepest ) && ( node.getIndicator() == 2 ) ) {
 668                     node = node.getParent();
 669                 }
 670             }
 671             else {
 672                 if ( node != n ) {
 673                     v.add( node );
 674                 }
 675                 if ( node != deepest ) {
 676                     node = node.getParent();
 677                 }
 678                 else {
 679                     node.setIndicator( ( byte ) 2 );
 680                 }
 681             }
 682         } while ( ( node != deepest ) || ( deepest.getIndicator() != 2 ) );
 683         return v;
 684     }
 685
 686     /**
 687      * Convenience method for display purposes.
 688      * Not intended for algorithms.
 689      */
 690     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
 691         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
 692             return "";
 693         }
 694         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
 695     }
 696
 697     /**
 698      * Returns all Nodes which are connected to external PhylogenyNode n of this
 699      * Phylogeny by a path containing, and leading to, only duplication events.
 700      * We call these "ultra paralogs". Nodes are returned as Vector of
 701      * references to Nodes.
 702      * <p>
 703      * PRECONDITION: This tree must be binary and rooted, and speciation -
 704      * duplication need to be assigned for each of its internal Nodes.
 705      * <p>
 706      * Returns null if this Phylogeny is empty or if n is internal.
 707      * <p>
 708      * (Last modified: 10/06/01)
 709      *
 710      * @param n
 711      *            external PhylogenyNode whose ultra paralogs are to be returned
 712      * @return Vector of references to all ultra paralogs of PhylogenyNode n of
 713      *         this Phylogeny, null if this Phylogeny is empty or if n is
 714      *         internal
 715      */
 716     public static List<PhylogenyNode> getUltraParalogousNodes( final PhylogenyNode n ) {
 717         // FIXME test me
 718         PhylogenyNode node = n;
 719         if ( !node.isExternal() ) {
 720             return null;
 721         }
 722         while ( !node.isRoot() && node.getParent().isDuplication() && areAllChildrenDuplications( node.getParent() ) ) {
 723             node = node.getParent();
 724         }
 725         final List<PhylogenyNode> nodes = node.getAllExternalDescendants();
 726         nodes.remove( n );
 727         return nodes;
 728     }
 729
 730     public static String inferCommonPartOfScientificNameOfDescendants( final PhylogenyNode node ) {
 731         final List<PhylogenyNode> descs = node.getDescendants();
 732         String sn = null;
 733         for( final PhylogenyNode n : descs ) {
 734             if ( !n.getNodeData().isHasTaxonomy()
 735                     || ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
 736                 return null;
 737             }
 738             else if ( sn == null ) {
 739                 sn = n.getNodeData().getTaxonomy().getScientificName().trim();
 740             }
 741             else {
 742                 String sn_current = n.getNodeData().getTaxonomy().getScientificName().trim();
 743                 if ( !sn.equals( sn_current ) ) {
 744                     boolean overlap = false;
 745                     while ( ( sn.indexOf( ' ' ) >= 0 ) || ( sn_current.indexOf( ' ' ) >= 0 ) ) {
 746                         if ( ForesterUtil.countChars( sn, ' ' ) > ForesterUtil.countChars( sn_current, ' ' ) ) {
 747                             sn = sn.substring( 0, sn.lastIndexOf( ' ' ) ).trim();
 748                         }
 749                         else {
 750                             sn_current = sn_current.substring( 0, sn_current.lastIndexOf( ' ' ) ).trim();
 751                         }
 752                         if ( sn.equals( sn_current ) ) {
 753                             overlap = true;
 754                             break;
 755                         }
 756                     }
 757                     if ( !overlap ) {
 758                         return null;
 759                     }
 760                 }
 761             }
 762         }
 763         return sn;
 764     }
 765
 766     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
 767         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 768             if ( node.getChildNode( i ).isExternal() ) {
 769                 return true;
 770             }
 771         }
 772         return false;
 773     }
 774
 775     /*
 776      * This is case insensitive.
 777      *
 778      */
 779     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
 780                                                                                final String[] providers ) {
 781         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
 782             final String my_tax_prov = tax.getIdentifier().getProvider();
 783             for( final String provider : providers ) {
 784                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
 785                     return true;
 786                 }
 787             }
 788             return false;
 789         }
 790         else {
 791             return false;
 792         }
 793     }
 794
 795     private static boolean match( final String s,
 796                                   final String query,
 797                                   final boolean case_sensitive,
 798                                   final boolean partial ) {
 799         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
 800             return false;
 801         }
 802         String my_s = s.trim();
 803         String my_query = query.trim();
 804         if ( !case_sensitive ) {
 805             my_s = my_s.toLowerCase();
 806             my_query = my_query.toLowerCase();
 807         }
 808         if ( partial ) {
 809             return my_s.indexOf( my_query ) >= 0;
 810         }
 811         else {
 812             return my_s.equals( my_query );
 813         }
 814     }
 815
 816     public static void midpointRoot( final Phylogeny phylogeny ) {
 817         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
 818             return;
 819         }
 820         final PhylogenyMethods methods = getInstance();
 821         final double farthest_d = methods.calculateFurthestDistance( phylogeny );
 822         final PhylogenyNode f1 = methods.getFarthestNode1();
 823         final PhylogenyNode f2 = methods.getFarthestNode2();
 824         if ( farthest_d <= 0.0 ) {
 825             return;
 826         }
 827         double x = farthest_d / 2.0;
 828         PhylogenyNode n = f1;
 829         if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny
 830                 .getRoot() ) ) {
 831             n = f2;
 832         }
 833         while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) {
 834             x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
 835             n = n.getParent();
 836         }
 837         phylogeny.reRoot( n, x );
 838         phylogeny.recalculateNumberOfExternalDescendants( true );
 839         final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() );
 840         final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() );
 841         final double da = getDistance( a, phylogeny.getRoot() );
 842         final double db = getDistance( b, phylogeny.getRoot() );
 843         if ( Math.abs( da - db ) > 0.000001 ) {
 844             throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed:  da="
 845                     + da + ",  db=" + db + ",  diff=" + Math.abs( da - db ) );
 846         }
 847     }
 848
 849     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
 850                                                  final double max_bootstrap_value,
 851                                                  final double max_normalized_value ) {
 852         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
 853             final PhylogenyNode node = iter.next();
 854             if ( node.isInternal() ) {
 855                 final double confidence = getConfidenceValue( node );
 856                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 857                     if ( confidence >= max_bootstrap_value ) {
 858                         setBootstrapConfidence( node, max_normalized_value );
 859                     }
 860                     else {
 861                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
 862                     }
 863                 }
 864             }
 865         }
 866     }
 867
 868     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
 869         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 870         if ( phy.isEmpty() ) {
 871             return nodes;
 872         }
 873         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 874             nodes.add( iter.next() );
 875         }
 876         return nodes;
 877     }
 878
 879     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
 880         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
 881             final PhylogenyNode node = iter.next();
 882             double red = 0.0;
 883             double green = 0.0;
 884             double blue = 0.0;
 885             int n = 0;
 886             if ( node.isInternal() ) {
 887                 for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
 888                     final PhylogenyNode child_node = iterator.next();
 889                     final Color child_color = getBranchColorValue( child_node );
 890                     if ( child_color != null ) {
 891                         ++n;
 892                         red += child_color.getRed();
 893                         green += child_color.getGreen();
 894                         blue += child_color.getBlue();
 895                     }
 896                 }
 897                 setBranchColorValue( node, new Color( ForesterUtil.roundToInt( red / n ), ForesterUtil
 898                         .roundToInt( green / n ), ForesterUtil.roundToInt( blue / n ) ) );
 899             }
 900         }
 901     }
 902
 903     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
 904         if ( remove_me.isRoot() ) {
 905             throw new IllegalArgumentException( "ill advised attempt to remove root node" );
 906         }
 907         if ( remove_me.isExternal() ) {
 908             phylogeny.deleteSubtree( remove_me, false );
 909         }
 910         else {
 911             final PhylogenyNode parent = remove_me.getParent();
 912             final List<PhylogenyNode> descs = remove_me.getDescendants();
 913             parent.removeChildNode( remove_me );
 914             for( final PhylogenyNode desc : descs ) {
 915                 parent.addAsChild( desc );
 916                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(), desc
 917                         .getDistanceToParent() ) );
 918             }
 919             remove_me.setParent( null );
 920             phylogeny.setIdHash( null );
 921             phylogeny.externalNodesHaveChanged();
 922         }
 923     }
 924
 925     public static List<PhylogenyNode> searchData( final String query,
 926                                                   final Phylogeny phy,
 927                                                   final boolean case_sensitive,
 928                                                   final boolean partial ) {
 929         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 930         if ( phy.isEmpty() || ( query == null ) ) {
 931             return nodes;
 932         }
 933         if ( ForesterUtil.isEmpty( query ) ) {
 934             return nodes;
 935         }
 936         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 937             final PhylogenyNode node = iter.next();
 938             boolean match = false;
 939             if ( match( node.getName(), query, case_sensitive, partial ) ) {
 940                 match = true;
 941             }
 942             else if ( node.getNodeData().isHasTaxonomy()
 943                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 944                 match = true;
 945             }
 946             else if ( node.getNodeData().isHasTaxonomy()
 947                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
 948                 match = true;
 949             }
 950             else if ( node.getNodeData().isHasTaxonomy()
 951                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
 952                 match = true;
 953             }
 954             else if ( node.getNodeData().isHasTaxonomy()
 955                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
 956                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
 957                               query,
 958                               case_sensitive,
 959                               partial ) ) {
 960                 match = true;
 961             }
 962             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
 963                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
 964                 I: for( final String syn : syns ) {
 965                     if ( match( syn, query, case_sensitive, partial ) ) {
 966                         match = true;
 967                         break I;
 968                     }
 969                 }
 970             }
 971             else if ( node.getNodeData().isHasSequence()
 972                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
 973                 match = true;
 974             }
 975             else if ( node.getNodeData().isHasSequence()
 976                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
 977                 match = true;
 978             }
 979             else if ( node.getNodeData().isHasSequence()
 980                     && ( node.getNodeData().getSequence().getAccession() != null )
 981                     && match( node.getNodeData().getSequence().getAccession().getValue(),
 982                               query,
 983                               case_sensitive,
 984                               partial ) ) {
 985                 match = true;
 986             }
 987             else if ( node.getNodeData().isHasSequence()
 988                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
 989                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
 990                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
 991                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
 992                         match = true;
 993                         break I;
 994                     }
 995                 }
 996             }
 997             if ( match ) {
 998                 nodes.add( node );
 999             }
1000         }
1001         return nodes;
1002     }
1003
1004     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
1005                                                             final Phylogeny phy,
1006                                                             final boolean case_sensitive,
1007                                                             final boolean partial ) {
1008         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
1009         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
1010             return nodes;
1011         }
1012         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
1013             final PhylogenyNode node = iter.next();
1014             boolean all_matched = true;
1015             for( final String query : queries ) {
1016                 boolean match = false;
1017                 if ( ForesterUtil.isEmpty( query ) ) {
1018                     continue;
1019                 }
1020                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
1021                     match = true;
1022                 }
1023                 else if ( node.getNodeData().isHasTaxonomy()
1024                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
1025                     match = true;
1026                 }
1027                 else if ( node.getNodeData().isHasTaxonomy()
1028                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1029                     match = true;
1030                 }
1031                 else if ( node.getNodeData().isHasTaxonomy()
1032                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1033                     match = true;
1034                 }
1035                 else if ( node.getNodeData().isHasTaxonomy()
1036                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1037                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1038                                   query,
1039                                   case_sensitive,
1040                                   partial ) ) {
1041                     match = true;
1042                 }
1043                 else if ( node.getNodeData().isHasTaxonomy()
1044                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1045                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1046                     I: for( final String syn : syns ) {
1047                         if ( match( syn, query, case_sensitive, partial ) ) {
1048                             match = true;
1049                             break I;
1050                         }
1051                     }
1052                 }
1053                 else if ( node.getNodeData().isHasSequence()
1054                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1055                     match = true;
1056                 }
1057                 else if ( node.getNodeData().isHasSequence()
1058                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1059                     match = true;
1060                 }
1061                 else if ( node.getNodeData().isHasSequence()
1062                         && ( node.getNodeData().getSequence().getAccession() != null )
1063                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1064                                   query,
1065                                   case_sensitive,
1066                                   partial ) ) {
1067                     match = true;
1068                 }
1069                 else if ( node.getNodeData().isHasSequence()
1070                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1071                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1072                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1073                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1074                             match = true;
1075                             break I;
1076                         }
1077                     }
1078                 }
1079                 if ( !match ) {
1080                     all_matched = false;
1081                     break;
1082                 }
1083             }
1084             if ( all_matched ) {
1085                 nodes.add( node );
1086             }
1087         }
1088         return nodes;
1089     }
1090
1091     /**
1092      * Convenience method.
1093      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1094      */
1095     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1096         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1097     }
1098
1099     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1100         if ( node.getBranchData().getBranchColor() == null ) {
1101             node.getBranchData().setBranchColor( new BranchColor() );
1102         }
1103         node.getBranchData().getBranchColor().setValue( color );
1104     }
1105
1106     /**
1107      * Convenience method
1108      */
1109     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1110         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1111     }
1112
1113     /**
1114      * Convenience method.
1115      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1116      */
1117     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1118         setConfidence( node, confidence_value, "" );
1119     }
1120
1121     /**
1122      * Convenience method.
1123      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1124      */
1125     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1126         Confidence c = null;
1127         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1128             c = node.getBranchData().getConfidence( 0 );
1129         }
1130         else {
1131             c = new Confidence();
1132             node.getBranchData().addConfidence( c );
1133         }
1134         c.setType( type );
1135         c.setValue( confidence_value );
1136     }
1137
1138     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1139         if ( !node.getNodeData().isHasTaxonomy() ) {
1140             node.getNodeData().setTaxonomy( new Taxonomy() );
1141         }
1142         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1143     }
1144
1145     /**
1146      * Convenience method to set the taxonomy code of a phylogeny node.
1147      *
1148      *
1149      * @param node
1150      * @param taxonomy_code
1151      */
1152     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code ) {
1153         if ( !node.getNodeData().isHasTaxonomy() ) {
1154             node.getNodeData().setTaxonomy( new Taxonomy() );
1155         }
1156         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1157     }
1158
1159     /**
1160      * Removes from Phylogeny to_be_stripped all external Nodes which are
1161      * associated with a species NOT found in Phylogeny reference.
1162      *
1163      * @param reference
1164      *            a reference Phylogeny
1165      * @param to_be_stripped
1166      *            Phylogeny to be stripped
1167      * @return number of external nodes removed from to_be_stripped
1168      */
1169     public static int taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference, final Phylogeny to_be_stripped ) {
1170         final Set<String> ref_ext_taxo = new HashSet<String>();
1171         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1172         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1173             ref_ext_taxo.add( getSpecies( it.next() ) );
1174         }
1175         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1176             final PhylogenyNode n = it.next();
1177             if ( !ref_ext_taxo.contains( getSpecies( n ) ) ) {
1178                 nodes_to_delete.add( n );
1179             }
1180         }
1181         for( final PhylogenyNode phylogenyNode : nodes_to_delete ) {
1182             to_be_stripped.deleteSubtree( phylogenyNode, true );
1183         }
1184         return nodes_to_delete.size();
1185     }
1186 }