pal.tree
Class TreeUtils

java.lang.Object
  extended by pal.tree.TreeUtils

public class TreeUtils
extends java.lang.Object

various utility functions on trees.

Version:
$Id: TreeUtils.java,v 1.51 2004/04/28 01:03:15 matt Exp $
Author:
Alexei Drummond, Korbinian Strimmer, Matthew Goode

Constructor Summary
TreeUtils()
           
 
Method Summary
static void computeAllDistances(Tree tree, int a, double[] dist, double[] idist, boolean countEdges, double epsilon)
           
static double computeDistance(Tree tree, int a, int b)
          compute distance between two external nodes
static Alignment extractAlignment(Tree tree)
          Extracts an alignment from a tree.
static Alignment extractAlignment(Tree tree, boolean leaveSeqsInTree)
          Extracts an alignment from a tree.
static TimeOrderCharacterData extractTimeOrderCharacterData(Tree tree, int units)
          Extracts a time order character data from a tree.
static Tree generationsToMutations(Tree generationTree, MutationRateModel muModel)
          Takes a tree (in generation units) and returns a scaled version of it (in mutation units).
static Tree generationsToMutations(Tree generationTree, MutationRateModel muModel, double generationTime)
          Takes a tree (in generation units) and returns a scaled version of it (in mutation units).
static Tree getBootstrapSupportByCladeTree(java.lang.String attributeName, Tree baseTree, Tree[] alternativeTrees)
          Deprecated. Use getReplicateCladeSupport instead
static IdGroup getLeafIdGroup(Tree tree)
          get list of the identifiers of the external nodes
static Node getNodeByName(Node root, java.lang.String name)
           
static Node getNodeByName(Tree tree, java.lang.String name)
           
static Tree getNumberRelabelledTree(Tree baseTree, IdGroup ids)
          Create a new tree such that the labels are redifined from a base tree in such a manner: For each leaf label If the base label is not a number the new label is just the original label If the base label is a number the new label appropriately index label from a set identifiers
static Node getRandomNode(Tree tree)
          Returns a uniformly distributed random node from the tree, including both internal and external nodes.
static Tree getReplicateCladeSupport(java.lang.String attributeName, Tree baseTree, TreeGenerator treeGenerator, int numberOfReplicates, AlgorithmCallback callback)
          Generates a tree which is identical to baseTree but has attributes (defined by attributeName) at all internal nodes excluding the root node signifying (as a value between 0 and 100) the replicate support by clade (that is the proportion of replicates that produce the sub clade under that node)
static double getRobinsonFouldsDistance(SplitSystem s1, Tree t2)
          computes Robinson-Foulds (1981) distance between two trees
static double getRobinsonFouldsDistance(Tree t1, Tree t2)
          computes Robinson-Foulds (1981) distance between two trees
static double getRobinsonFouldsRescaledDistance(SplitSystem s1, Tree t2)
          computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1
static double getRobinsonFouldsRescaledDistance(Tree t1, Tree t2)
          computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1
static Tree getScaled(Tree oldTree, double rate)
          Takes a tree and returns a scaled version of it.
static Tree getScaled(Tree oldTree, double rate, int newUnits)
          Takes a tree and returns a scaled version of it.
static Tree getScaled(Tree mutationRateTree, MutationRateModel muModel)
          Takes a tree and returns a scaled version of it.
static Tree getScaled(Tree mutationRateTree, MutationRateModel muModel, int newUnits)
          Takes a tree and returns a scaled version of it.
static void labelInternalNodes(Tree tree)
          Labels the internal nodes of the tree using numbers starting from 0.
static int[] mapExternalIdentifiers(IdGroup idGroup, Tree tree)
          map external identifiers in the tree to a set of given identifiers (which can be larger than the set of external identifiers but must contain all of them) NOTE: for efficiency it is assumed that the node lists of the tree are correctly maintained.
static Tree mutationsToGenerations(Tree mutationTree, MutationRateModel muModel)
          Takes a tree (in mutation units) and returns a scaled version of it (in generation units).
static void printNH(Tree tree, java.io.PrintWriter out)
          print a this tree in New Hampshire format (including distances and internal labels)
static void printNH(Tree tree, java.io.PrintWriter out, boolean printLengths, boolean printInternalLabels)
          print this tree in New Hampshire format
static void renameNodes(Tree tree, java.util.Hashtable table)
          Given a translation table where the keys are the current identifier names and the values are the new identifier names, this method replaces the current identifiers in the tree with new identifiers.
static void report(Tree tree, java.io.PrintWriter out)
           
static void reroot(Tree tree, Node node)
           
static void rotateByLeafCount(Tree tree)
          Rotates branches by leaf count.
static Tree scale(Tree oldTree, double rate, int newUnits)
          Deprecated. use getScaled()
static Tree scale(Tree mutationRateTree, MutationRateModel muModel)
          Deprecated. use getScaled()
static Tree scale(Tree mutationRateTree, MutationRateModel muModel, int newUnits)
          Deprecated. use getScaled()
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

TreeUtils

public TreeUtils()
Method Detail

getRobinsonFouldsDistance

public static double getRobinsonFouldsDistance(Tree t1,
                                               Tree t2)
computes Robinson-Foulds (1981) distance between two trees

Parameters:
t1 - tree 1
t2 - tree 2 Definition: Assuming that t1 is the reference tree, let fn be the false negatives, i.e. the number of edges in t1 missing in t2, and fp the number of false positives, i.e. the number of edges in t2 missing in t1. The RF distance is then (fn + fp)/2

getRobinsonFouldsDistance

public static double getRobinsonFouldsDistance(SplitSystem s1,
                                               Tree t2)
computes Robinson-Foulds (1981) distance between two trees

Parameters:
s1 - tree 1 (as represented by a SplitSystem)
t2 - tree 2

getRobinsonFouldsRescaledDistance

public static double getRobinsonFouldsRescaledDistance(Tree t1,
                                                       Tree t2)
computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1

Parameters:
t1 - tree 1
t2 - tree 2

getRobinsonFouldsRescaledDistance

public static double getRobinsonFouldsRescaledDistance(SplitSystem s1,
                                                       Tree t2)
computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1

Parameters:
s1 - tree 1 (as represented by a SplitSystem)
t2 - tree 2

getRandomNode

public static Node getRandomNode(Tree tree)
Returns a uniformly distributed random node from the tree, including both internal and external nodes.


getNodeByName

public static final Node getNodeByName(Tree tree,
                                       java.lang.String name)
Parameters:
tree - The Tree supposidly containing such a named node
name - The name of the node to find.
Returns:
the first found node that has a certain name (as determined by the nodes Identifier) in the tree defined by a root node.
See Also:
Identifier, Node

getNodeByName

public static final Node getNodeByName(Node root,
                                       java.lang.String name)
Parameters:
root - The root node of a tree
name - The name of the node to find.
Returns:
the first found node that has a certain name (as determined by the nodes Identifier) in the tree defined by a root node.
See Also:
Identifier, Node

mutationsToGenerations

public static Tree mutationsToGenerations(Tree mutationTree,
                                          MutationRateModel muModel)
Takes a tree (in mutation units) and returns a scaled version of it (in generation units).

Parameters:
mutationRateModel - the mutation rate model used for scaling and the desired units are expected substitutions then this scale factor should be equal to the mutation rate.
newUnits - the new units of the tree.

generationsToMutations

public static Tree generationsToMutations(Tree generationTree,
                                          MutationRateModel muModel)
Takes a tree (in generation units) and returns a scaled version of it (in mutation units).

Parameters:
mutationRateModel - the mutation rate model. The mutation rate must be in units of mutations per site per generation.

generationsToMutations

public static Tree generationsToMutations(Tree generationTree,
                                          MutationRateModel muModel,
                                          double generationTime)
Takes a tree (in generation units) and returns a scaled version of it (in mutation units).

Parameters:
mutationRateModel - the mutation rate model in calendar units.
generationTime - the length of a generation in calendar units. If the mutation rate is in mutations per site per year, then the generation time will be in generations per year.

scale

public static Tree scale(Tree oldTree,
                         double rate,
                         int newUnits)
Deprecated. use getScaled()


getScaled

public static final Tree getScaled(Tree oldTree,
                                   double rate)
Takes a tree and returns a scaled version of it. Scales a tree keeping old units

Parameters:
rate - scale factor.

getScaled

public static final Tree getScaled(Tree oldTree,
                                   double rate,
                                   int newUnits)
Takes a tree and returns a scaled version of it.

Parameters:
rate - scale factor. If the original tree is in generations and the desired units are expected substitutions then this scale factor should be equal to the mutation rate.
newUnits - the new units of the tree.

scale

public static Tree scale(Tree mutationRateTree,
                         MutationRateModel muModel)
Deprecated. use getScaled()


getScaled

public static Tree getScaled(Tree mutationRateTree,
                             MutationRateModel muModel)
Takes a tree and returns a scaled version of it.

Parameters:
rate - scale factor. If the original tree is in generations and the desired units are expected substitutions then this scale factor should be equal to the mutation rate.

scale

public static Tree scale(Tree mutationRateTree,
                         MutationRateModel muModel,
                         int newUnits)
Deprecated. use getScaled()


getScaled

public static Tree getScaled(Tree mutationRateTree,
                             MutationRateModel muModel,
                             int newUnits)
Takes a tree and returns a scaled version of it.

Parameters:
rate - scale factor. If the original tree is in generations and the desired units are expected substitutions then this scale factor should be equal to the mutation rate.
newUnits - the new units of the tree. (Such as the mutationTree is measured in expected substitutions/newUnits)

renameNodes

public static void renameNodes(Tree tree,
                               java.util.Hashtable table)
Given a translation table where the keys are the current identifier names and the values are the new identifier names, this method replaces the current identifiers in the tree with new identifiers.


rotateByLeafCount

public static void rotateByLeafCount(Tree tree)
Rotates branches by leaf count. WARNING: assumes binary tree!


getLeafIdGroup

public static final IdGroup getLeafIdGroup(Tree tree)
get list of the identifiers of the external nodes

Returns:
leaf identifier group

mapExternalIdentifiers

public static final int[] mapExternalIdentifiers(IdGroup idGroup,
                                                 Tree tree)
                                          throws java.lang.IllegalArgumentException
map external identifiers in the tree to a set of given identifiers (which can be larger than the set of external identifiers but must contain all of them) NOTE: for efficiency it is assumed that the node lists of the tree are correctly maintained. This should take effect everywhere soon. Only methods that actually change a tree need to call createNodeList().

Parameters:
idGroup - an ordered group of identifiers
Returns:
list of links
Throws:
java.lang.IllegalArgumentException

labelInternalNodes

public static final void labelInternalNodes(Tree tree)
Labels the internal nodes of the tree using numbers starting from 0. Skips numbers already used by external leaves.


extractTimeOrderCharacterData

public static TimeOrderCharacterData extractTimeOrderCharacterData(Tree tree,
                                                                   int units)
Extracts a time order character data from a tree.


extractAlignment

public static Alignment extractAlignment(Tree tree,
                                         boolean leaveSeqsInTree)
Extracts an alignment from a tree.


extractAlignment

public static Alignment extractAlignment(Tree tree)
Extracts an alignment from a tree.


printNH

public static void printNH(Tree tree,
                           java.io.PrintWriter out)
print a this tree in New Hampshire format (including distances and internal labels)

Parameters:
out - output stream

printNH

public static void printNH(Tree tree,
                           java.io.PrintWriter out,
                           boolean printLengths,
                           boolean printInternalLabels)
print this tree in New Hampshire format

Parameters:
out - output stream
printLengths - boolean variable determining whether branch lengths should be included in output
printInternalLabels - boolean variable determining whether internal labels should be included in output

reroot

public static void reroot(Tree tree,
                          Node node)

computeAllDistances

public static void computeAllDistances(Tree tree,
                                       int a,
                                       double[] dist,
                                       double[] idist,
                                       boolean countEdges,
                                       double epsilon)

computeDistance

public static final double computeDistance(Tree tree,
                                           int a,
                                           int b)
compute distance between two external nodes

Parameters:
tree - tree
a - external node 1
b - external node 2
Returns:
distance between node a and b

report

public static void report(Tree tree,
                          java.io.PrintWriter out)

getBootstrapSupportByCladeTree

public static final Tree getBootstrapSupportByCladeTree(java.lang.String attributeName,
                                                        Tree baseTree,
                                                        Tree[] alternativeTrees)
Deprecated. Use getReplicateCladeSupport instead

Generates a tree which is identical to baseTree but has attributes (defined by attributeName) at all internal nodes excluding the root node signifying (as a value between 0 and 100) the bootstrap support by clade (that is the proportion of replicates that produce the sub clade under that node)


getReplicateCladeSupport

public static final Tree getReplicateCladeSupport(java.lang.String attributeName,
                                                  Tree baseTree,
                                                  TreeGenerator treeGenerator,
                                                  int numberOfReplicates,
                                                  AlgorithmCallback callback)
Generates a tree which is identical to baseTree but has attributes (defined by attributeName) at all internal nodes excluding the root node signifying (as a value between 0 and 100) the replicate support by clade (that is the proportion of replicates that produce the sub clade under that node)

Parameters:
attributeName - the name attached to the attribute which holds the clade support value
baseTree - the baseTree
treeGenerator - the source of the replicates. This approach is used of supplying an array of trees as it can save memory! For bootstrap analysis, create an iterator that builds new trees based on bootstrap alignment.
numberOfReplicates - the number of replicates to extract from the TreeGenerator for use in calculating clade support (does not include base tree)
callback - An AlgorithmCallback object for monitoring progress
See Also:
pal.gui.TreePainter.BOOTSTRAP_ATTRIBUTE_NAME

getNumberRelabelledTree

public static final Tree getNumberRelabelledTree(Tree baseTree,
                                                 IdGroup ids)
Create a new tree such that the labels are redifined from a base tree in such a manner: For each leaf label
  1. If the base label is not a number the new label is just the original label
  2. If the base label is a number the new label appropriately index label from a set identifiers

Parameters:
baseTree - The base tree
ids - The set of identifiers
Returns:
A relabelled tree, or the input tree if no numbered leaves.