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