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: https://sites.google.com/site/cmzmasek/home/software/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.parsers.nhx.NHXParser;
42 import org.forester.io.writers.PhylogenyWriter;
43 import org.forester.phylogeny.PhylogenyNode.NH_CONVERSION_SUPPORT_VALUE_STYLE;
44 import org.forester.phylogeny.data.BranchData;
45 import org.forester.phylogeny.data.Confidence;
46 import org.forester.phylogeny.data.Identifier;
47 import org.forester.phylogeny.data.PhylogenyDataUtil;
48 import org.forester.phylogeny.data.Sequence;
49 import org.forester.phylogeny.data.SequenceRelation;
50 import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE;
51 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
52 import org.forester.phylogeny.factories.PhylogenyFactory;
53 import org.forester.phylogeny.iterators.ExternalForwardIterator;
54 import org.forester.phylogeny.iterators.LevelOrderTreeIterator;
55 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
56 import org.forester.phylogeny.iterators.PostorderTreeIterator;
57 import org.forester.phylogeny.iterators.PreorderTreeIterator;
58 import org.forester.util.FailedConditionCheckException;
59 import org.forester.util.ForesterUtil;
61 public class Phylogeny {
63 public final static boolean ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
64 private PhylogenyNode _root;
65 private boolean _rooted;
66 private boolean _allow_multiple_parents;
69 private String _description;
70 private String _distance_unit;
71 private Confidence _confidence;
72 private Identifier _identifier;
73 private boolean _rerootable;
74 private HashMap<Long, PhylogenyNode> _id_to_node_map;
75 private List<PhylogenyNode> _external_nodes_set;
76 private Collection<Sequence> _sequenceRelationQueries;
77 private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
80 * Default Phylogeny constructor. Constructs an empty Phylogeny.
87 * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
88 * and sets the parent of this to parent.
91 * the PhylogenyNode to add
93 public void addAsChild( final PhylogenyNode parent ) {
95 throw new IllegalArgumentException( "Attempt to add an empty tree." );
98 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
100 parent.addAsChild( getRoot() );
101 externalNodesHaveChanged();
104 public void addAsSibling( final PhylogenyNode sibling ) {
106 throw new IllegalArgumentException( "Attempt to add an empty tree." );
109 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
111 final int sibling_index = sibling.getChildNodeIndex();
112 final PhylogenyNode new_node = new PhylogenyNode();
113 final PhylogenyNode sibling_parent = sibling.getParent();
114 new_node.setChild1( sibling );
115 new_node.setChild2( getRoot() );
116 new_node.setParent( sibling_parent );
117 sibling.setParent( new_node );
118 sibling_parent.setChildNode( sibling_index, new_node );
119 final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT
120 : sibling.getDistanceToParent() / 2;
121 new_node.setDistanceToParent( new_dist );
122 sibling.setDistanceToParent( new_dist );
123 externalNodesHaveChanged();
127 * This calculates the height of the subtree emanating at n for rooted,
128 * tree-shaped phylogenies
131 * the root-node of a subtree
132 * @return the height of the subtree emanating at n
134 public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) {
135 if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) {
136 return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0;
139 double max = -Double.MAX_VALUE;
140 for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
141 final double l = calculateSubtreeHeight( n.getChildNode( i ), take_collapse_into_account );
146 return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0);
150 public void clearHashIdToNodeMap() {
151 setIdToNodeMap( null );
155 * Returns a deep copy of this Phylogeny.
157 * (The resulting Phylogeny has its references in the external nodes
158 * corrected, if they are lacking/obsolete in this.)
160 public Phylogeny copy() {
161 return copy( _root );
165 * Returns a deep copy of this Phylogeny.
167 * (The resulting Phylogeny has its references in the external nodes
168 * corrected, if they are lacking/obsolete in this.)
170 public Phylogeny copy( final PhylogenyNode source ) {
171 final Phylogeny tree = new Phylogeny();
176 tree._rooted = _rooted;
177 tree._name = new String( _name );
178 tree._description = new String( _description );
179 tree._type = new String( _type );
180 tree._rerootable = _rerootable;
181 tree._distance_unit = new String( _distance_unit );
182 if ( _confidence != null ) {
183 tree._confidence = ( Confidence ) _confidence.copy();
185 if ( _identifier != null ) {
186 tree._identifier = ( Identifier ) _identifier.copy();
188 tree.setAllowMultipleParents( isAllowMultipleParents() );
189 tree._root = PhylogenyMethods.copySubTree( source );
194 * Returns a shallow copy of this Phylogeny.
196 * (The resulting Phylogeny has its references in the external nodes
197 * corrected, if they are lacking/obsolete in this.)
199 public Phylogeny copyShallow() {
200 return copyShallow( _root );
203 public Phylogeny copyShallow( final PhylogenyNode source ) {
204 final Phylogeny tree = new Phylogeny();
209 tree._rooted = _rooted;
211 tree._description = _description;
213 tree._rerootable = _rerootable;
214 tree._distance_unit = _distance_unit;
215 tree._confidence = _confidence;
216 tree._identifier = _identifier;
217 tree.setAllowMultipleParents( isAllowMultipleParents() );
218 tree._root = PhylogenyMethods.copySubTreeShallow( source );
223 * Need to call clearHashIdToNodeMap() afterwards (not done automatically
224 * to allow client multiple deletions in linear time).
225 * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this
226 * if tree is to be displayed.
228 * @param remove_us the parent node of the subtree to be deleted
230 public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
231 if ( isEmpty() || ( remove_us.isRoot() && ( getNumberOfExternalNodes() != 1 ) ) ) {
234 if ( remove_us.isRoot() && ( getNumberOfExternalNodes() == 1 ) ) {
237 else if ( !collapse_resulting_node_with_one_desc ) {
238 remove_us.getParent().removeChildNode( remove_us );
241 final PhylogenyNode removed_node = remove_us;
242 final PhylogenyNode p = remove_us.getParent();
244 if ( p.getNumberOfDescendants() == 2 ) {
245 if ( removed_node.isFirstChildNode() ) {
246 setRoot( getRoot().getChildNode( 1 ) );
247 getRoot().setParent( null );
250 setRoot( getRoot().getChildNode( 0 ) );
251 getRoot().setParent( null );
255 p.removeChildNode( removed_node.getChildNodeIndex() );
259 final PhylogenyNode pp = removed_node.getParent().getParent();
260 if ( p.getNumberOfDescendants() == 2 ) {
261 final int pi = p.getChildNodeIndex();
262 if ( removed_node.isFirstChildNode() ) {
263 p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
264 .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) );
265 pp.setChildNode( pi, p.getChildNode( 1 ) );
268 p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
269 .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
270 pp.setChildNode( pi, p.getChildNode( 0 ) );
274 p.removeChildNode( removed_node.getChildNodeIndex() );
278 remove_us.removeConnections();
279 externalNodesHaveChanged();
282 public void externalNodesHaveChanged() {
283 _external_nodes_set = null;
286 public String[] getAllExternalNodeNames() {
291 final String[] names = new String[ getNumberOfExternalNodes() ];
292 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
293 names[ i++ ] = new String( iter.next().getName() );
298 public Confidence getConfidence() {
302 public String getDescription() {
306 public String getDistanceUnit() {
307 return _distance_unit;
310 public final static Phylogeny createInstanceFromNhxString( final String nhx ) throws IOException {
311 final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
312 return factory.create( nhx, new NHXParser() )[ 0 ];
317 * Warning. The order of the returned nodes is random
318 * -- and hence cannot be relied on.
320 * @return Unordered set of PhylogenyNode
322 public List<PhylogenyNode> getExternalNodes() {
323 if ( _external_nodes_set == null ) {
324 _external_nodes_set = new ArrayList<PhylogenyNode>();
325 for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
326 final PhylogenyNode n = it.next();
327 if ( n.isExternal() ) {
328 _external_nodes_set.add( n );
332 return _external_nodes_set;
337 * Returns the first external PhylogenyNode.
339 public PhylogenyNode getFirstExternalNode() {
341 throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
343 PhylogenyNode node = getRoot();
344 while ( node.isInternal() ) {
345 node = node.getFirstChildNode();
351 * This calculates the height for rooted, tree-shaped phylogenies. The
352 * height is the longest distance from the root to an external node.
354 * @return the height for rooted, tree-shaped phylogenies
356 public double calculateHeight(final boolean take_collapse_into_account) {
360 return calculateSubtreeHeight( getRoot(), take_collapse_into_account );
363 public Identifier getIdentifier() {
368 * Returns the name of this Phylogeny.
370 public String getName() {
375 * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
376 * @return PhylogenyNode with matching ID, null if not found
378 public PhylogenyNode getNode( final long id ) throws NoSuchElementException {
380 throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
382 if ( ( getIdToNodeMap() == null ) || getIdToNodeMap().isEmpty() ) {
385 return getIdToNodeMap().get( id );
389 * Returns a PhylogenyNode of this Phylogeny which has a matching name.
390 * Throws an Exception if seqname is not present in this or not unique.
393 * name (String) of PhylogenyNode to find
394 * @return PhylogenyNode with matchin name
396 public PhylogenyNode getNode( final String name ) {
400 final List<PhylogenyNode> nodes = getNodes( name );
401 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
402 throw new IllegalArgumentException( "node named \"" + name + "\" not found" );
404 if ( nodes.size() > 1 ) {
405 throw new IllegalArgumentException( "node named \"" + name + "\" not unique" );
407 return nodes.get( 0 );
411 * This is time-inefficient since it runs a iterator each time it is called.
414 public int getNodeCount() {
419 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
426 * Returns a List with references to all Nodes of this Phylogeny which have
430 * name (String) of Nodes to find
431 * @return Vector of references to Nodes of this Phylogeny with matching
433 * @see #getNodesWithMatchingSpecies(String)
435 public List<PhylogenyNode> getNodes( final String name ) {
439 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
440 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
441 final PhylogenyNode n = iter.next();
442 if ( n.getName().equals( name ) ) {
449 public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
453 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
454 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
455 final PhylogenyNode n = iter.next();
456 if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
463 public List<PhylogenyNode> getNodesViaSequenceSymbol( final String seq_name ) {
467 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
468 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
469 final PhylogenyNode n = iter.next();
470 if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) {
477 public List<PhylogenyNode> getNodesViaGeneName( final String seq_name ) {
481 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
482 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
483 final PhylogenyNode n = iter.next();
484 if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) {
491 public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
495 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
496 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
497 final PhylogenyNode n = iter.next();
498 if ( n.getNodeData().isHasTaxonomy()
499 && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
507 * Returns a Vector with references to all Nodes of this Phylogeny which
508 * have a matching species name.
511 * species name (String) of Nodes to find
512 * @return Vector of references to Nodes of this Phylogeny with matching
514 * @see #getNodes(String)
516 public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
520 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
521 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
522 final PhylogenyNode n = iter.next();
523 if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
530 public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
534 final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
535 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
536 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
538 if ( nodes.size() > 1 ) {
539 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
541 return nodes.get( 0 );
544 public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
548 final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
549 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
550 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
552 if ( nodes.size() > 1 ) {
553 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
555 return nodes.get( 0 );
558 public int getNumberOfBranches() {
563 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
572 public int getNumberOfInternalNodes() {
577 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
578 if ( iter.next().isInternal() ) {
589 * Returns the sum of external Nodes of this Phylogeny (int).
591 public int getNumberOfExternalNodes() {
595 return getExternalNodes().size();
599 * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
600 * paralog are returned as List of node references.
602 * PRECONDITION: This tree must be binary and rooted, and speciation -
603 * duplication need to be assigned for each of its internal Nodes.
605 * Returns null if this Phylogeny is empty or if n is internal.
607 * (Last modified: 11/22/00) Olivier CHABROL :
608 * olivier.chabrol@univ-provence.fr
611 * external PhylogenyNode whose orthologs are to be returned
612 * @return Vector of references to all orthologous Nodes of PhylogenyNode n
613 * of this Phylogeny, null if this Phylogeny is empty or if n is
616 public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
617 PhylogenyNode node = n;
618 PhylogenyNode prev = null;
619 final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
620 final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
621 getTaxonomyMap( getRoot(), map );
622 if ( !node.isExternal() || isEmpty() ) {
625 final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
626 if ( !node.isExternal() || isEmpty() ) {
629 List<String> taxIdList = null;
630 final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
631 while ( !node.isRoot() ) {
633 node = node.getParent();
634 taxIdList = map.get( node );
635 if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
636 if ( node.getChildNode1() == prev ) {
637 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
638 .getAllExternalDescendants() ) );
641 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
642 .getAllExternalDescendants() ) );
649 public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
650 if ( _relevant_sequence_relation_types == null ) {
651 _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
653 return _relevant_sequence_relation_types;
657 * Returns the root PhylogenyNode of this Phylogeny.
659 public PhylogenyNode getRoot() {
663 public Collection<Sequence> getSequenceRelationQueries() {
664 return _sequenceRelationQueries;
667 public String getType() {
672 * Deletes this Phylogeny.
681 _id_to_node_map = null;
685 setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
689 * Returns whether this is a completely binary tree (i.e. all internal nodes
693 public boolean isCompletelyBinary() {
697 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
698 final PhylogenyNode node = iter.next();
699 if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
707 * Checks whether a Phylogeny object is deleted (or empty).
709 * @return true if the tree is deleted (or empty), false otherwise
711 public boolean isEmpty() {
712 return ( getRoot() == null );
715 public boolean isRerootable() {
720 * Returns true is this Phylogeny is rooted.
722 public boolean isRooted() {
726 public boolean isTree() {
730 public PhylogenyNodeIterator iteratorExternalForward() {
731 return new ExternalForwardIterator( this );
734 public PhylogenyNodeIterator iteratorLevelOrder() {
735 return new LevelOrderTreeIterator( this );
738 public PhylogenyNodeIterator iteratorPostorder() {
739 return new PostorderTreeIterator( this );
742 public PhylogenyNodeIterator iteratorPreorder() {
743 return new PreorderTreeIterator( this );
747 * Resets the ID numbers of the nodes of this Phylogeny in level order,
748 * starting with start_label (for the root). <br>
749 * WARNING. After this method has been called, node IDs are no longer
752 public void levelOrderReID() {
756 _id_to_node_map = null;
758 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
759 final PhylogenyNode node = it.next();
760 if ( node.isRoot() ) {
761 node.setId( PhylogenyNode.getNodeCount() );
764 node.setId( node.getParent().getId() + 1 );
765 if ( node.getId() > max ) {
770 PhylogenyNode.setNodeCount( max + 1 );
774 * Prints descriptions of all external Nodes of this Phylogeny to
777 public void printExtNodes() {
781 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
782 System.out.println( iter.next() + "\n" );
787 * (Re)counts the number of children for each PhylogenyNode of this
788 * Phylogeny. As an example, this method needs to be called after a
789 * Phylogeny has been reRooted and it is to be displayed.
791 * @param consider_collapsed_nodes
792 * set to true to take into account collapsed nodes (collapsed
793 * nodes have 1 child).
795 public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
799 for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
800 final PhylogenyNode node = iter.next();
801 if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
802 node.setSumExtNodes( 1 );
806 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
807 sum += node.getChildNode( i ).getNumberOfExternalNodes();
809 node.setSumExtNodes( sum );
815 * Places the root of this Phylogeny on the parent branch of the
816 * PhylogenyNode with a corresponding ID. The new root is always placed on
817 * the middle of the branch. If the resulting reRooted Phylogeny is to be
818 * used any further, in most cases the following methods have to be called
819 * on the resulting Phylogeny:
821 * <li>recalculateNumberOfExternalDescendants(boolean)
822 * <li>recalculateAndReset()
825 * ID (int) of PhylogenyNode of this Phylogeny
827 public void reRoot( final long id ) {
828 reRoot( getNode( id ) );
832 * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
833 * The new root is always placed on the middle of the branch.
835 * If the resulting reRooted Phylogeny is to be used any further, in most
836 * cases the following three methods have to be called on the resulting
839 * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
842 * (Last modified: 10/01/01)
845 * PhylogenyNode of this Phylogeny\
847 public void reRoot( final PhylogenyNode n ) {
851 public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
852 if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
859 else if ( n.getParent().isRoot() ) {
860 if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
861 final double d = n.getParent().getChildNode1().getDistanceToParent()
862 + n.getParent().getChildNode2().getDistanceToParent();
864 if ( n.getChildNodeIndex() == 0 ) {
865 other = n.getParent().getChildNode2();
868 other = n.getParent().getChildNode1();
870 n.setDistanceToParent( distance_n_to_parent );
871 final double dm = d - distance_n_to_parent;
873 other.setDistanceToParent( dm );
876 other.setDistanceToParent( 0 );
879 if ( n.getParent().getNumberOfDescendants() > 2 ) {
880 final int index = n.getChildNodeIndex();
881 final double dn = n.getDistanceToParent();
882 final PhylogenyNode prev_root = getRoot();
883 prev_root.getDescendants().remove( index );
884 final PhylogenyNode new_root = new PhylogenyNode();
885 new_root.setChildNode( 0, n );
886 new_root.setChildNode( 1, prev_root );
887 if ( n.getBranchDataDirectly() != null ) {
888 prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
891 if ( distance_n_to_parent >= 0 ) {
892 n.setDistanceToParent( distance_n_to_parent );
893 final double d = dn - distance_n_to_parent;
895 prev_root.setDistanceToParent( d );
898 prev_root.setDistanceToParent( 0 );
903 final double d = dn / 2.0;
904 n.setDistanceToParent( d );
905 prev_root.setDistanceToParent( d );
912 PhylogenyNode b = null;
913 PhylogenyNode c = null;
914 final PhylogenyNode new_root = new PhylogenyNode();
915 double distance1 = 0.0;
916 double distance2 = 0.0;
917 BranchData branch_data_1 = null;
918 BranchData branch_data_2 = null;
921 new_root.setChildNode( 0, a );
922 new_root.setChildNode( 1, b );
923 distance1 = c.getDistanceToParent();
924 if ( c.getBranchDataDirectly() != null ) {
925 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
927 c.setDistanceToParent( b.getDistanceToParent() );
928 if ( b.getBranchDataDirectly() != null ) {
929 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
931 if ( a.getBranchDataDirectly() != null ) {
932 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
934 // New root is always placed in the middle of the branch:
935 if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
936 b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
939 if ( distance_n_to_parent >= 0.0 ) {
940 final double diff = a.getDistanceToParent() - distance_n_to_parent;
941 a.setDistanceToParent( distance_n_to_parent );
942 b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
945 final double d = a.getDistanceToParent() / 2.0;
946 a.setDistanceToParent( d );
947 b.setDistanceToParent( d );
950 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
951 // moving to the old root, swapping references:
952 while ( !c.isRoot() ) {
956 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
958 distance2 = c.getDistanceToParent();
959 branch_data_2 = c.getBranchDataDirectly();
960 c.setDistanceToParent( distance1 );
961 c.setBranchData( branch_data_1 );
962 distance1 = distance2;
963 branch_data_1 = branch_data_2;
965 // removing the old root:
966 if ( c.getNumberOfDescendants() == 2 ) {
967 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
969 if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
970 && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
971 node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
974 node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
975 + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
977 if ( c.getBranchDataDirectly() != null ) {
978 node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
980 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
981 if ( b.getChildNode( i ) == c ) {
982 b.setChildNodeOnly( i, node );
989 c.removeChildNode( b.getChildNodeIndex( c ) );
996 * Sets all Nodes of this Phylogeny to not-collapsed.
998 * In most cases methods adjustNodeCount(false) and recalculateAndReset()
999 * need to be called after this method has been called.
1001 public void setAllNodesToNotCollapse() {
1005 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1006 final PhylogenyNode node = iter.next();
1007 node.setCollapse( false );
1011 public void setConfidence( final Confidence confidence ) {
1012 _confidence = confidence;
1015 public void setDescription( final String description ) {
1016 _description = description;
1019 public void setDistanceUnit( final String _distance_unit ) {
1020 this._distance_unit = _distance_unit;
1023 public void setIdentifier( final Identifier identifier ) {
1024 _identifier = identifier;
1027 public void setIdToNodeMap( final HashMap<Long, PhylogenyNode> idhash ) {
1028 _id_to_node_map = idhash;
1032 * Sets the indicators of all Nodes of this Phylogeny to 0.
1034 public void setIndicatorsToZero() {
1038 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1039 iter.next().setIndicator( ( byte ) 0 );
1041 } // setIndicatorsToZero()
1044 * Sets the name of this Phylogeny to s.
1046 public void setName( final String s ) {
1050 public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1051 _relevant_sequence_relation_types = types;
1054 public void setRerootable( final boolean rerootable ) {
1055 _rerootable = rerootable;
1058 public void setRoot( final PhylogenyNode n ) {
1063 * Sets whether this Phylogeny is rooted or not.
1065 public void setRooted( final boolean b ) {
1069 public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1070 _sequenceRelationQueries = sequencesByName;
1073 public void setType( final String type ) {
1077 public String toNewHampshire() {
1078 return toNewHampshire( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1081 public String toNewHampshire( final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) {
1083 return new PhylogenyWriter().toNewHampshire( this, true, nh_conversion_support_style ).toString();
1085 catch ( final IOException e ) {
1086 throw new Error( "this should not have happend: " + e.getMessage() );
1090 public String toNewHampshireX() {
1092 return new PhylogenyWriter().toNewHampshireX( this ).toString();
1094 catch ( final IOException e ) {
1095 throw new Error( "this should not have happend: " + e.getMessage() );
1099 public String toNexus() {
1100 return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1103 public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
1105 return new PhylogenyWriter().toNexus( this, svs ).toString();
1107 catch ( final IOException e ) {
1108 throw new Error( "this should not have happend: " + e.getMessage() );
1112 public String toPhyloXML( final int phyloxml_level ) {
1114 return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1116 catch ( final IOException e ) {
1117 throw new Error( "this should not have happend: " + e.getMessage() );
1121 // ---------------------------------------------------------
1122 // Writing of Phylogeny to Strings
1123 // ---------------------------------------------------------
1125 * Converts this Phylogeny to a New Hampshire X (String) representation.
1127 * @return New Hampshire X (String) representation of this
1128 * @see #toNewHampshireX()
1131 public String toString() {
1132 return toNewHampshireX();
1136 * Removes the root PhylogenyNode this Phylogeny.
1138 public void unRoot() throws RuntimeException {
1140 throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1145 setIndicatorsToZero();
1146 if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {
1153 private HashMap<Long, PhylogenyNode> getIdToNodeMap() {
1154 return _id_to_node_map;
1158 * Return Node by TaxonomyId Olivier CHABROL :
1159 * olivier.chabrol@univ-provence.fr
1162 * search taxonomy identifier
1164 * sublist node to search
1165 * @return List node with the same taxonomy identifier
1167 private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
1168 final List<PhylogenyNode> retour = new ArrayList<PhylogenyNode>();
1169 for( final PhylogenyNode node : nodes ) {
1170 if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
1178 * List all species contains in all leaf under a node Olivier CHABROL :
1179 * olivier.chabrol@univ-provence.fr
1182 * PhylogenyNode whose sub node species are returned
1183 * @return species contains in all leaf under the param node
1185 private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
1186 final List<String> taxonomyList = new ArrayList<String>();
1187 final List<PhylogenyNode> childs = node.getAllExternalDescendants();
1188 String speciesId = null;
1189 for( final PhylogenyNode phylogenyNode : childs ) {
1190 // taxId = new Long(phylogenyNode.getTaxonomyID());
1191 speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
1192 if ( !taxonomyList.contains( speciesId ) ) {
1193 taxonomyList.add( speciesId );
1196 return taxonomyList;
1200 * Create a map [<PhylogenyNode, List<String>], the list contains the
1201 * species contains in all leaf under phylogeny node Olivier CHABROL :
1202 * olivier.chabrol@univ-provence.fr
1205 * the tree root node
1209 private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
1211 if ( node.isExternal() ) {
1214 map.put( node, getSubNodeTaxonomy( node ) );
1215 getTaxonomyMap( node.getChildNode1(), map );
1216 getTaxonomyMap( node.getChildNode2(), map );
1219 private boolean isAllowMultipleParents() {
1220 return _allow_multiple_parents;
1224 * Util method to check if all element of a list is contains in the
1225 * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
1230 * the range list to compare
1231 * @return <code>true</code> if all param list element are contains in param
1232 * rangeList, <code>false</code> otherwise.
1234 private boolean isContains( final List<String> list, final List<String> rangeList ) {
1235 if ( list.size() > rangeList.size() ) {
1239 for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
1240 l = iterator.next();
1241 if ( !rangeList.contains( l ) ) {
1249 * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
1250 * corresponding PhylogenyNode, in order to make method getNode( id ) run in
1251 * constant time. Important: The user is responsible for calling this method
1252 * (again) after this Phylogeny has been changed/created/renumbered.
1254 private void reHashIdToNodeMap() {
1258 setIdToNodeMap( new HashMap<Long, PhylogenyNode>() );
1259 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1260 final PhylogenyNode node = iter.next();
1261 getIdToNodeMap().put( node.getId(), node );
1265 private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1266 _allow_multiple_parents = allow_multiple_parents;