FORESTER 1.7

forester.tree
Class Tree

java.lang.Object
  |
  +--forester.tree.Tree
All Implemented Interfaces:
java.io.Serializable

public class Tree
extends java.lang.Object
implements java.io.Serializable

Version:
1.710 -- last modified: 05/26/01
Author:
Christian M. Zmasek
See Also:
Serialized Form

Field Summary
(package private) static int MAX_LENGTH
           
(package private) static long serialVersionUID
           
 
Constructor Summary
Tree()
          Default Tree constructor.
Tree(java.lang.String nh_string)
          Tree constructor which constructs a Tree from the nh_string.
 
Method Summary
(package private)  void addNodeAndConnect(java.lang.String s1, java.lang.String s2)
          Used for building Trees.
 void adjustNodeCount()
          (Re)counts the number of children for each Node of this Tree.
 void allowMoreThanBinaryNodesInNHoutput(boolean b)
          Sets whether to allow more than binary Nodes in New Hampshire (NH) output.
 boolean areBranchLenghtsBootstraps()
          Checks whether the branch length values actually are bootstrap values All external Nodes must have the same, >0, divisible by 10 branch length.
 double calculateRealHeight()
          Calculates the real height of this (rooted) Tree -- the longest distance from root to external node.
 void copyBranchLengthValuesFrom(Tree t)
          Modifies this Tree with the branch lenghts of Tree t.
 Tree copyTree()
          Returns a deep copy of this Tree.
 void delete()
          Deletes this Tree.
 void findExtremeLnL()
          Finds the highest of all log likelihood value associated with branches of this Tree.
 java.lang.String[] getAllExternalSeqNames()
          Returns the sequence names of all external Nodes of this Tree as array of Strings.
 Node getExtNode0()
          Returns the first external Node.
 double getHighestLnL()
          Returns the highest log likelihood value associated with branches of this Tree (double).
 Node getLastCommonAncestor(int id1, int id2)
          Finds the last common ancestor Node of two Nodes specified by their IDs id1 and id2.
 Node getLastCommonAncestor(java.lang.String seqname1, java.lang.String seqname2)
          Finds the last common ancestor Node of two Nodes specified by their sequence names seqname1 and seqname2.
 double getLowestLnL()
          Returns the lowest log likelihood value associated with branches of this Tree (double).
 java.lang.String getName()
          Returns the name of this Tree.
 Node getNode(int id)
          Finds the Node of this Tree which has a matching ID number.
 Node getNode(java.lang.String seqname)
          Returns a Node of this Tree which has a matching sequence name seqname.
 java.util.Vector getNodes(java.lang.String seqname)
          Returns a Vector with references to all Nodes of this Tree which have a matching sequence name.
 java.util.Vector getNodesWithMatchingSpecies(java.lang.String specname)
          Returns a Vector with references to all Nodes of this Tree which have a matching species name.
 int getNumberOfDuplications()
          Returns the number of duplications of this Tree (int).
 int getNumberOfExtNodes()
          Returns the sum of external Nodes of this Tree (int).
 java.util.Vector getOrthologs(Node n)
          Returns all orthologs of the external Node n of this Tree.
 java.util.Vector getPath(Node node1, Node node2, boolean ret_pseudo_nodes)
          Returns a Vector containing the Node IDs of all Nodes which are between two external Nodes (node2 and node1).
 double getRealHeight()
          Returns the real height of this Tree - the longest distance from root to external node.
 Node getRoot()
          Returns the root Node of this Tree.
 java.util.Vector getSiblings(Node n)
          Returns a Vector of references to all external siblings and nieces of a external Node n.
 java.util.Vector getStrictlySrelatedNodes(Node n)
          Returns all Nodes which are connected to external Node n of this Tree by a path containing only speciation events.
 void hashIDs()
          Hashes the ID number of each Node of this Tree to its corresonding Node, in order to make method getNode( id ) run in constant time.
 boolean isCompletelyBinary()
          Returns whether this is a completely binary tree (i.e.
 boolean isEmpty()
          Checks whether a Tree object is deleted (or empty).
 boolean isRooted()
          Returns true is this Tree is rooted.
 void levelOrderReID(int i)
          Resets the ID numbers of the Nodes of this Tree in level order, starting with i (for the root).
 void moveBranchLenghtsToBootstrap()
          Moves the values in the branch length field to the bootstrap field, for each Node of this Tree.
 int preorderReID(int i)
          Resets the ID numbers of the Nodes of this Tree in preorder, starting with i.
 void printAllNodes()
          Prints descriptions of all Nodes of this Tree to the console.
 void printExtNodes()
          Prints descriptions of all external Nodes of this Tree to the console.
 void recalculateAndReset()
          Recalculates and resets parameters of this Tree: highest and lowest lnL, real height, sum of ext Nodes.
 void removeExtNode(Node n)
          Removes external Node from this Tree.
 void reRoot(int id)
          Places the root of this Tree on the parent branch of the Node with a corresponding ID.
 void reRoot(int id, java.lang.String s)
          Places the root of this Tree on the parent branch of the Node with a corresponding ID.
 void reRoot(Node n)
          Places the root of this Tree on the parent branch Node n.
 void reRoot(Node n, java.lang.String s)
          Places the root of this Tree on the parent branch Node n.
 void setExtNodes(int i)
          Sets the sum of external Nodes of this Tree (int).
 void setIndicatorsToZero()
          Sets the indicators of all Nodes of this Tree to 0.
 void setName(java.lang.String s)
          Sets the name of this Tree to s.
 void setNumberOfDuplications(int i)
          Sets the number of duplications of this Tree (int).
 void setRealHeight(double d)
          Sets the real height of this Tree - the longest distance from root to external node.
(package private)  void setRoot(Node n)
           
 void setRooted(boolean b)
          Sets whether this Tree is rooted or not.
 Tree subTree(int id)
          Returns the subtree of this Tree which has the Node with ID id as its root Node.
 void swapChildren(int id)
          Swaps the the two childern of a Node with ID id of this Tree.
 void swapChildren(Node node)
          Swaps the the two childern of a Node node of this Tree.
 java.lang.String toNewHampshire(boolean clean_nh)
          Converts this Tree to a New Hampshire (String) representation.
 java.lang.String toNewHampshireX()
          Converts this Tree to a New Hampshire X (String) representation.
 java.lang.String toString()
          Converts this Tree to a New Hampshire X (String) representation.
 void unRoot()
          Removes the root Node this Tree.
 void unRootAndTrifurcate()
          Removes the root Node of this Tree and makes at least a trifurcation at its basal node.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

MAX_LENGTH

static final int MAX_LENGTH

serialVersionUID

static final long serialVersionUID
Constructor Detail

Tree

public Tree()
Default Tree constructor. Constructs empty Tree.

Tree

public Tree(java.lang.String nh_string)
     throws java.lang.Exception
Tree constructor which constructs a Tree from the nh_string. The tree is considered unrooted if the deepest node has more than two children, otherwise it is considered rooted.
Parameters:
nh_string - String in New Hampshire (NH) or New Hampshire X (NHX) format
Method Detail

isEmpty

public boolean isEmpty()
Checks whether a Tree object is deleted (or empty).
Returns:
true if the tree is deleted (or empty), false otherwise

delete

public void delete()
Deletes this Tree.

getOrthologs

public java.util.Vector getOrthologs(Node n)
Returns all orthologs of the external Node n of this Tree. Orthologs are returned as Vector of references to Nodes. This tree must be binary and rooted, and speciation vs. duplication needs to be assigned for each of its internal Nodes. Returns null if this Tree is empty or if n is internal. (Last modified: 11/22/00)
Parameters:
n - external Node whose orthologs are to be returned
Returns:
Vector of references to all orthologous Nodes of Node n of this Tree, null if this Tree is empty or if n is internal

getStrictlySrelatedNodes

public java.util.Vector getStrictlySrelatedNodes(Node n)
Returns all Nodes which are connected to external Node n of this Tree by a path containing only speciation events. Nodes are returned as Vector of references to Nodes. This tree must be binary and rooted, and speciation vs. duplication needs to be assigned for each of its internal Nodes. Returns null if this Tree is empty or if n is internal. (Last modified: 11/22/00)
Parameters:
n - external Node whose strictly speciation related Nodes are to be returned
Returns:
Vector of references to all strictly speciation related Nodes of Node n of this Tree, null if this Tree is empty or if n is internal

getAllExternalSeqNames

public java.lang.String[] getAllExternalSeqNames()
Returns the sequence names of all external Nodes of this Tree as array of Strings. (Last modified: 11/13/00)
Returns:
all external sequence names as String[]

removeExtNode

public void removeExtNode(Node n)
Removes external Node from this Tree. If this tree has only one node, a empty tree will be returned.
Parameters:
n - Node to remove

getNodes

public java.util.Vector getNodes(java.lang.String seqname)
                          throws java.lang.Exception
Returns a Vector with references to all Nodes of this Tree which have a matching sequence name.
Parameters:
seqname - Sequence name (String) of Nodes to find
Returns:
Vector of references to Nodes of this Tree with matching sequence names
See Also:
getNodesWithMatchingSpecies(String)

getNode

public Node getNode(java.lang.String seqname)
             throws java.lang.Exception
Returns a Node of this Tree which has a matching sequence name seqname. Throws an Exception if seqname is not present in this or not unique. (Last modifed: 12/03/00)
Parameters:
seqname - Sequence name (String) of Node to find
Returns:
Node with matchin sequence name

getNodesWithMatchingSpecies

public java.util.Vector getNodesWithMatchingSpecies(java.lang.String specname)
                                             throws java.lang.Exception
Returns a Vector with references to all Nodes of this Tree which have a matching species name.
Parameters:
specname - species name (String) of Nodes to find
Returns:
Vector of references to Nodes of this Tree with matching species names.
See Also:
getNodes(String)

getNode

public Node getNode(int id)
Finds the Node of this Tree which has a matching ID number. Takes O(n) time. After method hashIDs() has been called it runs in constant time. (Last modified: 11/20/00)
Parameters:
id - ID number (int) of the Node to find
Returns:
Node with matching ID, null if Node not found

swapChildren

public void swapChildren(int id)
Swaps the the two childern of a Node with ID id of this Tree.
Parameters:
id - ID (int) of Node

swapChildren

public void swapChildren(Node node)
Swaps the the two childern of a Node node of this Tree.
Parameters:
node - a Node of this Tree

subTree

public Tree subTree(int id)
             throws java.lang.Exception
Returns the subtree of this Tree which has the Node with ID id as its root Node.
Parameters:
id - ID (int) of Node

reRoot

public void reRoot(int id)
            throws java.lang.Exception
Places the root of this Tree on the parent branch of the Node with a corresponding ID. The new root is always placed on the middle of the branch. If the resulting reRooted Tree is to be used any further, in most cases the following three methods have to be called on the resulting Tree: adjustNodeCount() recalculateAndReset() setExtNodes( getRoot().getSumExtNodes() )
Parameters:
id - ID (int) of Node of this Tree

reRoot

public void reRoot(Node n)
            throws java.lang.Exception
Places the root of this Tree on the parent branch Node n. The new root is always placed on the middle of the branch. If the resulting reRooted Tree is to be used any further, in most cases the following three methods have to be called on the resulting Tree: adjustNodeCount() recalculateAndReset() setExtNodes( getRoot().getSumExtNodes() )
Parameters:
n - Node of this Tree

reRoot

public void reRoot(int id,
                   java.lang.String s)
            throws java.lang.Exception
Places the root of this Tree on the parent branch of the Node with a corresponding ID. Information for the new root Node is provided in a String using NHX tags. The new root is always placed on the middle of the branch. If the resulting reRooted Tree is to be used any further, in most cases the following three methods have to be called on the resulting Tree: adjustNodeCount() recalculateAndReset() setExtNodes( getRoot().getSumExtNodes() )
Parameters:
id - ID (int) of Node of this Tree
s - String describing new Node

reRoot

public void reRoot(Node n,
                   java.lang.String s)
            throws java.lang.Exception
Places the root of this Tree on the parent branch Node n. Information for the new root Node is provided in a String using NHX tags. The new root is always placed on the middle of the branch. If the resulting reRooted Tree is to be used any further, in most cases the following three methods have to be called on the resulting Tree: adjustNodeCount() recalculateAndReset() setExtNodes( getRoot().getSumExtNodes() )
last modified: 05/22/01
Parameters:
n - Node of this Tree
s - String describing new Node

copyBranchLengthValuesFrom

public void copyBranchLengthValuesFrom(Tree t)
                                throws java.lang.Exception
Modifies this Tree with the branch lenghts of Tree t. Important (but obvious): The topology of both trees needs to be the same. (The method is not robust in this point, and will produce wrong results if the internal topology differs.) Furthermore, the combination of sequence name, species, and EC number needs to be unique for each external node.
Last modified: 05/22/01
Parameters:
t - the Tree to copy the branch lenghts from

recalculateAndReset

public void recalculateAndReset()
Recalculates and resets parameters of this Tree: highest and lowest lnL, real height, sum of ext Nodes. To be used after Tree has been modified. (Last modified: 11/18/00)

copyTree

public Tree copyTree()
Returns a deep copy of this Tree. (Last modified: 11/18/00)

unRootAndTrifurcate

public void unRootAndTrifurcate()
Removes the root Node of this Tree and makes at least a trifurcation at its basal node.

unRoot

public void unRoot()
Removes the root Node this Tree.

getRoot

public Node getRoot()
Returns the root Node of this Tree.

setRoot

void setRoot(Node n)

isRooted

public boolean isRooted()
Returns true is this Tree is rooted.

setRooted

public void setRooted(boolean b)
Sets whether this Tree is rooted or not.

getHighestLnL

public double getHighestLnL()
Returns the highest log likelihood value associated with branches of this Tree (double).
See Also:
findExtremeLnL()

getLowestLnL

public double getLowestLnL()
Returns the lowest log likelihood value associated with branches of this Tree (double).
See Also:
findExtremeLnL()

getRealHeight

public double getRealHeight()
Returns the real height of this Tree - the longest distance from root to external node. Is either calculated with "calculateRealHeight()" or manualy set with "setRealHeight(double)".
Returns:
the real height of this Tree - as calculated with "calculateRealHeight()" or set with "setRealHeight(double)"
See Also:
calculateRealHeight(), setRealHeight(double)

setRealHeight

public void setRealHeight(double d)
Sets the real height of this Tree - the longest distance from root to external node. Could either be calculated with "calculateRealHeight()" or manualy set with this method.
Parameters:
the - real height of this Tree
See Also:
calculateRealHeight()

getNumberOfDuplications

public int getNumberOfDuplications()
Returns the number of duplications of this Tree (int). A return value of -1 indicates that the number of duplications is unknown.

setNumberOfDuplications

public void setNumberOfDuplications(int i)
Sets the number of duplications of this Tree (int). A value of -1 indicates that the number of duplications is unknown.
Parameters:
clean_nh - set to true for clean NH format

getExtNode0

public Node getExtNode0()
Returns the first external Node.

getNumberOfExtNodes

public int getNumberOfExtNodes()
Returns the sum of external Nodes of this Tree (int).

setExtNodes

public void setExtNodes(int i)
Sets the sum of external Nodes of this Tree (int).

allowMoreThanBinaryNodesInNHoutput

public void allowMoreThanBinaryNodesInNHoutput(boolean b)
Sets whether to allow more than binary Nodes in New Hampshire (NH) output. The basal node can always appear trifurcated in the NH output.

getName

public java.lang.String getName()
Returns the name of this Tree.

setName

public void setName(java.lang.String s)
Sets the name of this Tree to s.

printExtNodes

public void printExtNodes()
Prints descriptions of all external Nodes of this Tree to the console.

printAllNodes

public void printAllNodes()
Prints descriptions of all Nodes of this Tree to the console.

setIndicatorsToZero

public void setIndicatorsToZero()
Sets the indicators of all Nodes of this Tree to 0.

calculateRealHeight

public double calculateRealHeight()
Calculates the real height of this (rooted) Tree -- the longest distance from root to external node. The height of this is stored and can be obtained with "getRealHeight()". Returns the difference in heights of the two subtrees originating at the root of this (which obviously only makes sense if this is rooted and binary at the root). Difference = height of subtree at child1 - height of subtree at child2 (i.e. is positive if subtree 1 is higher, negative otherwise).

Takes into account collapsed Nodes.

(Last modified: 01/18/01)

Returns:
the difference in heigh of the two subtrees originating at the root of this Tree

findExtremeLnL

public void findExtremeLnL()
Finds the highest of all log likelihood value associated with branches of this Tree. The result can be obtained with "getHighestLnL()". (Last modifed: 11/18/00)
See Also:
getHighestLnL()

isCompletelyBinary

public boolean isCompletelyBinary()
Returns whether this is a completely binary tree (i.e. all internal nodes are bifurcations).
(Last modifed: 05/26/01)

moveBranchLenghtsToBootstrap

public void moveBranchLenghtsToBootstrap()
Moves the values in the branch length field to the bootstrap field, for each Node of this Tree. Converts a Tree originating from a phylip treefile after bootstrapping and which therefore has its bootstrap values where the branch lenghts would be.

areBranchLenghtsBootstraps

public boolean areBranchLenghtsBootstraps()
Checks whether the branch length values actually are bootstrap values All external Nodes must have the same, >0, divisible by 10 branch length. Boostrap of root must be assigned.

toString

public java.lang.String toString()
Converts this Tree to a New Hampshire X (String) representation.
Overrides:
toString in class java.lang.Object
Returns:
New Hampshire X (String) representation of this
See Also:
toNewHampshireX()

toNewHampshire

public java.lang.String toNewHampshire(boolean clean_nh)
Converts this Tree to a New Hampshire (String) representation. If the boolean clean_nh is true, the length of sequence names will be truncated to MAX_LENGTH (usually 10) characters and everything after a "/" will be removed (including the "/").
Parameters:
clean_nh - set to true for clean NH format
Returns:
New Hampshire (String) representation of this

toNewHampshireX

public java.lang.String toNewHampshireX()
Converts this Tree to a New Hampshire X (String) representation.
Returns:
New Hampshire X (String) representation of this

getPath

public java.util.Vector getPath(Node node1,
                                Node node2,
                                boolean ret_pseudo_nodes)
                         throws java.lang.Exception
Returns a Vector containing the Node IDs of all Nodes which are between two external Nodes (node2 and node1). The order is so that element 0 is node2, and the last element is node1. Even if the Tree is rooted, this method does not return the root as part of the pathway (not ideal). The boolean ret_pseudo_nodes determines whether or not to return pseudo Nodes. (true: return pseudo nodes, false: only return real nodes.)

getSiblings

public java.util.Vector getSiblings(Node n)
                             throws java.lang.Exception
Returns a Vector of references to all external siblings and nieces of a external Node n. The order is the same as in the Tree.
Returns:
Vector of references to Nodes

getLastCommonAncestor

public Node getLastCommonAncestor(java.lang.String seqname1,
                                  java.lang.String seqname2)
                           throws java.lang.Exception
Finds the last common ancestor Node of two Nodes specified by their sequence names seqname1 and seqname2. This method obviously can produce a meaningful result only, if this Tree is correctly rooted. Is inefficient and clumsy (O(n2)). Do not use.

getLastCommonAncestor

public Node getLastCommonAncestor(int id1,
                                  int id2)
                           throws java.lang.Exception
Finds the last common ancestor Node of two Nodes specified by their IDs id1 and id2. This method obviously can produce a meaningful result only, if this Tree is correctly rooted. Is inefficient and clumsy (O(n2)). Do not use.

adjustNodeCount

public void adjustNodeCount()
(Re)counts the number of children for each Node of this Tree. As an example, this method needs to be called after a Tree has been reRooted. (Last modifed 11/20/00)

addNodeAndConnect

void addNodeAndConnect(java.lang.String s1,
                       java.lang.String s2)
                 throws java.lang.Exception
Used for building Trees.

levelOrderReID

public void levelOrderReID(int i)
Resets the ID numbers of the Nodes of this Tree in level order, starting with i (for the root). Warning. After this method has been called, node IDs are not longer unique. Implemented recursively. (Last modified: 11/20/00)
Parameters:
i - the starting value (int)

preorderReID

public int preorderReID(int i)
Resets the ID numbers of the Nodes of this Tree in preorder, starting with i. Implemented using a Stack. (Last modified: 11/20/00)
Parameters:
i - the starting value (int)
Returns:
i plus the total number of Nodes of this Tree (int)

hashIDs

public void hashIDs()
Hashes the ID number of each Node of this Tree to its corresonding Node, in order to make method getNode( id ) run in constant time. Important: The user is responsible for calling this method (again) after this Tree has been changed/created/renumbered.

FORESTER 1.7