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

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