2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
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
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.
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.
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
25 // Contact: phylosoft @ gmail . com
26 // WWW: www.phylosoft.org/forester
28 package org.forester.phylogeny;
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;
38 import java.util.NoSuchElementException;
39 import java.util.Vector;
41 import org.forester.io.writers.PhylogenyWriter;
42 import org.forester.phylogeny.PhylogenyNodeI.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;
58 public class Phylogeny {
60 public final static boolean ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
61 private PhylogenyNode _root;
62 private boolean _rooted;
63 private boolean _allow_multiple_parents;
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> _idhash;
72 private List<PhylogenyNode> _external_nodes_set;
73 private Collection<Sequence> _sequenceRelationQueries;
74 private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
77 * Default Phylogeny constructor. Constructs an empty Phylogeny.
84 * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
85 * and sets the parent of this to parent.
88 * the PhylogenyNode to add
90 public void addAsChild( final PhylogenyNode parent ) {
92 throw new IllegalArgumentException( "Attempt to add an empty tree." );
95 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
97 parent.addAsChild( getRoot() );
98 externalNodesHaveChanged();
101 public void addAsSibling( final PhylogenyNode sibling ) {
103 throw new IllegalArgumentException( "Attempt to add an empty tree." );
106 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
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();
124 * This calculates the height of the subtree emanating at n for rooted,
125 * tree-shaped phylogenies
128 * the root-node of a subtree
129 * @return the height of the subtree emanating at n
131 public double calculateSubtreeHeight( final PhylogenyNode n ) {
132 if ( n.isExternal() || n.isCollapse() ) {
133 return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
136 double max = -Double.MAX_VALUE;
137 for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
138 final double l = calculateSubtreeHeight( n.getChildNode( i ) );
143 return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
148 * Returns a deep copy of this Phylogeny.
150 * (The resulting Phylogeny has its references in the external nodes
151 * corrected, if they are lacking/obsolete in this.)
153 public Phylogeny copy() {
154 return copy( _root );
158 * Returns a shallow copy of this Phylogeny.
160 * (The resulting Phylogeny has its references in the external nodes
161 * corrected, if they are lacking/obsolete in this.)
163 public Phylogeny copyShallow() {
164 return copyShallow( _root );
167 public Phylogeny copyShallow( final PhylogenyNode source ) {
168 final Phylogeny tree = new Phylogeny();
173 tree._rooted = _rooted;
175 tree._description = _description;
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 );
187 * Returns a deep copy of this Phylogeny.
189 * (The resulting Phylogeny has its references in the external nodes
190 * corrected, if they are lacking/obsolete in this.)
192 public Phylogeny copy( final PhylogenyNode source ) {
193 final Phylogeny tree = new Phylogeny();
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();
207 if ( _identifier != null ) {
208 tree._identifier = ( Identifier ) _identifier.copy();
210 tree.setAllowMultipleParents( isAllowMultipleParents() );
211 tree._root = PhylogenyMethods.copySubTree( source );
216 * Need the delete and/or rehash _idhash (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.
221 * @param remove_us the parent node of the subtree to be deleted
223 public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
224 if ( isEmpty() || ( remove_us.isRoot() && ( getNumberOfExternalNodes() != 1 ) ) ) {
227 if ( remove_us.isRoot() && ( getNumberOfExternalNodes() == 1 ) ) {
230 else if ( !collapse_resulting_node_with_one_desc ) {
231 remove_us.getParent().removeChildNode( remove_us );
234 final PhylogenyNode removed_node = remove_us;
235 final PhylogenyNode p = remove_us.getParent();
237 if ( p.getNumberOfDescendants() == 2 ) {
238 if ( removed_node.isFirstChildNode() ) {
239 setRoot( getRoot().getChildNode( 1 ) );
240 getRoot().setParent( null );
243 setRoot( getRoot().getChildNode( 0 ) );
244 getRoot().setParent( null );
248 p.removeChildNode( removed_node.getChildNodeIndex() );
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 ) );
261 p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
262 .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
263 pp.setChildNode( pi, p.getChildNode( 0 ) );
267 p.removeChildNode( removed_node.getChildNodeIndex() );
271 remove_us.removeConnections();
273 externalNodesHaveChanged();
276 public void externalNodesHaveChanged() {
277 _external_nodes_set = null;
280 public String[] getAllExternalNodeNames() {
285 final String[] names = new String[ getNumberOfExternalNodes() ];
286 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
287 names[ i++ ] = new String( iter.next().getName() );
292 public Confidence getConfidence() {
296 public String getDescription() {
300 public String getDistanceUnit() {
301 return _distance_unit;
306 * Warning. The order of the returned nodes is random
307 * -- and hence cannot be relied on.
309 * @return Unordered set of PhylogenyNode
311 public List<PhylogenyNode> getExternalNodes() {
312 if ( _external_nodes_set == null ) {
313 _external_nodes_set = new ArrayList<PhylogenyNode>();
314 for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
315 final PhylogenyNode n = it.next();
316 if ( n.isExternal() ) {
317 _external_nodes_set.add( n );
321 return _external_nodes_set;
325 * Returns the number of duplications of this Phylogeny (int). A return
326 * value of -1 indicates that the number of duplications is unknown.
328 // public int getNumberOfDuplications() {
329 // return _number_of_duplications;
330 // } // getNumberOfDuplications()
332 * Sets the number of duplications of this Phylogeny (int). A value of -1
333 * indicates that the number of duplications is unknown.
336 * set to true for clean NH format
338 // public void setNumberOfDuplications( int i ) {
340 // _number_of_duplications = -1;
343 // _number_of_duplications = i;
345 // } // setNumberOfDuplications( int )
347 * Returns the first external PhylogenyNode.
349 public PhylogenyNode getFirstExternalNode() {
351 throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
353 PhylogenyNode node = getRoot();
354 while ( node.isInternal() ) {
355 node = node.getFirstChildNode();
361 * This calculates the height for rooted, tree-shaped phylogenies. The
362 * height is the longest distance from the root to an external node. Please
363 * note. Child nodes of collapsed nodes are ignored -- which is useful for
364 * display purposes but might be misleading for other applications.
366 * @return the height for rooted, tree-shaped phylogenies
368 public double getHeight() {
372 return calculateSubtreeHeight( getRoot() );
375 public Identifier getIdentifier() {
379 // ---------------------------------------------------------
380 // Modification of Phylogeny topology and Phylogeny appearance
381 // ---------------------------------------------------------
382 private HashMap<Integer, PhylogenyNode> getIdHash() {
387 * Returns the name of this Phylogeny.
389 public String getName() {
394 * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
395 * Takes O(n) time. After method hashIDs() has been called it runs in
399 * ID number (int) of the PhylogenyNode to find
400 * @return PhylogenyNode with matching ID, null if not found
402 public PhylogenyNode getNode( final int id ) throws NoSuchElementException {
404 throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
406 if ( _idhash != null ) {
407 return _idhash.get( id );
410 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
411 final PhylogenyNode node = iter.next();
412 if ( node.getId() == id ) {
421 * Returns a PhylogenyNode of this Phylogeny which has a matching name.
422 * Throws an Exception if seqname is not present in this or not unique.
425 * name (String) of PhylogenyNode to find
426 * @return PhylogenyNode with matchin name
428 public PhylogenyNode getNode( final String name ) {
432 final List<PhylogenyNode> nodes = getNodes( name );
433 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
434 throw new IllegalArgumentException( "node named [" + name + "] not found" );
436 if ( nodes.size() > 1 ) {
437 throw new IllegalArgumentException( "node named [" + name + "] not unique" );
439 return nodes.get( 0 );
443 * Return Node by TaxonomyId Olivier CHABROL :
444 * olivier.chabrol@univ-provence.fr
447 * search taxonomy identifier
449 * sublist node to search
450 * @return List node with the same taxonomy identifier
452 private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
453 final List<PhylogenyNode> retour = new ArrayList<PhylogenyNode>();
454 for( final PhylogenyNode node : nodes ) {
455 if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
463 * Returns a List with references to all Nodes of this Phylogeny which have
467 * name (String) of Nodes to find
468 * @return Vector of references to Nodes of this Phylogeny with matching
470 * @see #getNodesWithMatchingSpecies(String)
472 public List<PhylogenyNode> getNodes( final String name ) {
476 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
477 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
478 final PhylogenyNode n = iter.next();
479 if ( n.getName().equals( name ) ) {
486 public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
490 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
491 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
492 final PhylogenyNode n = iter.next();
493 if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
500 public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
504 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
505 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
506 final PhylogenyNode n = iter.next();
507 if ( n.getNodeData().isHasTaxonomy()
508 && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
516 * Returns a Vector with references to all Nodes of this Phylogeny which
517 * have a matching species name.
520 * species name (String) of Nodes to find
521 * @return Vector of references to Nodes of this Phylogeny with matching
523 * @see #getNodes(String)
525 public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
529 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
530 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
531 final PhylogenyNode n = iter.next();
532 if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
539 public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
543 final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
544 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
545 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
547 if ( nodes.size() > 1 ) {
548 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
550 return nodes.get( 0 );
553 public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
557 final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
558 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
559 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
561 if ( nodes.size() > 1 ) {
562 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
564 return nodes.get( 0 );
568 * This is time-inefficient since it runs a iterator each time it is called.
571 public int getNodeCount() {
576 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
582 public int getNumberOfBranches() {
587 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
597 * Returns the sum of external Nodes of this Phylogeny (int).
599 public int getNumberOfExternalNodes() {
603 return getExternalNodes().size();
607 * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
608 * paralog are returned as List of node references.
610 * PRECONDITION: This tree must be binary and rooted, and speciation -
611 * duplication need to be assigned for each of its internal Nodes.
613 * Returns null if this Phylogeny is empty or if n is internal.
615 * (Last modified: 11/22/00) Olivier CHABROL :
616 * olivier.chabrol@univ-provence.fr
619 * external PhylogenyNode whose orthologs are to be returned
620 * @return Vector of references to all orthologous Nodes of PhylogenyNode n
621 * of this Phylogeny, null if this Phylogeny is empty or if n is
624 public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
625 PhylogenyNode node = n;
626 PhylogenyNode prev = null;
627 final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
628 final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
629 getTaxonomyMap( getRoot(), map );
630 if ( !node.isExternal() || isEmpty() ) {
633 final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
634 if ( !node.isExternal() || isEmpty() ) {
637 List<String> taxIdList = null;
638 final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
639 while ( !node.isRoot() ) {
641 node = node.getParent();
642 taxIdList = map.get( node );
643 if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
644 if ( node.getChildNode1() == prev ) {
645 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
646 .getAllExternalDescendants() ) );
649 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
650 .getAllExternalDescendants() ) );
657 public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
658 if ( _relevant_sequence_relation_types == null ) {
659 _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
661 return _relevant_sequence_relation_types;
665 * Returns the root PhylogenyNode of this Phylogeny.
667 public PhylogenyNode getRoot() {
671 public Collection<Sequence> getSequenceRelationQueries() {
672 return _sequenceRelationQueries;
676 * List all species contains in all leaf under a node Olivier CHABROL :
677 * olivier.chabrol@univ-provence.fr
680 * PhylogenyNode whose sub node species are returned
681 * @return species contains in all leaf under the param node
683 private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
684 final List<String> taxonomyList = new ArrayList<String>();
685 final List<PhylogenyNode> childs = node.getAllExternalDescendants();
686 String speciesId = null;
687 for( final PhylogenyNode phylogenyNode : childs ) {
688 // taxId = new Long(phylogenyNode.getTaxonomyID());
689 speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
690 if ( !taxonomyList.contains( speciesId ) ) {
691 taxonomyList.add( speciesId );
698 * Create a map [<PhylogenyNode, List<String>], the list contains the
699 * species contains in all leaf under phylogeny node Olivier CHABROL :
700 * olivier.chabrol@univ-provence.fr
707 private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
709 if ( node.isExternal() ) {
712 map.put( node, getSubNodeTaxonomy( node ) );
713 getTaxonomyMap( node.getChildNode1(), map );
714 getTaxonomyMap( node.getChildNode2(), map );
717 public String getType() {
722 * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
723 * corresponding PhylogenyNode, in order to make method getNode( id ) run in
724 * constant time. Important: The user is responsible for calling this method
725 * (again) after this Phylogeny has been changed/created/renumbered.
727 public void hashIDs() {
731 setIdHash( new HashMap<Integer, PhylogenyNode>() );
732 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
733 final PhylogenyNode node = iter.next();
734 getIdHash().put( node.getId(), node );
739 * Deletes this Phylogeny.
752 setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
755 private boolean isAllowMultipleParents() {
756 return _allow_multiple_parents;
760 * Returns whether this is a completely binary tree (i.e. all internal nodes
764 public boolean isCompletelyBinary() {
768 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
769 final PhylogenyNode node = iter.next();
770 if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
778 * Util method to check if all element of a list is contains in the
779 * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
784 * the range list to compare
785 * @return <code>true</code> if all param list element are contains in param
786 * rangeList, <code>false</code> otherwise.
788 private boolean isContains( final List<String> list, final List<String> rangeList ) {
789 if ( list.size() > rangeList.size() ) {
793 for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
795 if ( !rangeList.contains( l ) ) {
803 * Checks whether a Phylogeny object is deleted (or empty).
805 * @return true if the tree is deleted (or empty), false otherwise
807 public boolean isEmpty() {
808 return ( getRoot() == null );
811 public boolean isRerootable() {
816 * Returns true is this Phylogeny is rooted.
818 public boolean isRooted() {
822 public boolean isTree() {
826 public PhylogenyNodeIterator iteratorExternalForward() {
827 return new ExternalForwardIterator( this );
830 public PhylogenyNodeIterator iteratorLevelOrder() {
831 return new LevelOrderTreeIterator( this );
834 public PhylogenyNodeIterator iteratorPostorder() {
835 return new PostorderTreeIterator( this );
838 public PhylogenyNodeIterator iteratorPreorder() {
839 return new PreorderTreeIterator( this );
843 * Resets the ID numbers of the nodes of this Phylogeny in level order,
844 * starting with start_label (for the root). <br>
845 * WARNING. After this method has been called, node IDs are no longer
848 public void levelOrderReID() {
854 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
855 final PhylogenyNode node = it.next();
856 if ( node.isRoot() ) {
857 node.setId( PhylogenyNode.getNodeCount() );
860 node.setId( node.getParent().getId() + 1 );
861 if ( node.getId() > max ) {
866 PhylogenyNode.setNodeCount( max + 1 );
869 public void preOrderReId() {
874 int i = PhylogenyNode.getNodeCount();
875 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
876 it.next().setId( i++ );
878 PhylogenyNode.setNodeCount( i );
882 * Prints descriptions of all external Nodes of this Phylogeny to
885 public void printExtNodes() {
889 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
890 System.out.println( iter.next() + "\n" );
895 * (Re)counts the number of children for each PhylogenyNode of this
896 * Phylogeny. As an example, this method needs to be called after a
897 * Phylogeny has been reRooted and it is to be displayed.
899 * @param consider_collapsed_nodes
900 * set to true to take into account collapsed nodes (collapsed
901 * nodes have 1 child).
903 public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
907 for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
908 final PhylogenyNode node = iter.next();
909 if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
910 node.setSumExtNodes( 1 );
914 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
915 sum += node.getChildNode( i ).getNumberOfExternalNodes();
917 node.setSumExtNodes( sum );
923 * Places the root of this Phylogeny on the parent branch of the
924 * PhylogenyNode with a corresponding ID. The new root is always placed on
925 * the middle of the branch. If the resulting reRooted Phylogeny is to be
926 * used any further, in most cases the following methods have to be called
927 * on the resulting Phylogeny:
929 * <li>recalculateNumberOfExternalDescendants(boolean)
930 * <li>recalculateAndReset()
933 * ID (int) of PhylogenyNode of this Phylogeny
935 public void reRoot( final int id ) {
936 reRoot( getNode( id ) );
940 * Places the root of this Phylogeny on Branch b. The new root is always
941 * placed on the middle of the branch b.
944 public void reRoot( final PhylogenyBranch b ) {
945 final PhylogenyNode n1 = b.getFirstNode();
946 final PhylogenyNode n2 = b.getSecondNode();
947 if ( n1.isExternal() ) {
950 else if ( n2.isExternal() ) {
953 else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) {
956 else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) {
959 else if ( ( n1.getParent() != null ) && n1.getParent().isRoot()
960 && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) {
964 throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." );
969 * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
970 * The new root is always placed on the middle of the branch.
972 * If the resulting reRooted Phylogeny is to be used any further, in most
973 * cases the following three methods have to be called on the resulting
976 * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
979 * (Last modified: 10/01/01)
982 * PhylogenyNode of this Phylogeny\
984 public void reRoot( final PhylogenyNode n ) {
988 public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
989 if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
996 else if ( n.getParent().isRoot() ) {
997 if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
998 final double d = n.getParent().getChildNode1().getDistanceToParent()
999 + n.getParent().getChildNode2().getDistanceToParent();
1000 PhylogenyNode other;
1001 if ( n.getChildNodeIndex() == 0 ) {
1002 other = n.getParent().getChildNode2();
1005 other = n.getParent().getChildNode1();
1007 n.setDistanceToParent( distance_n_to_parent );
1008 final double dm = d - distance_n_to_parent;
1010 other.setDistanceToParent( dm );
1013 other.setDistanceToParent( 0 );
1016 if ( n.getParent().getNumberOfDescendants() > 2 ) {
1017 final int index = n.getChildNodeIndex();
1018 final double dn = n.getDistanceToParent();
1019 final PhylogenyNode prev_root = getRoot();
1020 prev_root.getDescendants().remove( index );
1021 final PhylogenyNode new_root = new PhylogenyNode();
1022 new_root.setChildNode( 0, n );
1023 new_root.setChildNode( 1, prev_root );
1024 if ( n.getBranchDataDirectly() != null ) {
1025 prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
1027 setRoot( new_root );
1028 if ( distance_n_to_parent >= 0 ) {
1029 n.setDistanceToParent( distance_n_to_parent );
1030 final double d = dn - distance_n_to_parent;
1032 prev_root.setDistanceToParent( d );
1035 prev_root.setDistanceToParent( 0 );
1040 final double d = dn / 2.0;
1041 n.setDistanceToParent( d );
1042 prev_root.setDistanceToParent( d );
1048 PhylogenyNode a = n;
1049 PhylogenyNode b = null;
1050 PhylogenyNode c = null;
1051 final PhylogenyNode new_root = new PhylogenyNode();
1052 double distance1 = 0.0;
1053 double distance2 = 0.0;
1054 BranchData branch_data_1 = null;
1055 BranchData branch_data_2 = null;
1058 new_root.setChildNode( 0, a );
1059 new_root.setChildNode( 1, b );
1060 distance1 = c.getDistanceToParent();
1061 if ( c.getBranchDataDirectly() != null ) {
1062 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
1064 c.setDistanceToParent( b.getDistanceToParent() );
1065 if ( b.getBranchDataDirectly() != null ) {
1066 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
1068 if ( a.getBranchDataDirectly() != null ) {
1069 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
1071 // New root is always placed in the middle of the branch:
1072 if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
1073 b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
1076 if ( distance_n_to_parent >= 0.0 ) {
1077 final double diff = a.getDistanceToParent() - distance_n_to_parent;
1078 a.setDistanceToParent( distance_n_to_parent );
1079 b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
1082 final double d = a.getDistanceToParent() / 2.0;
1083 a.setDistanceToParent( d );
1084 b.setDistanceToParent( d );
1087 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1088 // moving to the old root, swapping references:
1089 while ( !c.isRoot() ) {
1093 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1095 distance2 = c.getDistanceToParent();
1096 branch_data_2 = c.getBranchDataDirectly();
1097 c.setDistanceToParent( distance1 );
1098 c.setBranchData( branch_data_1 );
1099 distance1 = distance2;
1100 branch_data_1 = branch_data_2;
1102 // removing the old root:
1103 if ( c.getNumberOfDescendants() == 2 ) {
1104 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
1105 node.setParent( b );
1106 if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
1107 && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
1108 node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
1111 node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
1112 + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
1114 if ( c.getBranchDataDirectly() != null ) {
1115 node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
1117 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
1118 if ( b.getChildNode( i ) == c ) {
1119 b.setChildNodeOnly( i, node );
1126 c.removeChildNode( b.getChildNodeIndex( c ) );
1128 setRoot( new_root );
1133 * Sets all Nodes of this Phylogeny to not-collapsed.
1135 * In most cases methods adjustNodeCount(false) and recalculateAndReset()
1136 * need to be called after this method has been called.
1138 public void setAllNodesToNotCollapse() {
1142 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1143 final PhylogenyNode node = iter.next();
1144 node.setCollapse( false );
1148 private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1149 _allow_multiple_parents = allow_multiple_parents;
1152 public void setConfidence( final Confidence confidence ) {
1153 _confidence = confidence;
1156 public void setDescription( final String description ) {
1157 _description = description;
1160 public void setDistanceUnit( final String _distance_unit ) {
1161 this._distance_unit = _distance_unit;
1164 public void setIdentifier( final Identifier identifier ) {
1165 _identifier = identifier;
1168 void setIdHash( final HashMap<Integer, PhylogenyNode> idhash ) {
1173 * Sets the indicators of all Nodes of this Phylogeny to 0.
1175 public void setIndicatorsToZero() {
1179 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1180 iter.next().setIndicator( ( byte ) 0 );
1182 } // setIndicatorsToZero()
1185 * Sets the name of this Phylogeny to s.
1187 public void setName( final String s ) {
1191 public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1192 _relevant_sequence_relation_types = types;
1195 public void setRerootable( final boolean rerootable ) {
1196 _rerootable = rerootable;
1199 public void setRoot( final PhylogenyNode n ) {
1201 } // setRoot( PhylogenyNode )
1204 * Sets whether this Phylogeny is rooted or not.
1206 public void setRooted( final boolean b ) {
1208 } // setRooted( boolean )
1210 public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1211 _sequenceRelationQueries = sequencesByName;
1214 public void setType( final String type ) {
1218 public String toNewHampshire() {
1219 return toNewHampshire( false, NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1222 public String toNewHampshire( final boolean simple_nh,
1223 final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) {
1225 return new PhylogenyWriter().toNewHampshire( this, simple_nh, true, nh_conversion_support_style )
1228 catch ( final IOException e ) {
1229 throw new Error( "this should not have happend: " + e.getMessage() );
1233 public String toNewHampshireX() {
1235 return new PhylogenyWriter().toNewHampshireX( this ).toString();
1237 catch ( final IOException e ) {
1238 throw new Error( "this should not have happend: " + e.getMessage() );
1242 public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
1244 return new PhylogenyWriter().toNexus( this, svs ).toString();
1246 catch ( final IOException e ) {
1247 throw new Error( "this should not have happend: " + e.getMessage() );
1251 public String toNexus() {
1252 return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1255 public String toPhyloXML( final int phyloxml_level ) {
1257 return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1259 catch ( final IOException e ) {
1260 throw new Error( "this should not have happend: " + e.getMessage() );
1264 // ---------------------------------------------------------
1265 // Writing of Phylogeny to Strings
1266 // ---------------------------------------------------------
1268 * Converts this Phylogeny to a New Hampshire X (String) representation.
1270 * @return New Hampshire X (String) representation of this
1271 * @see #toNewHampshireX()
1274 public String toString() {
1275 return toNewHampshireX();
1279 * Removes the root PhylogenyNode this Phylogeny.
1281 public void unRoot() throws RuntimeException {
1283 throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1288 setIndicatorsToZero();
1289 if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {