Package pal.tree
Class TreeUtils
- java.lang.Object
-
- 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
Constructors Constructor Description TreeUtils()
-
Method Summary
All Methods Static Methods Concrete Methods Deprecated Methods Modifier and Type Method Description 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 nodesstatic 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 insteadstatic IdGroup
getLeafIdGroup(Tree tree)
get list of the identifiers of the external nodesstatic 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 identifiersstatic 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 treesstatic double
getRobinsonFouldsDistance(Tree t1, Tree t2)
computes Robinson-Foulds (1981) distance between two treesstatic double
getRobinsonFouldsRescaledDistance(SplitSystem s1, Tree t2)
computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1static double
getRobinsonFouldsRescaledDistance(Tree t1, Tree t2)
computes Robinson-Foulds (1981) distance between two trees rescaled to a number between 0 and 1static 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 formatstatic 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()
-
-
-
Method Detail
-
getRobinsonFouldsDistance
public static double getRobinsonFouldsDistance(Tree t1, Tree t2)
computes Robinson-Foulds (1981) distance between two trees- Parameters:
t1
- tree 1t2
- 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 1t2
- 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 nodename
- 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.
-
getNodeByName
public static final Node getNodeByName(Node root, java.lang.String name)
- Parameters:
root
- The root node of a treename
- 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.
-
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 streamprintLengths
- boolean variable determining whether branch lengths should be included in outputprintInternalLabels
- boolean variable determining whether internal labels should be included in output
-
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
- treea
- external node 1b
- 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 insteadGenerates 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 valuebaseTree
- the baseTreetreeGenerator
- 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- 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
- Parameters:
baseTree
- The base treeids
- The set of identifiers- Returns:
- A relabelled tree, or the input tree if no numbered leaves.
-
-