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