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