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