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     private static enum NDF {\r
 940         NodeName( "NN" ),\r
 941         TaxonomyCode( "TC" ),\r
 942         TaxonomyCommonName( "CN" ),\r
 943         TaxonomyScientificName( "TS" ),\r
 944         TaxonomyIdentifier( "TI" ),\r
 945         TaxonomySynonym( "SY" ),\r
 946         SequenceName( "SN" ),\r
 947         GeneName( "GN" ),\r
 948         SequenceSymbol( "SS" ),\r
 949         SequenceAccession( "SA" ),\r
 950         Domain( "DO" ),\r
 951         Annotation( "AN" ),\r
 952         CrossRef( "XR" ),\r
 953         BinaryCharacter( "BC" ),\r
 954         MolecularSequence( "MS" );\r
 955 \r
 956         private final String _text;\r
 957 \r
 958         NDF( final String text ) {\r
 959             _text = text;\r
 960         }\r
 961 \r
 962         public static NDF fromString( final String text ) {\r
 963             for( final NDF n : NDF.values() ) {\r
 964                 if ( text.startsWith( n._text ) ) {\r
 965                     return n;\r
 966                 }\r
 967             }\r
 968             return null;\r
 969         }\r
 970     }\r
 971 \r
 972     public static List<PhylogenyNode> searchData( final String query,\r
 973                                                   final Phylogeny phy,\r
 974                                                   final boolean case_sensitive,\r
 975                                                   final boolean partial,\r
 976                                                   final boolean regex,\r
 977                                                   final boolean search_domains,\r
 978                                                   final double domains_confidence_threshold ) {\r
 979         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();\r
 980         if ( phy.isEmpty() || ( query == null ) ) {\r
 981             return nodes;\r
 982         }\r
 983         if ( ForesterUtil.isEmpty( query ) ) {\r
 984             return nodes;\r
 985         }\r
 986         String my_query = query;\r
 987         NDF ndf = null;\r
 988         if ( ( my_query.length() > 2 ) && ( my_query.indexOf( ":" ) == 2 ) ) {\r
 989             ndf = NDF.fromString( my_query );\r
 990             if ( ndf != null ) {\r
 991                 my_query = my_query.substring( 3 );\r
 992             }\r
 993         }\r
 994         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {\r
 995             final PhylogenyNode node = iter.next();\r
 996             boolean match = false;\r
 997             if ( ( ( ndf == null ) || ( ndf == NDF.NodeName ) )\r
 998                     && match( node.getName(), my_query, case_sensitive, partial, regex ) ) {\r
 999                 match = true;\r
1000             }\r
1001             else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyCode ) )\r
1002                     && node.getNodeData().isHasTaxonomy()\r
1003                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(),\r
1004                               my_query,\r
1005                               case_sensitive,\r
1006                               partial,\r
1007                               regex ) ) {\r
1008                 match = true;\r
1009             }\r
1010             else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyCommonName ) )\r
1011                     && node.getNodeData().isHasTaxonomy()\r
1012                     && match( node.getNodeData().getTaxonomy().getCommonName(),\r
1013                               my_query,\r
1014                               case_sensitive,\r
1015                               partial,\r
1016                               regex ) ) {\r
1017                 match = true;\r
1018             }\r
1019             else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyScientificName ) )\r
1020                     && node.getNodeData().isHasTaxonomy()\r
1021                     && match( node.getNodeData().getTaxonomy().getScientificName(),\r
1022                               my_query,\r
1023                               case_sensitive,\r
1024                               partial,\r
1025                               regex ) ) {\r
1026                 match = true;\r
1027             }\r
1028             else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyIdentifier ) )\r
1029                     && node.getNodeData().isHasTaxonomy()\r
1030                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )\r
1031                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),\r
1032                               my_query,\r
1033                               case_sensitive,\r
1034                               partial,\r
1035                               regex ) ) {\r
1036                 match = true;\r
1037             }\r
1038             else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomySynonym ) ) && node.getNodeData().isHasTaxonomy()\r
1039                     && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {\r
1040                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();\r
1041                 I: for( final String syn : syns ) {\r
1042                     if ( match( syn, my_query, case_sensitive, partial, regex ) ) {\r
1043                         match = true;\r
1044                         break I;\r
1045                     }\r
1046                 }\r
1047             }\r
1048             if ( !match && ( ( ndf == null ) || ( ndf == NDF.SequenceName ) ) && node.getNodeData().isHasSequence()\r
1049                     && match( node.getNodeData().getSequence().getName(), my_query, case_sensitive, partial, regex ) ) {\r
1050                 match = true;\r
1051             }\r
1052             if ( !match && ( ( ndf == null ) || ( ndf == NDF.GeneName ) ) && node.getNodeData().isHasSequence()\r
1053                     && match( node.getNodeData().getSequence().getGeneName(), my_query, case_sensitive, partial, regex ) ) {\r
1054                 match = true;\r
1055             }\r
1056             if ( !match && ( ( ndf == null ) || ( ndf == NDF.SequenceSymbol ) ) && node.getNodeData().isHasSequence()\r
1057                     && match( node.getNodeData().getSequence().getSymbol(), my_query, case_sensitive, partial, regex ) ) {\r
1058                 match = true;\r
1059             }\r
1060             if ( !match\r
1061                     && ( ( ndf == null ) || ( ndf == NDF.SequenceAccession ) )\r
1062                     && node.getNodeData().isHasSequence()\r
1063                     && ( node.getNodeData().getSequence().getAccession() != null )\r
1064                     && match( node.getNodeData().getSequence().getAccession().getValue(),\r
1065                               my_query,\r
1066                               case_sensitive,\r
1067                               partial,\r
1068                               regex ) ) {\r
1069                 match = true;\r
1070             }\r
1071             if ( !match && ( ( ( ndf == null ) && search_domains ) || ( ndf == NDF.Domain ) )\r
1072                     && node.getNodeData().isHasSequence()\r
1073                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {\r
1074                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();\r
1075                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {\r
1076                     if ( ( da.getDomain( i ).getConfidence() <= domains_confidence_threshold )\r
1077                             && ( match( da.getDomain( i ).getName(), my_query, case_sensitive, partial, regex ) ) ) {\r
1078                         match = true;\r
1079                         break I;\r
1080                     }\r
1081                 }\r
1082             }\r
1083             if ( !match && ( ( ndf == null ) || ( ndf == NDF.Annotation ) ) && node.getNodeData().isHasSequence()\r
1084                     && ( node.getNodeData().getSequence().getAnnotations() != null ) ) {\r
1085                 for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) {\r
1086                     if ( match( ann.getDesc(), my_query, case_sensitive, partial, regex ) ) {\r
1087                         match = true;\r
1088                         break;\r
1089                     }\r
1090                     if ( match( ann.getRef(), my_query, case_sensitive, partial, regex ) ) {\r
1091                         match = true;\r
1092                         break;\r
1093                     }\r
1094                 }\r
1095             }\r
1096             if ( !match && ( ( ndf == null ) || ( ndf == NDF.CrossRef ) ) && node.getNodeData().isHasSequence()\r
1097                     && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) {\r
1098                 for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) {\r
1099                     if ( match( x.getComment(), my_query, case_sensitive, partial, regex ) ) {\r
1100                         match = true;\r
1101                         break;\r
1102                     }\r
1103                     if ( match( x.getSource(), my_query, case_sensitive, partial, regex ) ) {\r
1104                         match = true;\r
1105                         break;\r
1106                     }\r
1107                     if ( match( x.getValue(), my_query, case_sensitive, partial, regex ) ) {\r
1108                         match = true;\r
1109                         break;\r
1110                     }\r
1111                 }\r
1112             }\r
1113             if ( !match && ( ( ndf == null ) || ( ndf == NDF.BinaryCharacter ) )\r
1114                     && ( node.getNodeData().getBinaryCharacters() != null ) ) {\r
1115                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();\r
1116                 I: while ( it.hasNext() ) {\r
1117                     if ( match( it.next(), my_query, case_sensitive, partial, regex ) ) {\r
1118                         match = true;\r
1119                         break I;\r
1120                     }\r
1121                 }\r
1122                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();\r
1123                 I: while ( it.hasNext() ) {\r
1124                     if ( match( it.next(), my_query, case_sensitive, partial, regex ) ) {\r
1125                         match = true;\r
1126                         break I;\r
1127                     }\r
1128                 }\r
1129             }\r
1130             if ( !match\r
1131                     && ( ndf == NDF.MolecularSequence )\r
1132                     && node.getNodeData().isHasSequence()\r
1133                     && match( node.getNodeData().getSequence().getMolecularSequence(),\r
1134                               my_query,\r
1135                               case_sensitive,\r
1136                               true,\r
1137                               regex ) ) {\r
1138                 match = true;\r
1139             }\r
1140             if ( match ) {\r
1141                 nodes.add( node );\r
1142             }\r
1143         }\r
1144         return nodes;\r
1145     }\r
1146 \r
1147     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,\r
1148                                                             final Phylogeny phy,\r
1149                                                             final boolean case_sensitive,\r
1150                                                             final boolean partial,\r
1151                                                             final boolean search_domains,\r
1152                                                             final double domains_confidence_threshold ) {\r
1153         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();\r
1154         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {\r
1155             return nodes;\r
1156         }\r
1157         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {\r
1158             final PhylogenyNode node = iter.next();\r
1159             boolean all_matched = true;\r
1160             for( String query : queries ) {\r
1161                 NDF ndf = null;\r
1162                 if ( ( query.length() > 2 ) && ( query.indexOf( ":" ) == 2 ) ) {\r
1163                     ndf = NDF.fromString( query );\r
1164                     if ( ndf != null ) {\r
1165                         query = query.substring( 3 );\r
1166                     }\r
1167                 }\r
1168                 boolean match = false;\r
1169                 if ( ForesterUtil.isEmpty( query ) ) {\r
1170                     continue;\r
1171                 }\r
1172                 if ( ( ( ndf == null ) || ( ndf == NDF.NodeName ) )\r
1173                         && match( node.getName(), query, case_sensitive, partial, false ) ) {\r
1174                     match = true;\r
1175                 }\r
1176                 else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyCode ) )\r
1177                         && node.getNodeData().isHasTaxonomy()\r
1178                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(),\r
1179                                   query,\r
1180                                   case_sensitive,\r
1181                                   partial,\r
1182                                   false ) ) {\r
1183                     match = true;\r
1184                 }\r
1185                 else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyCommonName ) )\r
1186                         && node.getNodeData().isHasTaxonomy()\r
1187                         && match( node.getNodeData().getTaxonomy().getCommonName(),\r
1188                                   query,\r
1189                                   case_sensitive,\r
1190                                   partial,\r
1191                                   false ) ) {\r
1192                     match = true;\r
1193                 }\r
1194                 else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyScientificName ) )\r
1195                         && node.getNodeData().isHasTaxonomy()\r
1196                         && match( node.getNodeData().getTaxonomy().getScientificName(),\r
1197                                   query,\r
1198                                   case_sensitive,\r
1199                                   partial,\r
1200                                   false ) ) {\r
1201                     match = true;\r
1202                 }\r
1203                 else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomyIdentifier ) )\r
1204                         && node.getNodeData().isHasTaxonomy()\r
1205                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )\r
1206                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),\r
1207                                   query,\r
1208                                   case_sensitive,\r
1209                                   partial,\r
1210                                   false ) ) {\r
1211                     match = true;\r
1212                 }\r
1213                 else if ( ( ( ndf == null ) || ( ndf == NDF.TaxonomySynonym ) ) && node.getNodeData().isHasTaxonomy()\r
1214                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {\r
1215                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();\r
1216                     I: for( final String syn : syns ) {\r
1217                         if ( match( syn, query, case_sensitive, partial, false ) ) {\r
1218                             match = true;\r
1219                             break I;\r
1220                         }\r
1221                     }\r
1222                 }\r
1223                 if ( !match && ( ( ndf == null ) || ( ndf == NDF.SequenceName ) ) && node.getNodeData().isHasSequence()\r
1224                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial, false ) ) {\r
1225                     match = true;\r
1226                 }\r
1227                 if ( !match\r
1228                         && ( ( ndf == null ) || ( ndf == NDF.GeneName ) )\r
1229                         && node.getNodeData().isHasSequence()\r
1230                         && match( node.getNodeData().getSequence().getGeneName(), query, case_sensitive, partial, false ) ) {\r
1231                     match = true;\r
1232                 }\r
1233                 if ( !match && ( ( ndf == null ) || ( ndf == NDF.SequenceSymbol ) )\r
1234                         && node.getNodeData().isHasSequence()\r
1235                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial, false ) ) {\r
1236                     match = true;\r
1237                 }\r
1238                 if ( !match\r
1239                         && ( ( ndf == null ) || ( ndf == NDF.SequenceAccession ) )\r
1240                         && node.getNodeData().isHasSequence()\r
1241                         && ( node.getNodeData().getSequence().getAccession() != null )\r
1242                         && match( node.getNodeData().getSequence().getAccession().getValue(),\r
1243                                   query,\r
1244                                   case_sensitive,\r
1245                                   partial,\r
1246                                   false ) ) {\r
1247                     match = true;\r
1248                 }\r
1249                 if ( !match && ( ( ( ndf == null ) && search_domains ) || ( ndf == NDF.Domain ) )\r
1250                         && node.getNodeData().isHasSequence()\r
1251                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {\r
1252                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();\r
1253                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {\r
1254                         if ( ( da.getDomain( i ).getConfidence() <= domains_confidence_threshold )\r
1255                                 && match( da.getDomain( i ).getName(), query, case_sensitive, partial, false ) ) {\r
1256                             match = true;\r
1257                             break I;\r
1258                         }\r
1259                     }\r
1260                 }\r
1261                 if ( !match && ( ( ndf == null ) || ( ndf == NDF.Annotation ) ) && node.getNodeData().isHasSequence()\r
1262                         && ( node.getNodeData().getSequence().getAnnotations() != null ) ) {\r
1263                     for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) {\r
1264                         if ( match( ann.getDesc(), query, case_sensitive, partial, false ) ) {\r
1265                             match = true;\r
1266                             break;\r
1267                         }\r
1268                         if ( match( ann.getRef(), query, case_sensitive, partial, false ) ) {\r
1269                             match = true;\r
1270                             break;\r
1271                         }\r
1272                     }\r
1273                 }\r
1274                 if ( !match && ( ( ndf == null ) || ( ndf == NDF.CrossRef ) ) && node.getNodeData().isHasSequence()\r
1275                         && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) {\r
1276                     for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) {\r
1277                         if ( match( x.getComment(), query, case_sensitive, partial, false ) ) {\r
1278                             match = true;\r
1279                             break;\r
1280                         }\r
1281                         if ( match( x.getSource(), query, case_sensitive, partial, false ) ) {\r
1282                             match = true;\r
1283                             break;\r
1284                         }\r
1285                         if ( match( x.getValue(), query, case_sensitive, partial, false ) ) {\r
1286                             match = true;\r
1287                             break;\r
1288                         }\r
1289                     }\r
1290                 }\r
1291                 if ( !match && ( ( ndf == null ) || ( ndf == NDF.BinaryCharacter ) )\r
1292                         && ( node.getNodeData().getBinaryCharacters() != null ) ) {\r
1293                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();\r
1294                     I: while ( it.hasNext() ) {\r
1295                         if ( match( it.next(), query, case_sensitive, partial, false ) ) {\r
1296                             match = true;\r
1297                             break I;\r
1298                         }\r
1299                     }\r
1300                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();\r
1301                     I: while ( it.hasNext() ) {\r
1302                         if ( match( it.next(), query, case_sensitive, partial, false ) ) {\r
1303                             match = true;\r
1304                             break I;\r
1305                         }\r
1306                     }\r
1307                 }\r
1308                 if ( !match\r
1309                         && ( ndf == NDF.MolecularSequence )\r
1310                         && node.getNodeData().isHasSequence()\r
1311                         && match( node.getNodeData().getSequence().getMolecularSequence(),\r
1312                                   query,\r
1313                                   case_sensitive,\r
1314                                   true,\r
1315                                   false ) ) {\r
1316                     match = true;\r
1317                 }\r
1318                 if ( !match ) {\r
1319                     all_matched = false;\r
1320                     break;\r
1321                 }\r
1322             }\r
1323             if ( all_matched ) {\r
1324                 nodes.add( node );\r
1325             }\r
1326         }\r
1327         return nodes;\r
1328     }\r
1329 \r
1330     public static void setAllIndicatorsToZero( final Phylogeny phy ) {\r
1331         for( final PhylogenyNodeIterator it = phy.iteratorPostorder(); it.hasNext(); ) {\r
1332             it.next().setIndicator( ( byte ) 0 );\r
1333         }\r
1334     }\r
1335 \r
1336     /**\r
1337      * Convenience method.\r
1338      * Sets value for the first confidence value (created if not present, values overwritten otherwise).\r
1339      */\r
1340     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {\r
1341         setConfidence( node, bootstrap_confidence_value, "bootstrap" );\r
1342     }\r
1343 \r
1344     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {\r
1345         if ( node.getBranchData().getBranchColor() == null ) {\r
1346             node.getBranchData().setBranchColor( new BranchColor() );\r
1347         }\r
1348         node.getBranchData().getBranchColor().setValue( color );\r
1349     }\r
1350 \r
1351     /**\r
1352      * Convenience method\r
1353      */\r
1354     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {\r
1355         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );\r
1356     }\r
1357 \r
1358     /**\r
1359      * Convenience method.\r
1360      * Sets value for the first confidence value (created if not present, values overwritten otherwise).\r
1361      */\r
1362     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {\r
1363         setConfidence( node, confidence_value, "" );\r
1364     }\r
1365 \r
1366     /**\r
1367      * Convenience method.\r
1368      * Sets value for the first confidence value (created if not present, values overwritten otherwise).\r
1369      */\r
1370     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {\r
1371         Confidence c = null;\r
1372         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {\r
1373             c = node.getBranchData().getConfidence( 0 );\r
1374         }\r
1375         else {\r
1376             c = new Confidence();\r
1377             node.getBranchData().addConfidence( c );\r
1378         }\r
1379         c.setType( type );\r
1380         c.setValue( confidence_value );\r
1381     }\r
1382 \r
1383     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {\r
1384         if ( !node.getNodeData().isHasTaxonomy() ) {\r
1385             node.getNodeData().setTaxonomy( new Taxonomy() );\r
1386         }\r
1387         node.getNodeData().getTaxonomy().setScientificName( scientific_name );\r
1388     }\r
1389 \r
1390     /**\r
1391      * Convenience method to set the taxonomy code of a phylogeny node.\r
1392      *\r
1393      *\r
1394      * @param node\r
1395      * @param taxonomy_code\r
1396      * @throws PhyloXmlDataFormatException\r
1397      */\r
1398     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code )\r
1399             throws PhyloXmlDataFormatException {\r
1400         if ( !node.getNodeData().isHasTaxonomy() ) {\r
1401             node.getNodeData().setTaxonomy( new Taxonomy() );\r
1402         }\r
1403         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );\r
1404     }\r
1405 \r
1406     final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) {\r
1407         Comparator<PhylogenyNode> c;\r
1408         switch ( pri ) {\r
1409             case SEQUENCE:\r
1410                 c = new PhylogenyNodeSortSequencePriority();\r
1411                 break;\r
1412             case NODE_NAME:\r
1413                 c = new PhylogenyNodeSortNodeNamePriority();\r
1414                 break;\r
1415             default:\r
1416                 c = new PhylogenyNodeSortTaxonomyPriority();\r
1417         }\r
1418         final List<PhylogenyNode> descs = node.getDescendants();\r
1419         Collections.sort( descs, c );\r
1420         int i = 0;\r
1421         for( final PhylogenyNode desc : descs ) {\r
1422             node.setChildNode( i++, desc );\r
1423         }\r
1424     }\r
1425 \r
1426     /**\r
1427      * Removes from Phylogeny to_be_stripped all external Nodes which are\r
1428      * associated with a species NOT found in Phylogeny reference.\r
1429      *\r
1430      * @param reference\r
1431      *            a reference Phylogeny\r
1432      * @param to_be_stripped\r
1433      *            Phylogeny to be stripped\r
1434      * @return nodes removed from to_be_stripped\r
1435      */\r
1436     public static List<PhylogenyNode> taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference,\r
1437                                                                             final Phylogeny to_be_stripped ) {\r
1438         final Set<String> ref_ext_taxo = new HashSet<String>();\r
1439         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {\r
1440             final PhylogenyNode n = it.next();\r
1441             if ( !n.getNodeData().isHasTaxonomy() ) {\r
1442                 throw new IllegalArgumentException( "no taxonomic data in node: " + n );\r
1443             }\r
1444             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {\r
1445                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() );\r
1446             }\r
1447             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {\r
1448                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() );\r
1449             }\r
1450             if ( ( n.getNodeData().getTaxonomy().getIdentifier() != null )\r
1451                     && !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getIdentifier().getValue() ) ) {\r
1452                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() );\r
1453             }\r
1454         }\r
1455         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();\r
1456         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {\r
1457             final PhylogenyNode n = it.next();\r
1458             if ( !n.getNodeData().isHasTaxonomy() ) {\r
1459                 nodes_to_delete.add( n );\r
1460             }\r
1461             else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) )\r
1462                     && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) )\r
1463                     && !( ( n.getNodeData().getTaxonomy().getIdentifier() != null ) && ref_ext_taxo.contains( n\r
1464                             .getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() ) ) ) {\r
1465                 nodes_to_delete.add( n );\r
1466             }\r
1467         }\r
1468         for( final PhylogenyNode n : nodes_to_delete ) {\r
1469             to_be_stripped.deleteSubtree( n, true );\r
1470         }\r
1471         to_be_stripped.clearHashIdToNodeMap();\r
1472         to_be_stripped.externalNodesHaveChanged();\r
1473         return nodes_to_delete;\r
1474     }\r
1475 \r
1476     final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) {\r
1477         final PhylogenyNodeIterator it = phy.iteratorPostorder();\r
1478         while ( it.hasNext() ) {\r
1479             final PhylogenyNode n = it.next();\r
1480             if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) {\r
1481                 double value = -1;\r
1482                 try {\r
1483                     value = Double.parseDouble( n.getName() );\r
1484                 }\r
1485                 catch ( final NumberFormatException e ) {\r
1486                     throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: "\r
1487                             + e.getLocalizedMessage() );\r
1488                 }\r
1489                 if ( value >= 0.0 ) {\r
1490                     n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) );\r
1491                     n.setName( "" );\r
1492                 }\r
1493             }\r
1494         }\r
1495     }\r
1496 \r
1497     final static public boolean isInternalNamesLookLikeConfidences( final Phylogeny phy ) {\r
1498         final PhylogenyNodeIterator it = phy.iteratorPostorder();\r
1499         while ( it.hasNext() ) {\r
1500             final PhylogenyNode n = it.next();\r
1501             if ( !n.isExternal() && !n.isRoot() ) {\r
1502                 if ( !ForesterUtil.isEmpty( n.getName() ) ) {\r
1503                     double value = -1;\r
1504                     try {\r
1505                         value = Double.parseDouble( n.getName() );\r
1506                     }\r
1507                     catch ( final NumberFormatException e ) {\r
1508                         return false;\r
1509                     }\r
1510                     if ( ( value < 0.0 ) || ( value > 100 ) ) {\r
1511                         return false;\r
1512                     }\r
1513                 }\r
1514             }\r
1515         }\r
1516         return true;\r
1517     }\r
1518 \r
1519     final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy, final String confidence_type ) {\r
1520         final PhylogenyNodeIterator it = phy.iteratorPostorder();\r
1521         while ( it.hasNext() ) {\r
1522             transferInternalNodeNameToConfidence( confidence_type, it.next() );\r
1523         }\r
1524     }\r
1525 \r
1526     private static void transferInternalNodeNameToConfidence( final String confidence_type, final PhylogenyNode n ) {\r
1527         if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) {\r
1528             if ( !ForesterUtil.isEmpty( n.getName() ) ) {\r
1529                 double d = -1.0;\r
1530                 try {\r
1531                     d = Double.parseDouble( n.getName() );\r
1532                 }\r
1533                 catch ( final Exception e ) {\r
1534                     d = -1.0;\r
1535                 }\r
1536                 if ( d >= 0.0 ) {\r
1537                     n.getBranchData().addConfidence( new Confidence( d, confidence_type ) );\r
1538                     n.setName( "" );\r
1539                 }\r
1540             }\r
1541         }\r
1542     }\r
1543 \r
1544     final static public void transferNodeNameToField( final Phylogeny phy,\r
1545                                                       final PhylogenyNodeField field,\r
1546                                                       final boolean external_only ) throws PhyloXmlDataFormatException {\r
1547         final PhylogenyNodeIterator it = phy.iteratorPostorder();\r
1548         while ( it.hasNext() ) {\r
1549             final PhylogenyNode n = it.next();\r
1550             if ( external_only && n.isInternal() ) {\r
1551                 continue;\r
1552             }\r
1553             final String name = n.getName().trim();\r
1554             if ( !ForesterUtil.isEmpty( name ) ) {\r
1555                 switch ( field ) {\r
1556                     case TAXONOMY_CODE:\r
1557                         n.setName( "" );\r
1558                         setTaxonomyCode( n, name );\r
1559                         break;\r
1560                     case TAXONOMY_SCIENTIFIC_NAME:\r
1561                         n.setName( "" );\r
1562                         if ( !n.getNodeData().isHasTaxonomy() ) {\r
1563                             n.getNodeData().setTaxonomy( new Taxonomy() );\r
1564                         }\r
1565                         n.getNodeData().getTaxonomy().setScientificName( name );\r
1566                         break;\r
1567                     case TAXONOMY_COMMON_NAME:\r
1568                         n.setName( "" );\r
1569                         if ( !n.getNodeData().isHasTaxonomy() ) {\r
1570                             n.getNodeData().setTaxonomy( new Taxonomy() );\r
1571                         }\r
1572                         n.getNodeData().getTaxonomy().setCommonName( name );\r
1573                         break;\r
1574                     case SEQUENCE_SYMBOL:\r
1575                         n.setName( "" );\r
1576                         if ( !n.getNodeData().isHasSequence() ) {\r
1577                             n.getNodeData().setSequence( new Sequence() );\r
1578                         }\r
1579                         n.getNodeData().getSequence().setSymbol( name );\r
1580                         break;\r
1581                     case SEQUENCE_NAME:\r
1582                         n.setName( "" );\r
1583                         if ( !n.getNodeData().isHasSequence() ) {\r
1584                             n.getNodeData().setSequence( new Sequence() );\r
1585                         }\r
1586                         n.getNodeData().getSequence().setName( name );\r
1587                         break;\r
1588                     case TAXONOMY_ID_UNIPROT_1: {\r
1589                         if ( !n.getNodeData().isHasTaxonomy() ) {\r
1590                             n.getNodeData().setTaxonomy( new Taxonomy() );\r
1591                         }\r
1592                         String id = name;\r
1593                         final int i = name.indexOf( '_' );\r
1594                         if ( i > 0 ) {\r
1595                             id = name.substring( 0, i );\r
1596                         }\r
1597                         else {\r
1598                             n.setName( "" );\r
1599                         }\r
1600                         n.getNodeData().getTaxonomy()\r
1601                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );\r
1602                         break;\r
1603                     }\r
1604                     case TAXONOMY_ID_UNIPROT_2: {\r
1605                         if ( !n.getNodeData().isHasTaxonomy() ) {\r
1606                             n.getNodeData().setTaxonomy( new Taxonomy() );\r
1607                         }\r
1608                         String id = name;\r
1609                         final int i = name.indexOf( '_' );\r
1610                         if ( i > 0 ) {\r
1611                             id = name.substring( i + 1, name.length() );\r
1612                         }\r
1613                         else {\r
1614                             n.setName( "" );\r
1615                         }\r
1616                         n.getNodeData().getTaxonomy()\r
1617                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );\r
1618                         break;\r
1619                     }\r
1620                     case TAXONOMY_ID: {\r
1621                         if ( !n.getNodeData().isHasTaxonomy() ) {\r
1622                             n.getNodeData().setTaxonomy( new Taxonomy() );\r
1623                         }\r
1624                         n.getNodeData().getTaxonomy().setIdentifier( new Identifier( name ) );\r
1625                         break;\r
1626                     }\r
1627                 }\r
1628             }\r
1629         }\r
1630     }\r
1631 \r
1632     static double addPhylogenyDistances( final double a, final double b ) {\r
1633         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {\r
1634             return a + b;\r
1635         }\r
1636         else if ( a >= 0.0 ) {\r
1637             return a;\r
1638         }\r
1639         else if ( b >= 0.0 ) {\r
1640             return b;\r
1641         }\r
1642         return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;\r
1643     }\r
1644 \r
1645     static double calculateDistanceToAncestor( final PhylogenyNode anc, PhylogenyNode desc ) {\r
1646         double d = 0;\r
1647         boolean all_default = true;\r
1648         while ( anc != desc ) {\r
1649             if ( desc.getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {\r
1650                 d += desc.getDistanceToParent();\r
1651                 if ( all_default ) {\r
1652                     all_default = false;\r
1653                 }\r
1654             }\r
1655             desc = desc.getParent();\r
1656         }\r
1657         if ( all_default ) {\r
1658             return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;\r
1659         }\r
1660         return d;\r
1661     }\r
1662 \r
1663     /**\r
1664      * Deep copies the phylogeny originating from this node.\r
1665      */\r
1666     static PhylogenyNode copySubTree( final PhylogenyNode source ) {\r
1667         if ( source == null ) {\r
1668             return null;\r
1669         }\r
1670         else {\r
1671             final PhylogenyNode newnode = source.copyNodeData();\r
1672             if ( !source.isExternal() ) {\r
1673                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {\r
1674                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );\r
1675                 }\r
1676             }\r
1677             return newnode;\r
1678         }\r
1679     }\r
1680 \r
1681     /**\r
1682      * Shallow copies the phylogeny originating from this node.\r
1683      */\r
1684     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {\r
1685         if ( source == null ) {\r
1686             return null;\r
1687         }\r
1688         else {\r
1689             final PhylogenyNode newnode = source.copyNodeDataShallow();\r
1690             if ( !source.isExternal() ) {\r
1691                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {\r
1692                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );\r
1693                 }\r
1694             }\r
1695             return newnode;\r
1696         }\r
1697     }\r
1698 \r
1699     private final static List<PhylogenyNode> divideIntoSubTreesHelper( final PhylogenyNode node,\r
1700                                                                        final double min_distance_to_root ) {\r
1701         final List<PhylogenyNode> l = new ArrayList<PhylogenyNode>();\r
1702         final PhylogenyNode r = moveTowardsRoot( node, min_distance_to_root );\r
1703         for( final PhylogenyNode ext : r.getAllExternalDescendants() ) {\r
1704             if ( ext.getIndicator() != 0 ) {\r
1705                 throw new RuntimeException( "this should not have happened" );\r
1706             }\r
1707             ext.setIndicator( ( byte ) 1 );\r
1708             l.add( ext );\r
1709         }\r
1710         return l;\r
1711     }\r
1712 \r
1713     /**\r
1714      * Calculates the distance between PhylogenyNodes n1 and n2.\r
1715      * PRECONDITION: n1 is a descendant of n2.\r
1716      *\r
1717      * @param n1\r
1718      *            a descendant of n2\r
1719      * @param n2\r
1720      * @return distance between n1 and n2\r
1721      */\r
1722     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {\r
1723         double d = 0.0;\r
1724         while ( n1 != n2 ) {\r
1725             if ( n1.getDistanceToParent() > 0.0 ) {\r
1726                 d += n1.getDistanceToParent();\r
1727             }\r
1728             n1 = n1.getParent();\r
1729         }\r
1730         return d;\r
1731     }\r
1732 \r
1733     private static boolean match( final String s,\r
1734                                   final String query,\r
1735                                   final boolean case_sensitive,\r
1736                                   final boolean partial,\r
1737                                   final boolean regex ) {\r
1738         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {\r
1739             return false;\r
1740         }\r
1741         String my_s = s.trim();\r
1742         String my_query = query.trim();\r
1743         if ( !case_sensitive && !regex ) {\r
1744             my_s = my_s.toLowerCase();\r
1745             my_query = my_query.toLowerCase();\r
1746         }\r
1747         if ( regex ) {\r
1748             Pattern p = null;\r
1749             try {\r
1750                 if ( case_sensitive ) {\r
1751                     p = Pattern.compile( my_query );\r
1752                 }\r
1753                 else {\r
1754                     p = Pattern.compile( my_query, Pattern.CASE_INSENSITIVE );\r
1755                 }\r
1756             }\r
1757             catch ( final PatternSyntaxException e ) {\r
1758                 return false;\r
1759             }\r
1760             if ( p != null ) {\r
1761                 return p.matcher( my_s ).find();\r
1762             }\r
1763             else {\r
1764                 return false;\r
1765             }\r
1766         }\r
1767         else if ( partial ) {\r
1768             return my_s.indexOf( my_query ) >= 0;\r
1769         }\r
1770         else {\r
1771             Pattern p = null;\r
1772             try {\r
1773                 p = Pattern.compile( "(\\b|_)" + Pattern.quote( my_query ) + "(\\b|_)" );\r
1774             }\r
1775             catch ( final PatternSyntaxException e ) {\r
1776                 return false;\r
1777             }\r
1778             if ( p != null ) {\r
1779                 return p.matcher( my_s ).find();\r
1780             }\r
1781             else {\r
1782                 return false;\r
1783             }\r
1784         }\r
1785     }\r
1786 \r
1787     private final static PhylogenyNode moveTowardsRoot( final PhylogenyNode node, final double min_distance_to_root ) {\r
1788         PhylogenyNode n = node;\r
1789         PhylogenyNode prev = node;\r
1790         while ( min_distance_to_root < n.calculateDistanceToRoot() ) {\r
1791             prev = n;\r
1792             n = n.getParent();\r
1793         }\r
1794         return prev;\r
1795     }\r
1796 \r
1797     public static enum DESCENDANT_SORT_PRIORITY {\r
1798         NODE_NAME, SEQUENCE, TAXONOMY;\r
1799     }\r
1800 \r
1801     public static enum PhylogenyNodeField {\r
1802         CLADE_NAME,\r
1803         SEQUENCE_NAME,\r
1804         SEQUENCE_SYMBOL,\r
1805         TAXONOMY_CODE,\r
1806         TAXONOMY_COMMON_NAME,\r
1807         TAXONOMY_ID,\r
1808         TAXONOMY_ID_UNIPROT_1,\r
1809         TAXONOMY_ID_UNIPROT_2,\r
1810         TAXONOMY_SCIENTIFIC_NAME;\r
1811     }\r
1812 \r
1813     public static void addMolecularSeqsToTree( final Phylogeny phy, final Msa msa ) {\r
1814         for( int s = 0; s < msa.getNumberOfSequences(); ++s ) {\r
1815             final org.forester.sequence.MolecularSequence seq = msa.getSequence( s );\r
1816             final PhylogenyNode node = phy.getNode( seq.getIdentifier() );\r
1817             final org.forester.phylogeny.data.Sequence new_seq = new Sequence();\r
1818             new_seq.setMolecularSequenceAligned( true );\r
1819             new_seq.setMolecularSequence( seq.getMolecularSequenceAsString() );\r
1820             new_seq.setName( seq.getIdentifier() );\r
1821             try {\r
1822                 new_seq.setType( PhyloXmlUtil.SEQ_TYPE_PROTEIN );\r
1823             }\r
1824             catch ( final PhyloXmlDataFormatException ignore ) {\r
1825                 // do nothing\r
1826             }\r
1827             node.getNodeData().addSequence( new_seq );\r
1828         }\r
1829     }\r
1830 \r
1831     final private static class PhylogenyNodeSortTaxonomyPriority implements Comparator<PhylogenyNode> {\r
1832 \r
1833         @Override\r
1834         public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {\r
1835             if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {\r
1836                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )\r
1837                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {\r
1838                     return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()\r
1839                             .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );\r
1840                 }\r
1841                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )\r
1842                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {\r
1843                     return n1.getNodeData().getTaxonomy().getTaxonomyCode()\r
1844                             .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );\r
1845                 }\r
1846             }\r
1847             if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {\r
1848                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )\r
1849                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {\r
1850                     return n1.getNodeData().getSequence().getName().toLowerCase()\r
1851                             .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );\r
1852                 }\r
1853                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )\r
1854                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {\r
1855                     return n1.getNodeData().getSequence().getGeneName()\r
1856                             .compareTo( n2.getNodeData().getSequence().getGeneName() );\r
1857                 }\r
1858                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )\r
1859                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {\r
1860                     return n1.getNodeData().getSequence().getSymbol()\r
1861                             .compareTo( n2.getNodeData().getSequence().getSymbol() );\r
1862                 }\r
1863             }\r
1864             if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {\r
1865                 return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );\r
1866             }\r
1867             return 0;\r
1868         }\r
1869     }\r
1870 \r
1871     final private static class PhylogenyNodeSortSequencePriority implements Comparator<PhylogenyNode> {\r
1872 \r
1873         @Override\r
1874         public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {\r
1875             if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {\r
1876                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )\r
1877                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {\r
1878                     return n1.getNodeData().getSequence().getName().toLowerCase()\r
1879                             .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );\r
1880                 }\r
1881                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )\r
1882                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {\r
1883                     return n1.getNodeData().getSequence().getGeneName()\r
1884                             .compareTo( n2.getNodeData().getSequence().getGeneName() );\r
1885                 }\r
1886                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )\r
1887                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {\r
1888                     return n1.getNodeData().getSequence().getSymbol()\r
1889                             .compareTo( n2.getNodeData().getSequence().getSymbol() );\r
1890                 }\r
1891             }\r
1892             if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {\r
1893                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )\r
1894                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {\r
1895                     return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()\r
1896                             .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );\r
1897                 }\r
1898                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )\r
1899                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {\r
1900                     return n1.getNodeData().getTaxonomy().getTaxonomyCode()\r
1901                             .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );\r
1902                 }\r
1903             }\r
1904             if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {\r
1905                 return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );\r
1906             }\r
1907             return 0;\r
1908         }\r
1909     }\r
1910 \r
1911     final private static class PhylogenyNodeSortNodeNamePriority implements Comparator<PhylogenyNode> {\r
1912 \r
1913         @Override\r
1914         public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {\r
1915             if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {\r
1916                 return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );\r
1917             }\r
1918             if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {\r
1919                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )\r
1920                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {\r
1921                     return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()\r
1922                             .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );\r
1923                 }\r
1924                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )\r
1925                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {\r
1926                     return n1.getNodeData().getTaxonomy().getTaxonomyCode()\r
1927                             .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );\r
1928                 }\r
1929             }\r
1930             if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {\r
1931                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )\r
1932                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {\r
1933                     return n1.getNodeData().getSequence().getName().toLowerCase()\r
1934                             .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );\r
1935                 }\r
1936                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) )\r
1937                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) {\r
1938                     return n1.getNodeData().getSequence().getGeneName()\r
1939                             .compareTo( n2.getNodeData().getSequence().getGeneName() );\r
1940                 }\r
1941                 if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )\r
1942                         && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {\r
1943                     return n1.getNodeData().getSequence().getSymbol()\r
1944                             .compareTo( n2.getNodeData().getSequence().getSymbol() );\r
1945                 }\r
1946             }\r
1947             return 0;\r
1948         }\r
1949     }\r
1950 }\r