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