X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogeny.java;h=4aefb5cb82d5e8c986cd7010d46bb0bcef5c2ef1;hb=949eaaae036e91f8a98bb8d37e519f98384b337e;hp=9eb8d189308140f4b54257a723e5c328385bf6c4;hpb=cc75486aa58b98ab6fa53d8de4cb9b984a86bf83;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/Phylogeny.java b/forester/java/src/org/forester/phylogeny/Phylogeny.java index 9eb8d18..4aefb5c 100644 --- a/forester/java/src/org/forester/phylogeny/Phylogeny.java +++ b/forester/java/src/org/forester/phylogeny/Phylogeny.java @@ -23,7 +23,7 @@ // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA // // Contact: phylosoft @ gmail . com -// WWW: www.phylosoft.org/forester +// WWW: https://sites.google.com/site/cmzmasek/home/software/forester package org.forester.phylogeny; @@ -38,6 +38,7 @@ import java.util.Map; import java.util.NoSuchElementException; import java.util.Vector; +import org.forester.io.parsers.nhx.NHXParser; import org.forester.io.writers.PhylogenyWriter; import org.forester.phylogeny.PhylogenyNode.NH_CONVERSION_SUPPORT_VALUE_STYLE; import org.forester.phylogeny.data.BranchData; @@ -47,13 +48,14 @@ import org.forester.phylogeny.data.PhylogenyDataUtil; import org.forester.phylogeny.data.Sequence; import org.forester.phylogeny.data.SequenceRelation; import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE; +import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory; +import org.forester.phylogeny.factories.PhylogenyFactory; import org.forester.phylogeny.iterators.ExternalForwardIterator; import org.forester.phylogeny.iterators.LevelOrderTreeIterator; import org.forester.phylogeny.iterators.PhylogenyNodeIterator; import org.forester.phylogeny.iterators.PostorderTreeIterator; import org.forester.phylogeny.iterators.PreorderTreeIterator; import org.forester.util.FailedConditionCheckException; -import org.forester.util.ForesterUtil; public class Phylogeny { @@ -68,7 +70,7 @@ public class Phylogeny { private Confidence _confidence; private Identifier _identifier; private boolean _rerootable; - private HashMap _id_to_node_map; + private HashMap _id_to_node_map; private List _external_nodes_set; private Collection _sequenceRelationQueries; private Collection _relevant_sequence_relation_types; @@ -83,7 +85,7 @@ public class Phylogeny { /** * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent * and sets the parent of this to parent. - * + * * @param n * the PhylogenyNode to add */ @@ -123,24 +125,24 @@ public class Phylogeny { /** * This calculates the height of the subtree emanating at n for rooted, * tree-shaped phylogenies - * + * * @param n * the root-node of a subtree * @return the height of the subtree emanating at n */ - public double calculateSubtreeHeight( final PhylogenyNode n ) { - if ( n.isExternal() || n.isCollapse() ) { - return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) { + if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) { + return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0; } else { double max = -Double.MAX_VALUE; for( int i = 0; i < n.getNumberOfDescendants(); ++i ) { - final double l = calculateSubtreeHeight( n.getChildNode( i ) ); + final double l = calculateSubtreeHeight( n.getChildNode( i ), take_collapse_into_account ); if ( l > max ) { max = l; } } - return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0); } } @@ -219,9 +221,9 @@ public class Phylogeny { /** * Need to call clearHashIdToNodeMap() afterwards (not done automatically * to allow client multiple deletions in linear time). - * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this + * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this * if tree is to be displayed. - * + * * @param remove_us the parent node of the subtree to be deleted */ public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) { @@ -258,12 +260,12 @@ public class Phylogeny { final int pi = p.getChildNodeIndex(); if ( removed_node.isFirstChildNode() ) { p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) ); + .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 1 ) ); } else { p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) ); + .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 0 ) ); } } @@ -304,11 +306,16 @@ public class Phylogeny { return _distance_unit; } + public final static Phylogeny createInstanceFromNhxString( final String nhx ) throws IOException { + final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance(); + return factory.create( nhx, new NHXParser() )[ 0 ]; + } + /** - * + * * Warning. The order of the returned nodes is random * -- and hence cannot be relied on. - * + * * @return Unordered set of PhylogenyNode */ public List getExternalNodes() { @@ -324,28 +331,7 @@ public class Phylogeny { return _external_nodes_set; } - /** - * Returns the number of duplications of this Phylogeny (int). A return - * value of -1 indicates that the number of duplications is unknown. - */ - // public int getNumberOfDuplications() { - // return _number_of_duplications; - // } // getNumberOfDuplications() - /** - * Sets the number of duplications of this Phylogeny (int). A value of -1 - * indicates that the number of duplications is unknown. - * - * @param clean_nh - * set to true for clean NH format - */ - // public void setNumberOfDuplications( int i ) { - // if ( i < 0 ) { - // _number_of_duplications = -1; - // } - // else { - // _number_of_duplications = i; - // } - // } // setNumberOfDuplications( int ) + /** * Returns the first external PhylogenyNode. */ @@ -362,17 +348,15 @@ public class Phylogeny { /** * This calculates the height for rooted, tree-shaped phylogenies. The - * height is the longest distance from the root to an external node. Please - * note. Child nodes of collapsed nodes are ignored -- which is useful for - * display purposes but might be misleading for other applications. - * + * height is the longest distance from the root to an external node. + * * @return the height for rooted, tree-shaped phylogenies */ - public double getHeight() { + public double calculateHeight(final boolean take_collapse_into_account) { if ( isEmpty() ) { return 0.0; } - return calculateSubtreeHeight( getRoot() ); + return calculateSubtreeHeight( getRoot(), take_collapse_into_account ); } public Identifier getIdentifier() { @@ -390,7 +374,7 @@ public class Phylogeny { * Finds the PhylogenyNode of this Phylogeny which has a matching ID number. * @return PhylogenyNode with matching ID, null if not found */ - public PhylogenyNode getNode( final int id ) throws NoSuchElementException { + public PhylogenyNode getNode( final long id ) throws NoSuchElementException { if ( isEmpty() ) { throw new NoSuchElementException( "attempt to get node in an empty phylogeny" ); } @@ -403,7 +387,7 @@ public class Phylogeny { /** * Returns a PhylogenyNode of this Phylogeny which has a matching name. * Throws an Exception if seqname is not present in this or not unique. - * + * * @param name * name (String) of PhylogenyNode to find * @return PhylogenyNode with matchin name @@ -424,7 +408,7 @@ public class Phylogeny { /** * This is time-inefficient since it runs a iterator each time it is called. - * + * */ public int getNodeCount() { if ( isEmpty() ) { @@ -440,7 +424,7 @@ public class Phylogeny { /** * Returns a List with references to all Nodes of this Phylogeny which have * a matching name. - * + * * @param name * name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -475,6 +459,34 @@ public class Phylogeny { return nodes; } + public List getNodesViaSequenceSymbol( final String seq_name ) { + if ( isEmpty() ) { + return null; + } + final List nodes = new ArrayList(); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) { + nodes.add( n ); + } + } + return nodes; + } + + public List getNodesViaGeneName( final String seq_name ) { + if ( isEmpty() ) { + return null; + } + final List nodes = new ArrayList(); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) { + nodes.add( n ); + } + } + return nodes; + } + public List getNodesViaTaxonomyCode( final String taxonomy_code ) { if ( isEmpty() ) { return null; @@ -493,7 +505,7 @@ public class Phylogeny { /** * Returns a Vector with references to all Nodes of this Phylogeny which * have a matching species name. - * + * * @param specname * species name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -593,7 +605,7 @@ public class Phylogeny { *

* (Last modified: 11/22/00) Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param n * external PhylogenyNode whose orthologs are to be returned * @return Vector of references to all orthologous Nodes of PhylogenyNode n @@ -622,11 +634,11 @@ public class Phylogeny { if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) { if ( node.getChildNode1() == prev ) { v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2() - .getAllExternalDescendants() ) ); + .getAllExternalDescendants() ) ); } else { v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1() - .getAllExternalDescendants() ) ); + .getAllExternalDescendants() ) ); } } } @@ -675,7 +687,7 @@ public class Phylogeny { /** * Returns whether this is a completely binary tree (i.e. all internal nodes * are bifurcations). - * + * */ public boolean isCompletelyBinary() { if ( isEmpty() ) { @@ -692,7 +704,7 @@ public class Phylogeny { /** * Checks whether a Phylogeny object is deleted (or empty). - * + * * @return true if the tree is deleted (or empty), false otherwise */ public boolean isEmpty() { @@ -734,14 +746,14 @@ public class Phylogeny { * Resets the ID numbers of the nodes of this Phylogeny in level order, * starting with start_label (for the root).
* WARNING. After this method has been called, node IDs are no longer - * unique. + * unique. */ public void levelOrderReID() { if ( isEmpty() ) { return; } _id_to_node_map = null; - int max = 0; + long max = 0; for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) { final PhylogenyNode node = it.next(); if ( node.isRoot() ) { @@ -774,7 +786,7 @@ public class Phylogeny { * (Re)counts the number of children for each PhylogenyNode of this * Phylogeny. As an example, this method needs to be called after a * Phylogeny has been reRooted and it is to be displayed. - * + * * @param consider_collapsed_nodes * set to true to take into account collapsed nodes (collapsed * nodes have 1 child). @@ -807,44 +819,15 @@ public class Phylogeny { *

*

  • recalculateNumberOfExternalDescendants(boolean) *
  • recalculateAndReset() - * + * * @param id * ID (int) of PhylogenyNode of this Phylogeny */ - public void reRoot( final int id ) { + public void reRoot( final long id ) { reRoot( getNode( id ) ); } /** - * Places the root of this Phylogeny on Branch b. The new root is always - * placed on the middle of the branch b. - * - */ - public void reRoot( final PhylogenyBranch b ) { - final PhylogenyNode n1 = b.getFirstNode(); - final PhylogenyNode n2 = b.getSecondNode(); - if ( n1.isExternal() ) { - reRoot( n1 ); - } - else if ( n2.isExternal() ) { - reRoot( n2 ); - } - else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) { - reRoot( n2 ); - } - else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) { - reRoot( n1 ); - } - else if ( ( n1.getParent() != null ) && n1.getParent().isRoot() - && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) { - reRoot( n1 ); - } - else { - throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." ); - } - } - - /** * Places the root of this Phylogeny on the parent branch PhylogenyNode n. * The new root is always placed on the middle of the branch. *

    @@ -856,7 +839,7 @@ public class Phylogeny { * *

    * (Last modified: 10/01/01) - * + * * @param n * PhylogenyNode of this Phylogeny\ */ @@ -988,7 +971,7 @@ public class Phylogeny { } else { node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 ) - + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) ); + + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) ); } if ( c.getBranchDataDirectly() != null ) { node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() ); @@ -1040,7 +1023,7 @@ public class Phylogeny { _identifier = identifier; } - public void setIdToNodeMap( final HashMap idhash ) { + public void setIdToNodeMap( final HashMap idhash ) { _id_to_node_map = idhash; } @@ -1073,14 +1056,14 @@ public class Phylogeny { public void setRoot( final PhylogenyNode n ) { _root = n; - } // setRoot( PhylogenyNode ) + } /** * Sets whether this Phylogeny is rooted or not. */ public void setRooted( final boolean b ) { _rooted = b; - } // setRooted( boolean ) + } public void setSequenceRelationQueries( final Collection sequencesByName ) { _sequenceRelationQueries = sequencesByName; @@ -1091,14 +1074,12 @@ public class Phylogeny { } public String toNewHampshire() { - return toNewHampshire( false, NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); + return toNewHampshire( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); } - public String toNewHampshire( final boolean simple_nh, - final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) { + public String toNewHampshire( final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) { try { - return new PhylogenyWriter().toNewHampshire( this, simple_nh, true, nh_conversion_support_style ) - .toString(); + return new PhylogenyWriter().toNewHampshire( this, true, nh_conversion_support_style ).toString(); } catch ( final IOException e ) { throw new Error( "this should not have happend: " + e.getMessage() ); @@ -1141,7 +1122,7 @@ public class Phylogeny { // --------------------------------------------------------- /** * Converts this Phylogeny to a New Hampshire X (String) representation. - * + * * @return New Hampshire X (String) representation of this * @see #toNewHampshireX() */ @@ -1168,14 +1149,14 @@ public class Phylogeny { return; } // unRoot() - private HashMap getIdToNodeMap() { + private HashMap getIdToNodeMap() { return _id_to_node_map; } /** * Return Node by TaxonomyId Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param taxonomyID * search taxonomy identifier * @param nodes @@ -1195,7 +1176,7 @@ public class Phylogeny { /** * List all species contains in all leaf under a node Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param node * PhylogenyNode whose sub node species are returned * @return species contains in all leaf under the param node @@ -1218,7 +1199,7 @@ public class Phylogeny { * Create a map [], the list contains the * species contains in all leaf under phylogeny node Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param node * the tree root node * @param map @@ -1241,7 +1222,7 @@ public class Phylogeny { /** * Util method to check if all element of a list is contains in the * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr - * + * * @param list * list to be check * @param rangeList @@ -1273,7 +1254,7 @@ public class Phylogeny { if ( isEmpty() ) { return; } - setIdToNodeMap( new HashMap() ); + setIdToNodeMap( new HashMap() ); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode node = iter.next(); getIdToNodeMap().put( node.getId(), node );