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