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

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