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

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