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