Package pal.tree

Class 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 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.
      • 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.
      • 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.
      • 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.