forester/java/src/org/forester/phylogeny/Phylogeny.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 // Copyright (C) 2000-2001 Washington University School of Medicine
   8 // and Howard Hughes Medical Institute
   9 // All rights reserved
  10 //
  11 // This library is free software; you can redistribute it and/or
  12 // modify it under the terms of the GNU Lesser General Public
  13 // License as published by the Free Software Foundation; either
  14 // version 2.1 of the License, or (at your option) any later version.
  15 //
  16 // This library is distributed in the hope that it will be useful,
  17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  19 // Lesser General Public License for more details.
  20 //
  21 // You should have received a copy of the GNU Lesser General Public
  22 // License along with this library; if not, write to the Free Software
  23 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  24 //
  25 // Contact: phylosoft @ gmail . com
  26 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
  27
  28 package org.forester.phylogeny;
  29
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collection;
  34 import java.util.HashMap;
  35 import java.util.Iterator;
  36 import java.util.List;
  37 import java.util.Map;
  38 import java.util.NoSuchElementException;
  39 import java.util.Vector;
  40
  41 import org.forester.io.parsers.nhx.NHXParser;
  42 import org.forester.io.writers.PhylogenyWriter;
  43 import org.forester.phylogeny.PhylogenyNode.NH_CONVERSION_SUPPORT_VALUE_STYLE;
  44 import org.forester.phylogeny.data.BranchData;
  45 import org.forester.phylogeny.data.Confidence;
  46 import org.forester.phylogeny.data.Identifier;
  47 import org.forester.phylogeny.data.PhylogenyDataUtil;
  48 import org.forester.phylogeny.data.Sequence;
  49 import org.forester.phylogeny.data.SequenceRelation;
  50 import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE;
  51 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  52 import org.forester.phylogeny.factories.PhylogenyFactory;
  53 import org.forester.phylogeny.iterators.ExternalForwardIterator;
  54 import org.forester.phylogeny.iterators.LevelOrderTreeIterator;
  55 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  56 import org.forester.phylogeny.iterators.PostorderTreeIterator;
  57 import org.forester.phylogeny.iterators.PreorderTreeIterator;
  58 import org.forester.util.FailedConditionCheckException;
  59 import org.forester.util.ForesterUtil;
  60
  61 public class Phylogeny {
  62
  63     public final static boolean                                 ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
  64     private PhylogenyNode                                       _root;
  65     private boolean                                             _rooted;
  66     private boolean                                             _allow_multiple_parents;
  67     private String                                              _name;
  68     private String                                              _type;
  69     private String                                              _description;
  70     private String                                              _distance_unit;
  71     private Confidence                                          _confidence;
  72     private Identifier                                          _identifier;
  73     private boolean                                             _rerootable;
  74     private HashMap<Long, PhylogenyNode>                        _id_to_node_map;
  75     private List<PhylogenyNode>                                 _external_nodes_set;
  76     private Collection<Sequence>                                _sequenceRelationQueries;
  77     private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
  78
  79     /**
  80      * Default Phylogeny constructor. Constructs an empty Phylogeny.
  81      */
  82     public Phylogeny() {
  83         init();
  84     }
  85
  86     /**
  87      * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
  88      * and sets the parent of this to parent.
  89      *
  90      * @param n
  91      *            the PhylogenyNode to add
  92      */
  93     public void addAsChild( final PhylogenyNode parent ) {
  94         if ( isEmpty() ) {
  95             throw new IllegalArgumentException( "Attempt to add an empty tree." );
  96         }
  97         if ( !isRooted() ) {
  98             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
  99         }
 100         parent.addAsChild( getRoot() );
 101         externalNodesHaveChanged();
 102     }
 103
 104     public void addAsSibling( final PhylogenyNode sibling ) {
 105         if ( isEmpty() ) {
 106             throw new IllegalArgumentException( "Attempt to add an empty tree." );
 107         }
 108         if ( !isRooted() ) {
 109             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
 110         }
 111         final int sibling_index = sibling.getChildNodeIndex();
 112         final PhylogenyNode new_node = new PhylogenyNode();
 113         final PhylogenyNode sibling_parent = sibling.getParent();
 114         new_node.setChild1( sibling );
 115         new_node.setChild2( getRoot() );
 116         new_node.setParent( sibling_parent );
 117         sibling.setParent( new_node );
 118         sibling_parent.setChildNode( sibling_index, new_node );
 119         final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT
 120                 : sibling.getDistanceToParent() / 2;
 121         new_node.setDistanceToParent( new_dist );
 122         sibling.setDistanceToParent( new_dist );
 123         externalNodesHaveChanged();
 124     }
 125
 126     /**
 127      * This calculates the height of the subtree emanating at n for rooted,
 128      * tree-shaped phylogenies
 129      *
 130      * @param n
 131      *            the root-node of a subtree
 132      * @return the height of the subtree emanating at n
 133      */
 134     public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) {
 135         if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) {
 136             return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0;
 137         }
 138         else {
 139             double max = -Double.MAX_VALUE;
 140             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 141                 final double l = calculateSubtreeHeight( n.getChildNode( i ),  take_collapse_into_account );
 142                 if ( l > max ) {
 143                     max = l;
 144                 }
 145             }
 146             return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0);
 147         }
 148     }
 149
 150     public void clearHashIdToNodeMap() {
 151         setIdToNodeMap( null );
 152     }
 153
 154     /**
 155      * Returns a deep copy of this Phylogeny.
 156      * <p>
 157      * (The resulting Phylogeny has its references in the external nodes
 158      * corrected, if they are lacking/obsolete in this.)
 159      */
 160     public Phylogeny copy() {
 161         return copy( _root );
 162     }
 163
 164     /**
 165      * Returns a deep copy of this Phylogeny.
 166      * <p>
 167      * (The resulting Phylogeny has its references in the external nodes
 168      * corrected, if they are lacking/obsolete in this.)
 169      */
 170     public Phylogeny copy( final PhylogenyNode source ) {
 171         final Phylogeny tree = new Phylogeny();
 172         if ( isEmpty() ) {
 173             tree.init();
 174             return tree;
 175         }
 176         tree._rooted = _rooted;
 177         tree._name = new String( _name );
 178         tree._description = new String( _description );
 179         tree._type = new String( _type );
 180         tree._rerootable = _rerootable;
 181         tree._distance_unit = new String( _distance_unit );
 182         if ( _confidence != null ) {
 183             tree._confidence = ( Confidence ) _confidence.copy();
 184         }
 185         if ( _identifier != null ) {
 186             tree._identifier = ( Identifier ) _identifier.copy();
 187         }
 188         tree.setAllowMultipleParents( isAllowMultipleParents() );
 189         tree._root = PhylogenyMethods.copySubTree( source );
 190         return tree;
 191     }
 192
 193     /**
 194      * Returns a shallow copy of this Phylogeny.
 195      * <p>
 196      * (The resulting Phylogeny has its references in the external nodes
 197      * corrected, if they are lacking/obsolete in this.)
 198      */
 199     public Phylogeny copyShallow() {
 200         return copyShallow( _root );
 201     }
 202
 203     public Phylogeny copyShallow( final PhylogenyNode source ) {
 204         final Phylogeny tree = new Phylogeny();
 205         if ( isEmpty() ) {
 206             tree.init();
 207             return tree;
 208         }
 209         tree._rooted = _rooted;
 210         tree._name = _name;
 211         tree._description = _description;
 212         tree._type = _type;
 213         tree._rerootable = _rerootable;
 214         tree._distance_unit = _distance_unit;
 215         tree._confidence = _confidence;
 216         tree._identifier = _identifier;
 217         tree.setAllowMultipleParents( isAllowMultipleParents() );
 218         tree._root = PhylogenyMethods.copySubTreeShallow( source );
 219         return tree;
 220     }
 221
 222     /**
 223      * Need to call clearHashIdToNodeMap() afterwards (not done automatically
 224      * to allow client multiple deletions in linear time).
 225      * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this
 226      * if tree is to be displayed.
 227      *
 228      * @param remove_us the parent node of the subtree to be deleted
 229      */
 230     public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
 231         if ( isEmpty() || ( remove_us.isRoot() && ( getNumberOfExternalNodes() != 1 ) ) ) {
 232             return;
 233         }
 234         if ( remove_us.isRoot() && ( getNumberOfExternalNodes() == 1 ) ) {
 235             init();
 236         }
 237         else if ( !collapse_resulting_node_with_one_desc ) {
 238             remove_us.getParent().removeChildNode( remove_us );
 239         }
 240         else {
 241             final PhylogenyNode removed_node = remove_us;
 242             final PhylogenyNode p = remove_us.getParent();
 243             if ( p.isRoot() ) {
 244                 if ( p.getNumberOfDescendants() == 2 ) {
 245                     if ( removed_node.isFirstChildNode() ) {
 246                         setRoot( getRoot().getChildNode( 1 ) );
 247                         getRoot().setParent( null );
 248                     }
 249                     else {
 250                         setRoot( getRoot().getChildNode( 0 ) );
 251                         getRoot().setParent( null );
 252                     }
 253                 }
 254                 else {
 255                     p.removeChildNode( removed_node.getChildNodeIndex() );
 256                 }
 257             }
 258             else {
 259                 final PhylogenyNode pp = removed_node.getParent().getParent();
 260                 if ( p.getNumberOfDescendants() == 2 ) {
 261                     final int pi = p.getChildNodeIndex();
 262                     if ( removed_node.isFirstChildNode() ) {
 263                         p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
 264                                                                                                          .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) );
 265                         pp.setChildNode( pi, p.getChildNode( 1 ) );
 266                     }
 267                     else {
 268                         p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
 269                                                                                                          .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
 270                         pp.setChildNode( pi, p.getChildNode( 0 ) );
 271                     }
 272                 }
 273                 else {
 274                     p.removeChildNode( removed_node.getChildNodeIndex() );
 275                 }
 276             }
 277         }
 278         remove_us.removeConnections();
 279         externalNodesHaveChanged();
 280     }
 281
 282     public void externalNodesHaveChanged() {
 283         _external_nodes_set = null;
 284     }
 285
 286     public String[] getAllExternalNodeNames() {
 287         int i = 0;
 288         if ( isEmpty() ) {
 289             return null;
 290         }
 291         final String[] names = new String[ getNumberOfExternalNodes() ];
 292         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 293             names[ i++ ] = new String( iter.next().getName() );
 294         }
 295         return names;
 296     }
 297
 298     public Confidence getConfidence() {
 299         return _confidence;
 300     }
 301
 302     public String getDescription() {
 303         return _description;
 304     }
 305
 306     public String getDistanceUnit() {
 307         return _distance_unit;
 308     }
 309
 310     public final static Phylogeny createInstanceFromNhxString( final String nhx ) throws IOException {
 311         final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 312         return factory.create( nhx, new NHXParser() )[ 0 ];
 313     }
 314
 315     /**
 316      *
 317      * Warning. The order of the returned nodes is random
 318      * -- and hence cannot be relied on.
 319      *
 320      * @return Unordered set of PhylogenyNode
 321      */
 322     public List<PhylogenyNode> getExternalNodes() {
 323         if ( _external_nodes_set == null ) {
 324             _external_nodes_set = new ArrayList<PhylogenyNode>();
 325             for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
 326                 final PhylogenyNode n = it.next();
 327                 if ( n.isExternal() ) {
 328                     _external_nodes_set.add( n );
 329                 }
 330             }
 331         }
 332         return _external_nodes_set;
 333     }
 334
 335
 336     /**
 337      * Returns the first external PhylogenyNode.
 338      */
 339     public PhylogenyNode getFirstExternalNode() {
 340         if ( isEmpty() ) {
 341             throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
 342         }
 343         PhylogenyNode node = getRoot();
 344         while ( node.isInternal() ) {
 345             node = node.getFirstChildNode();
 346         }
 347         return node;
 348     }
 349
 350     /**
 351      * This calculates the height for rooted, tree-shaped phylogenies. The
 352      * height is the longest distance from the root to an external node.
 353      *
 354      * @return the height for rooted, tree-shaped phylogenies
 355      */
 356     public double calculateHeight(final boolean take_collapse_into_account) {
 357         if ( isEmpty() ) {
 358             return 0.0;
 359         }
 360         return calculateSubtreeHeight( getRoot(), take_collapse_into_account );
 361     }
 362
 363     public Identifier getIdentifier() {
 364         return _identifier;
 365     }
 366
 367     /**
 368      * Returns the name of this Phylogeny.
 369      */
 370     public String getName() {
 371         return _name;
 372     }
 373
 374     /**
 375      * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
 376      * @return PhylogenyNode with matching ID, null if not found
 377      */
 378     public PhylogenyNode getNode( final long id ) throws NoSuchElementException {
 379         if ( isEmpty() ) {
 380             throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
 381         }
 382         if ( ( getIdToNodeMap() == null ) || getIdToNodeMap().isEmpty() ) {
 383             reHashIdToNodeMap();
 384         }
 385         return getIdToNodeMap().get( id );
 386     }
 387
 388     /**
 389      * Returns a PhylogenyNode of this Phylogeny which has a matching name.
 390      * Throws an Exception if seqname is not present in this or not unique.
 391      *
 392      * @param name
 393      *            name (String) of PhylogenyNode to find
 394      * @return PhylogenyNode with matchin name
 395      */
 396     public PhylogenyNode getNode( final String name ) {
 397         if ( isEmpty() ) {
 398             return null;
 399         }
 400         final List<PhylogenyNode> nodes = getNodes( name );
 401         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 402             throw new IllegalArgumentException( "node named \"" + name + "\" not found" );
 403         }
 404         if ( nodes.size() > 1 ) {
 405             throw new IllegalArgumentException( "node named \"" + name + "\" not unique" );
 406         }
 407         return nodes.get( 0 );
 408     }
 409
 410     /**
 411      * This is time-inefficient since it runs a iterator each time it is called.
 412      *
 413      */
 414     public int getNodeCount() {
 415         if ( isEmpty() ) {
 416             return 0;
 417         }
 418         int c = 0;
 419         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
 420             ++c;
 421         }
 422         return c;
 423     }
 424
 425     /**
 426      * Returns a List with references to all Nodes of this Phylogeny which have
 427      * a matching name.
 428      *
 429      * @param name
 430      *            name (String) of Nodes to find
 431      * @return Vector of references to Nodes of this Phylogeny with matching
 432      *         names
 433      * @see #getNodesWithMatchingSpecies(String)
 434      */
 435     public List<PhylogenyNode> getNodes( final String name ) {
 436         if ( isEmpty() ) {
 437             return null;
 438         }
 439         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 440         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 441             final PhylogenyNode n = iter.next();
 442             if ( n.getName().equals( name ) ) {
 443                 nodes.add( n );
 444             }
 445         }
 446         return nodes;
 447     }
 448
 449     public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
 450         if ( isEmpty() ) {
 451             return null;
 452         }
 453         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 454         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 455             final PhylogenyNode n = iter.next();
 456             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
 457                 nodes.add( n );
 458             }
 459         }
 460         return nodes;
 461     }
 462
 463     public List<PhylogenyNode> getNodesViaSequenceSymbol( final String seq_name ) {
 464         if ( isEmpty() ) {
 465             return null;
 466         }
 467         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 468         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 469             final PhylogenyNode n = iter.next();
 470             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) {
 471                 nodes.add( n );
 472             }
 473         }
 474         return nodes;
 475     }
 476
 477     public List<PhylogenyNode> getNodesViaGeneName( final String seq_name ) {
 478         if ( isEmpty() ) {
 479             return null;
 480         }
 481         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 482         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 483             final PhylogenyNode n = iter.next();
 484             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) {
 485                 nodes.add( n );
 486             }
 487         }
 488         return nodes;
 489     }
 490
 491     public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
 492         if ( isEmpty() ) {
 493             return null;
 494         }
 495         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 496         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 497             final PhylogenyNode n = iter.next();
 498             if ( n.getNodeData().isHasTaxonomy()
 499                     && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
 500                 nodes.add( n );
 501             }
 502         }
 503         return nodes;
 504     }
 505
 506     /**
 507      * Returns a Vector with references to all Nodes of this Phylogeny which
 508      * have a matching species name.
 509      *
 510      * @param specname
 511      *            species name (String) of Nodes to find
 512      * @return Vector of references to Nodes of this Phylogeny with matching
 513      *         species names.
 514      * @see #getNodes(String)
 515      */
 516     public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
 517         if ( isEmpty() ) {
 518             return null;
 519         }
 520         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 521         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 522             final PhylogenyNode n = iter.next();
 523             if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
 524                 nodes.add( n );
 525             }
 526         }
 527         return nodes;
 528     }
 529
 530     public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
 531         if ( isEmpty() ) {
 532             return null;
 533         }
 534         final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
 535         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 536             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
 537         }
 538         if ( nodes.size() > 1 ) {
 539             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
 540         }
 541         return nodes.get( 0 );
 542     }
 543
 544     public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
 545         if ( isEmpty() ) {
 546             return null;
 547         }
 548         final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
 549         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 550             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
 551         }
 552         if ( nodes.size() > 1 ) {
 553             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
 554         }
 555         return nodes.get( 0 );
 556     }
 557
 558     public int getNumberOfBranches() {
 559         if ( isEmpty() ) {
 560             return 0;
 561         }
 562         int c = 0;
 563         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
 564             ++c;
 565         }
 566         if ( !isRooted() ) {
 567             --c;
 568         }
 569         return c;
 570     }
 571
 572     public int getNumberOfInternalNodes() {
 573         if ( isEmpty() ) {
 574             return 0;
 575         }
 576         int c = 0;
 577         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 578             if ( iter.next().isInternal() ) {
 579                 ++c;
 580             }
 581         }
 582         if ( !isRooted() ) {
 583             --c;
 584         }
 585         return c;
 586     }
 587
 588     /**
 589      * Returns the sum of external Nodes of this Phylogeny (int).
 590      */
 591     public int getNumberOfExternalNodes() {
 592         if ( isEmpty() ) {
 593             return 0;
 594         }
 595         return getExternalNodes().size();
 596     }
 597
 598     /**
 599      * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
 600      * paralog are returned as List of node references.
 601      * <p>
 602      * PRECONDITION: This tree must be binary and rooted, and speciation -
 603      * duplication need to be assigned for each of its internal Nodes.
 604      * <p>
 605      * Returns null if this Phylogeny is empty or if n is internal.
 606      * <p>
 607      * (Last modified: 11/22/00) Olivier CHABROL :
 608      * olivier.chabrol@univ-provence.fr
 609      *
 610      * @param n
 611      *            external PhylogenyNode whose orthologs are to be returned
 612      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 613      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 614      *         internal
 615      */
 616     public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
 617         PhylogenyNode node = n;
 618         PhylogenyNode prev = null;
 619         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
 620         final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
 621         getTaxonomyMap( getRoot(), map );
 622         if ( !node.isExternal() || isEmpty() ) {
 623             return null;
 624         }
 625         final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
 626         if ( !node.isExternal() || isEmpty() ) {
 627             return null;
 628         }
 629         List<String> taxIdList = null;
 630         final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
 631         while ( !node.isRoot() ) {
 632             prev = node;
 633             node = node.getParent();
 634             taxIdList = map.get( node );
 635             if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
 636                 if ( node.getChildNode1() == prev ) {
 637                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
 638                                                    .getAllExternalDescendants() ) );
 639                 }
 640                 else {
 641                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
 642                                                    .getAllExternalDescendants() ) );
 643                 }
 644             }
 645         }
 646         return v;
 647     }
 648
 649     public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
 650         if ( _relevant_sequence_relation_types == null ) {
 651             _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
 652         }
 653         return _relevant_sequence_relation_types;
 654     }
 655
 656     /**
 657      * Returns the root PhylogenyNode of this Phylogeny.
 658      */
 659     public PhylogenyNode getRoot() {
 660         return _root;
 661     }
 662
 663     public Collection<Sequence> getSequenceRelationQueries() {
 664         return _sequenceRelationQueries;
 665     }
 666
 667     public String getType() {
 668         return _type;
 669     }
 670
 671     /**
 672      * Deletes this Phylogeny.
 673      */
 674     public void init() {
 675         _root = null;
 676         _rooted = false;
 677         _name = "";
 678         _description = "";
 679         _type = "";
 680         _distance_unit = "";
 681         _id_to_node_map = null;
 682         _confidence = null;
 683         _identifier = null;
 684         _rerootable = true;
 685         setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
 686     }
 687
 688     /**
 689      * Returns whether this is a completely binary tree (i.e. all internal nodes
 690      * are bifurcations).
 691      *
 692      */
 693     public boolean isCompletelyBinary() {
 694         if ( isEmpty() ) {
 695             return false;
 696         }
 697         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 698             final PhylogenyNode node = iter.next();
 699             if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
 700                 return false;
 701             }
 702         }
 703         return true;
 704     }
 705
 706     /**
 707      * Checks whether a Phylogeny object is deleted (or empty).
 708      *
 709      * @return true if the tree is deleted (or empty), false otherwise
 710      */
 711     public boolean isEmpty() {
 712         return ( getRoot() == null );
 713     }
 714
 715     public boolean isRerootable() {
 716         return _rerootable;
 717     }
 718
 719     /**
 720      * Returns true is this Phylogeny is rooted.
 721      */
 722     public boolean isRooted() {
 723         return _rooted;
 724     } // isRooted()
 725
 726     public boolean isTree() {
 727         return true;
 728     }
 729
 730     public PhylogenyNodeIterator iteratorExternalForward() {
 731         return new ExternalForwardIterator( this );
 732     }
 733
 734     public PhylogenyNodeIterator iteratorLevelOrder() {
 735         return new LevelOrderTreeIterator( this );
 736     }
 737
 738     public PhylogenyNodeIterator iteratorPostorder() {
 739         return new PostorderTreeIterator( this );
 740     }
 741
 742     public PhylogenyNodeIterator iteratorPreorder() {
 743         return new PreorderTreeIterator( this );
 744     }
 745
 746     /**
 747      * Resets the ID numbers of the nodes of this Phylogeny in level order,
 748      * starting with start_label (for the root). <br>
 749      * WARNING. After this method has been called, node IDs are no longer
 750      * unique.
 751      */
 752     public void levelOrderReID() {
 753         if ( isEmpty() ) {
 754             return;
 755         }
 756         _id_to_node_map = null;
 757         long max = 0;
 758         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 759             final PhylogenyNode node = it.next();
 760             if ( node.isRoot() ) {
 761                 node.setId( PhylogenyNode.getNodeCount() );
 762             }
 763             else {
 764                 node.setId( node.getParent().getId() + 1 );
 765                 if ( node.getId() > max ) {
 766                     max = node.getId();
 767                 }
 768             }
 769         }
 770         PhylogenyNode.setNodeCount( max + 1 );
 771     }
 772
 773     /**
 774      * Prints descriptions of all external Nodes of this Phylogeny to
 775      * System.out.
 776      */
 777     public void printExtNodes() {
 778         if ( isEmpty() ) {
 779             return;
 780         }
 781         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 782             System.out.println( iter.next() + "\n" );
 783         }
 784     }
 785
 786     /**
 787      * (Re)counts the number of children for each PhylogenyNode of this
 788      * Phylogeny. As an example, this method needs to be called after a
 789      * Phylogeny has been reRooted and it is to be displayed.
 790      *
 791      * @param consider_collapsed_nodes
 792      *            set to true to take into account collapsed nodes (collapsed
 793      *            nodes have 1 child).
 794      */
 795     public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
 796         if ( isEmpty() ) {
 797             return;
 798         }
 799         for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
 800             final PhylogenyNode node = iter.next();
 801             if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
 802                 node.setSumExtNodes( 1 );
 803             }
 804             else {
 805                 int sum = 0;
 806                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 807                     sum += node.getChildNode( i ).getNumberOfExternalNodes();
 808                 }
 809                 node.setSumExtNodes( sum );
 810             }
 811         }
 812     }
 813
 814     /**
 815      * Places the root of this Phylogeny on the parent branch of the
 816      * PhylogenyNode with a corresponding ID. The new root is always placed on
 817      * the middle of the branch. If the resulting reRooted Phylogeny is to be
 818      * used any further, in most cases the following methods have to be called
 819      * on the resulting Phylogeny:
 820      * <p>
 821      * <li>recalculateNumberOfExternalDescendants(boolean)
 822      * <li>recalculateAndReset()
 823      *
 824      * @param id
 825      *            ID (int) of PhylogenyNode of this Phylogeny
 826      */
 827     public void reRoot( final long id ) {
 828         reRoot( getNode( id ) );
 829     }
 830
 831     /**
 832      * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
 833      * The new root is always placed on the middle of the branch.
 834      * <p>
 835      * If the resulting reRooted Phylogeny is to be used any further, in most
 836      * cases the following three methods have to be called on the resulting
 837      * Phylogeny:
 838      * <ul>
 839      * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
 840      * </ul>
 841      * <p>
 842      * (Last modified: 10/01/01)
 843      *
 844      * @param n
 845      *            PhylogenyNode of this Phylogeny\
 846      */
 847     public void reRoot( final PhylogenyNode n ) {
 848         reRoot( n, -1 );
 849     }
 850
 851     public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
 852         if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
 853             return;
 854         }
 855         setRooted( true );
 856         if ( n.isRoot() ) {
 857             return;
 858         }
 859         else if ( n.getParent().isRoot() ) {
 860             if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
 861                 final double d = n.getParent().getChildNode1().getDistanceToParent()
 862                         + n.getParent().getChildNode2().getDistanceToParent();
 863                 PhylogenyNode other;
 864                 if ( n.getChildNodeIndex() == 0 ) {
 865                     other = n.getParent().getChildNode2();
 866                 }
 867                 else {
 868                     other = n.getParent().getChildNode1();
 869                 }
 870                 n.setDistanceToParent( distance_n_to_parent );
 871                 final double dm = d - distance_n_to_parent;
 872                 if ( dm >= 0 ) {
 873                     other.setDistanceToParent( dm );
 874                 }
 875                 else {
 876                     other.setDistanceToParent( 0 );
 877                 }
 878             }
 879             if ( n.getParent().getNumberOfDescendants() > 2 ) {
 880                 final int index = n.getChildNodeIndex();
 881                 final double dn = n.getDistanceToParent();
 882                 final PhylogenyNode prev_root = getRoot();
 883                 prev_root.getDescendants().remove( index );
 884                 final PhylogenyNode new_root = new PhylogenyNode();
 885                 new_root.setChildNode( 0, n );
 886                 new_root.setChildNode( 1, prev_root );
 887                 if ( n.getBranchDataDirectly() != null ) {
 888                     prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
 889                 }
 890                 setRoot( new_root );
 891                 if ( distance_n_to_parent >= 0 ) {
 892                     n.setDistanceToParent( distance_n_to_parent );
 893                     final double d = dn - distance_n_to_parent;
 894                     if ( d >= 0 ) {
 895                         prev_root.setDistanceToParent( d );
 896                     }
 897                     else {
 898                         prev_root.setDistanceToParent( 0 );
 899                     }
 900                 }
 901                 else {
 902                     if ( dn >= 0 ) {
 903                         final double d = dn / 2.0;
 904                         n.setDistanceToParent( d );
 905                         prev_root.setDistanceToParent( d );
 906                     }
 907                 }
 908             }
 909         }
 910         else {
 911             PhylogenyNode a = n;
 912             PhylogenyNode b = null;
 913             PhylogenyNode c = null;
 914             final PhylogenyNode new_root = new PhylogenyNode();
 915             double distance1 = 0.0;
 916             double distance2 = 0.0;
 917             BranchData branch_data_1 = null;
 918             BranchData branch_data_2 = null;
 919             b = a.getParent();
 920             c = b.getParent();
 921             new_root.setChildNode( 0, a );
 922             new_root.setChildNode( 1, b );
 923             distance1 = c.getDistanceToParent();
 924             if ( c.getBranchDataDirectly() != null ) {
 925                 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
 926             }
 927             c.setDistanceToParent( b.getDistanceToParent() );
 928             if ( b.getBranchDataDirectly() != null ) {
 929                 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
 930             }
 931             if ( a.getBranchDataDirectly() != null ) {
 932                 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
 933             }
 934             // New root is always placed in the middle of the branch:
 935             if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
 936                 b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
 937             }
 938             else {
 939                 if ( distance_n_to_parent >= 0.0 ) {
 940                     final double diff = a.getDistanceToParent() - distance_n_to_parent;
 941                     a.setDistanceToParent( distance_n_to_parent );
 942                     b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
 943                 }
 944                 else {
 945                     final double d = a.getDistanceToParent() / 2.0;
 946                     a.setDistanceToParent( d );
 947                     b.setDistanceToParent( d );
 948                 }
 949             }
 950             b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
 951             // moving to the old root, swapping references:
 952             while ( !c.isRoot() ) {
 953                 a = b;
 954                 b = c;
 955                 c = c.getParent();
 956                 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
 957                 b.setParent( a );
 958                 distance2 = c.getDistanceToParent();
 959                 branch_data_2 = c.getBranchDataDirectly();
 960                 c.setDistanceToParent( distance1 );
 961                 c.setBranchData( branch_data_1 );
 962                 distance1 = distance2;
 963                 branch_data_1 = branch_data_2;
 964             }
 965             // removing the old root:
 966             if ( c.getNumberOfDescendants() == 2 ) {
 967                 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
 968                 node.setParent( b );
 969                 if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
 970                         && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
 971                     node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
 972                 }
 973                 else {
 974                     node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
 975                                               + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
 976                 }
 977                 if ( c.getBranchDataDirectly() != null ) {
 978                     node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
 979                 }
 980                 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
 981                     if ( b.getChildNode( i ) == c ) {
 982                         b.setChildNodeOnly( i, node );
 983                         break;
 984                     }
 985                 }
 986             }
 987             else {
 988                 c.setParent( b );
 989                 c.removeChildNode( b.getChildNodeIndex( c ) );
 990             }
 991             setRoot( new_root );
 992         }
 993     }
 994
 995     /**
 996      * Sets all Nodes of this Phylogeny to not-collapsed.
 997      * <p>
 998      * In most cases methods adjustNodeCount(false) and recalculateAndReset()
 999      * need to be called after this method has been called.
1000      */
1001     public void setAllNodesToNotCollapse() {
1002         if ( isEmpty() ) {
1003             return;
1004         }
1005         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1006             final PhylogenyNode node = iter.next();
1007             node.setCollapse( false );
1008         }
1009     }
1010
1011     public void setConfidence( final Confidence confidence ) {
1012         _confidence = confidence;
1013     }
1014
1015     public void setDescription( final String description ) {
1016         _description = description;
1017     }
1018
1019     public void setDistanceUnit( final String _distance_unit ) {
1020         this._distance_unit = _distance_unit;
1021     }
1022
1023     public void setIdentifier( final Identifier identifier ) {
1024         _identifier = identifier;
1025     }
1026
1027     public void setIdToNodeMap( final HashMap<Long, PhylogenyNode> idhash ) {
1028         _id_to_node_map = idhash;
1029     }
1030
1031     /**
1032      * Sets the indicators of all Nodes of this Phylogeny to 0.
1033      */
1034     public void setIndicatorsToZero() {
1035         if ( isEmpty() ) {
1036             return;
1037         }
1038         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1039             iter.next().setIndicator( ( byte ) 0 );
1040         }
1041     } // setIndicatorsToZero()
1042
1043     /**
1044      * Sets the name of this Phylogeny to s.
1045      */
1046     public void setName( final String s ) {
1047         _name = s;
1048     }
1049
1050     public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1051         _relevant_sequence_relation_types = types;
1052     }
1053
1054     public void setRerootable( final boolean rerootable ) {
1055         _rerootable = rerootable;
1056     }
1057
1058     public void setRoot( final PhylogenyNode n ) {
1059         _root = n;
1060     }
1061
1062     /**
1063      * Sets whether this Phylogeny is rooted or not.
1064      */
1065     public void setRooted( final boolean b ) {
1066         _rooted = b;
1067     }
1068
1069     public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1070         _sequenceRelationQueries = sequencesByName;
1071     }
1072
1073     public void setType( final String type ) {
1074         _type = type;
1075     }
1076
1077     public String toNewHampshire() {
1078         return toNewHampshire( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1079     }
1080
1081     public String toNewHampshire( final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) {
1082         try {
1083             return new PhylogenyWriter().toNewHampshire( this, true, nh_conversion_support_style ).toString();
1084         }
1085         catch ( final IOException e ) {
1086             throw new Error( "this should not have happend: " + e.getMessage() );
1087         }
1088     }
1089
1090     public String toNewHampshireX() {
1091         try {
1092             return new PhylogenyWriter().toNewHampshireX( this ).toString();
1093         }
1094         catch ( final IOException e ) {
1095             throw new Error( "this should not have happend: " + e.getMessage() );
1096         }
1097     }
1098
1099     public String toNexus() {
1100         return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1101     }
1102
1103     public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
1104         try {
1105             return new PhylogenyWriter().toNexus( this, svs ).toString();
1106         }
1107         catch ( final IOException e ) {
1108             throw new Error( "this should not have happend: " + e.getMessage() );
1109         }
1110     }
1111
1112     public String toPhyloXML( final int phyloxml_level ) {
1113         try {
1114             return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1115         }
1116         catch ( final IOException e ) {
1117             throw new Error( "this should not have happend: " + e.getMessage() );
1118         }
1119     }
1120
1121     // ---------------------------------------------------------
1122     // Writing of Phylogeny to Strings
1123     // ---------------------------------------------------------
1124     /**
1125      * Converts this Phylogeny to a New Hampshire X (String) representation.
1126      *
1127      * @return New Hampshire X (String) representation of this
1128      * @see #toNewHampshireX()
1129      */
1130     @Override
1131     public String toString() {
1132         return toNewHampshireX();
1133     }
1134
1135     /**
1136      * Removes the root PhylogenyNode this Phylogeny.
1137      */
1138     public void unRoot() throws RuntimeException {
1139         if ( !isTree() ) {
1140             throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1141         }
1142         if ( isEmpty() ) {
1143             return;
1144         }
1145         setIndicatorsToZero();
1146         if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {
1147             return;
1148         }
1149         setRooted( false );
1150         return;
1151     } // unRoot()
1152
1153     private HashMap<Long, PhylogenyNode> getIdToNodeMap() {
1154         return _id_to_node_map;
1155     }
1156
1157     /**
1158      * Return Node by TaxonomyId Olivier CHABROL :
1159      * olivier.chabrol@univ-provence.fr
1160      *
1161      * @param taxonomyID
1162      *            search taxonomy identifier
1163      * @param nodes
1164      *            sublist node to search
1165      * @return List node with the same taxonomy identifier
1166      */
1167     private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
1168         final List<PhylogenyNode> retour = new ArrayList<PhylogenyNode>();
1169         for( final PhylogenyNode node : nodes ) {
1170             if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
1171                 retour.add( node );
1172             }
1173         }
1174         return retour;
1175     }
1176
1177     /**
1178      * List all species contains in all leaf under a node Olivier CHABROL :
1179      * olivier.chabrol@univ-provence.fr
1180      *
1181      * @param node
1182      *            PhylogenyNode whose sub node species are returned
1183      * @return species contains in all leaf under the param node
1184      */
1185     private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
1186         final List<String> taxonomyList = new ArrayList<String>();
1187         final List<PhylogenyNode> childs = node.getAllExternalDescendants();
1188         String speciesId = null;
1189         for( final PhylogenyNode phylogenyNode : childs ) {
1190             // taxId = new Long(phylogenyNode.getTaxonomyID());
1191             speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
1192             if ( !taxonomyList.contains( speciesId ) ) {
1193                 taxonomyList.add( speciesId );
1194             }
1195         }
1196         return taxonomyList;
1197     }
1198
1199     /**
1200      * Create a map [<PhylogenyNode, List<String>], the list contains the
1201      * species contains in all leaf under phylogeny node Olivier CHABROL :
1202      * olivier.chabrol@univ-provence.fr
1203      *
1204      * @param node
1205      *            the tree root node
1206      * @param map
1207      *            map to fill
1208      */
1209     private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
1210         // node is leaf
1211         if ( node.isExternal() ) {
1212             return;
1213         }
1214         map.put( node, getSubNodeTaxonomy( node ) );
1215         getTaxonomyMap( node.getChildNode1(), map );
1216         getTaxonomyMap( node.getChildNode2(), map );
1217     }
1218
1219     private boolean isAllowMultipleParents() {
1220         return _allow_multiple_parents;
1221     }
1222
1223     /**
1224      * Util method to check if all element of a list is contains in the
1225      * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
1226      *
1227      * @param list
1228      *            list to be check
1229      * @param rangeList
1230      *            the range list to compare
1231      * @return <code>true</code> if all param list element are contains in param
1232      *         rangeList, <code>false</code> otherwise.
1233      */
1234     private boolean isContains( final List<String> list, final List<String> rangeList ) {
1235         if ( list.size() > rangeList.size() ) {
1236             return false;
1237         }
1238         String l = null;
1239         for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
1240             l = iterator.next();
1241             if ( !rangeList.contains( l ) ) {
1242                 return false;
1243             }
1244         }
1245         return true;
1246     }
1247
1248     /**
1249      * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
1250      * corresponding PhylogenyNode, in order to make method getNode( id ) run in
1251      * constant time. Important: The user is responsible for calling this method
1252      * (again) after this Phylogeny has been changed/created/renumbered.
1253      */
1254     private void reHashIdToNodeMap() {
1255         if ( isEmpty() ) {
1256             return;
1257         }
1258         setIdToNodeMap( new HashMap<Long, PhylogenyNode>() );
1259         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1260             final PhylogenyNode node = iter.next();
1261             getIdToNodeMap().put( node.getId(), node );
1262         }
1263     }
1264
1265     private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1266         _allow_multiple_parents = allow_multiple_parents;
1267     }
1268 }