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