FORESTER 1.8

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.820 -- last modified: 07/03/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 String nh_string.
 
Method Summary
(package private)  void addNodeAndConnect(java.lang.String s1, java.lang.String s2)
           
 void adjustNodeCount(boolean considerCollapsedNodes)
          (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 collapseToDeepestAnotNodes()
          Collapses this Tree's deepest Nodes anotated with either a sequence name or a species name.
 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).
 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.
 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 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.
 void orderAppearance(boolean order)
          Arranges the order of childern for each node of this Tree in such a way that either the branch with more children is on top (right) or on bottom (left), dependent on the value of boolean order.
 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 System.out.
 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.
 void removeExtNode(Node n)
          Removes external Node n 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(Node n)
          Places the root of this Tree on the parent branch Node n.
 void reRootSkeleton(Node n)
          Places the root of this Tree on the parent branch Node n.
 void setAllNodesToNotCollapse()
          Sets all Nodes of this Tree to not-collapsed.
 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 an empty Tree.

Tree

public Tree(java.lang.String nh_string)
     throws java.lang.Exception
Tree constructor which constructs a Tree from String 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

copyTree

public Tree copyTree()
Returns a deep copy of this Tree.

(The resulting Tree has its references in the external nodes corrected, if they are lacking/ obsolete in this.)

(Last modified: 06/11/01)


delete

public void delete()
Deletes this Tree.

subTree

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

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.

removeExtNode

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

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.

(Last modified: 06/13/01)

Parameters:
node - a Node of this Tree

orderAppearance

public void orderAppearance(boolean order)
Arranges the order of childern for each node of this Tree in such a way that either the branch with more children is on top (right) or on bottom (left), dependent on the value of boolean order.

(Last modified: 06/13/01)

Parameters:
order - decides in which direction to order

setAllNodesToNotCollapse

public void setAllNodesToNotCollapse()
Sets all Nodes of this Tree to not-collapsed.

In most cases methods adjustNodeCount(false) and recalculateAndReset() need to be called after this method has been called.

(Last modified: 07/03/01)


collapseToDeepestAnotNodes

public void collapseToDeepestAnotNodes()
Collapses this Tree's deepest Nodes anotated with either a sequence name or a species name. All other Nodes are uncollapsed.

(Last modified: 07/03/01)


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. 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(boolean)
  • recalculateAndReset()
    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. 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:

    (Last modified: 05/22/01)

    Parameters:
    n - Node of this Tree

    reRootSkeleton

    public void reRootSkeleton(Node n)
                        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.

    This method only considers the "skeleton" of the Tree: It ignores everything except the topology and branch lenghts. It also does not deal properly with multifurcated tree! DO NOT USE.

    This is ONLY to be used by methods in class SDIunrooted (in forester/tools)!

    (Last modified: 06/11/01)

    Parameters:
    n - Node of 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. We call these "super orthologs". 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

    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

    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

    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)

    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)

    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[]

    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()

    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

    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.

    isEmpty

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

    isCompletelyBinary

    public boolean isCompletelyBinary()
    Returns whether this is a completely binary tree (i.e. all internal nodes are bifurcations).

    (Last modifed: 05/26/01)


    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.

    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)

    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.

    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 "/").
    (Last modified: 06/28/01)
    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.
    (Last modified: 06/28/01)
    Returns:
    New Hampshire X (String) representation of this

    printExtNodes

    public void printExtNodes()
    Prints descriptions of all external Nodes of this Tree to System.out.

    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.

    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.

    recalculateAndReset

    public void recalculateAndReset()
    Recalculates and resets parameters of this Tree: To be used after Tree has been modified.

    (Last modified: 11/18/00)


    adjustNodeCount

    public void adjustNodeCount(boolean considerCollapsedNodes)
    (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 and it is to be diplayed.

    (Last modifed 06/28/00)

    Parameters:
    considerCollapsedNodes - set to true to take into account collapsed nodes (collapsed nodes have 1 child).

    addNodeAndConnect

    void addNodeAndConnect(java.lang.String s1,
                           java.lang.String s2)
                     throws java.lang.Exception

    FORESTER 1.8