bpp-phyl  2.3.0
bpp::TreeTools Class Reference

Generic utilitary methods dealing with trees. More...

#include <Bpp/Phyl/TreeTools.h>

+ Collaboration diagram for bpp::TreeTools:

Classes

struct  Moments_
 

Public Member Functions

 TreeTools ()
 
virtual ~TreeTools ()
 

Static Public Member Functions

static TreeMRP (const std::vector< Tree * > &vecTr)
 Matrix Representation Parsimony supertree method. More...
 
static void computeBootstrapValues (Tree &tree, const std::vector< Tree * > &vecTr, bool verbose=true, int format=0)
 Compute bootstrap values. More...
 
static void constrainedMidPointRooting (Tree &tree)
 Determine the mid-point position of the root along the branch that already contains the root. Consequently, the topology of the rooted tree remains identical. More...
 
static TreeMRPMultilabel (const std::vector< Tree * > &vecTr)
 Matrix Representation Parsimony supertree method for multilabel trees. More...
 
Retrieve topology information
static std::vector< int > getLeavesId (const Tree &tree, int nodeId) throw (NodeNotFoundException)
 Retrieve all leaves from a subtree. More...
 
static void getLeavesId (const Tree &tree, int nodeId, std::vector< int > &leaves) throw (NodeNotFoundException)
 Retrieve all leaves from a subtree. More...
 
static size_t getNumberOfLeaves (const Tree &tree, int nodeId) throw (NodeNotFoundException)
 Count the number of leaves from a subtree. More...
 
static int getLeafId (const Tree &tree, int nodeId, const std::string &name) throw (NodeNotFoundException)
 Get the id of a leaf given its name in a subtree. More...
 
static void searchLeaf (const Tree &tree, int nodeId, const std::string &name, int *&id) throw (NodeNotFoundException)
 Get the id of a leaf given its name in a subtree. More...
 
static std::vector< int > getPathBetweenAnyTwoNodes (const Tree &tree, int nodeId1, int nodeId2, bool includeAncestor=true) throw (NodeNotFoundException)
 Get a vector of ancestor nodes between to nodes. More...
 
static std::vector< int > getAncestors (const Tree &tree, int nodeId) throw (NodeNotFoundException)
 Get a list of all ids of parents nodes, from the current node (not included) to the root of the tree. More...
 
static int getLastCommonAncestor (const Tree &tree, const std::vector< int > &nodeIds) throw (NodeNotFoundException, Exception)
 Get the id of the last common ancestors of all specified nodes. More...
 
static size_t getDepth (const Tree &tree, int nodeId) throw (NodeNotFoundException)
 Get the depth of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'. More...
 
static size_t getDepths (const Tree &tree, int nodeId, std::map< int, size_t > &depths) throw (NodeNotFoundException)
 Get the depths for all nodes of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'. More...
 
static double getHeight (const Tree &tree, int nodeId) throw (NodeNotFoundException,NodeException)
 Get the height of the subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree. More...
 
static double getHeights (const Tree &tree, int nodeId, std::map< int, double > &heights) throw (NodeNotFoundException,NodeException)
 Get the heights of all nodes within a subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree. More...
 
Conversion tools.

Convert to Newick standard tree description. The description is for a node, and hence is to be surrounded with parenthesis. ex: (A:0.001, (B:0.001, C:0.02)90:0.005)50:0.0005

static std::string nodeToParenthesis (const Tree &tree, int nodeId, bool writeId=false) throw (NodeNotFoundException)
 Get the parenthesis description of a subtree. More...
 
static std::string nodeToParenthesis (const Tree &tree, int nodeId, bool bootstrap, const std::string &propertyName) throw (NodeNotFoundException)
 Get the parenthesis description of a subtree. More...
 
static std::string treeToParenthesis (const Tree &tree, bool writeId=false)
 Get the parenthesis description of a tree. More...
 
static std::string treeToParenthesis (const Tree &tree, bool bootstrap, const std::string &propertyName)
 Get the parenthesis description of a tree. More...
 
Deal with identifiers
static std::vector< int > getNodesId (const Tree &tree, int nodeId) throw (NodeNotFoundException)
 Retrieve all nodes ids nodes from a subtree. More...
 
static void getNodesId (const Tree &tree, int nodeId, std::vector< int > &nodes) throw (NodeNotFoundException)
 Retrieve all nodes ids from a subtree. More...
 
static int getMaxId (const Tree &tree, int id)
 Get the maximum identifier used in a (sub)tree. More...
 
static int getMPNUId (const Tree &tree, int id)
 Get the minimum positive non-used identifier in a (sub)tree. More...
 
static bool checkIds (const Tree &tree, bool throwException) throw (Exception)
 Check if the ids are uniques. More...
 
Topology methods
static VectorSiteContainerMRPEncode (const std::vector< Tree * > &vecTr)
 Creates a sequence data set corresponding to the Matrix Representation of the input trees. More...
 
static VectorSiteContainerMRPEncodeMultilabel (const std::vector< Tree * > &vecTr)
 Creates a sequence data set corresponding to the Matrix Representation of the input multilabel trees. More...
 
static bool haveSameTopology (const Tree &tr1, const Tree &tr2)
 Tells whether two trees have the same unrooted topology. More...
 
static int robinsonFouldsDistance (const Tree &tr1, const Tree &tr2, bool checkNames=true, int *missing_in_tr2=NULL, int *missing_in_tr1=NULL) throw (Exception)
 Calculates the Robinson-Foulds topological distance between two trees. More...
 
static BipartitionListbipartitionOccurrences (const std::vector< Tree * > &vecTr, std::vector< size_t > &bipScore)
 Counts the total number of occurrences of every bipartition from the input trees. More...
 
static TreeTemplate< Node > * thresholdConsensus (const std::vector< Tree * > &vecTr, double threshold, bool checkNames=true) throw (Exception)
 General greedy consensus tree method. More...
 
static TreeTemplate< Node > * fullyResolvedConsensus (const std::vector< Tree * > &vecTr, bool checkNames=true)
 Fully-resolved greedy consensus tree method. More...
 
static TreeTemplate< Node > * majorityConsensus (const std::vector< Tree * > &vecTr, bool checkNames=true)
 Majority consensus tree method. More...
 
static TreeTemplate< Node > * strictConsensus (const std::vector< Tree * > &vecTr, bool checkNames=true)
 Strict consensus tree method. More...
 

Act on branch lengths.

static Vdouble getBranchLengths (const Tree &tree, int nodeId) throw (NodeNotFoundException,NodeException)
 Get all the branch lengths of a subtree. More...
 
static double getTotalLength (const Tree &tree, int nodeId, bool includeAncestor=true) throw (NodeNotFoundException,NodeException)
 Get the total length (sum of all branch lengths) of a subtree. More...
 
static void setBranchLengths (Tree &tree, int nodeId, double brLen) throw (NodeNotFoundException)
 Set all the branch lengths of a subtree. More...
 
static void setVoidBranchLengths (Tree &tree, int nodeId, double brLen) throw (NodeNotFoundException)
 Give a length to branches that don't have one in a subtree. More...
 
static void scaleTree (Tree &tree, int nodeId, double factor) throw (NodeNotFoundException,NodeException)
 Scale a given tree. More...
 
static void initBranchLengthsGrafen (Tree &tree)
 Grafen's method to initialize branch lengths. More...
 
static void computeBranchLengthsGrafen (Tree &tree, double power=1, bool init=true) throw (NodeException)
 Compute branch lengths using Grafen's method. More...
 
static double convertToClockTree (Tree &tree, int nodeId, bool noneg=false)
 Modify a tree's branch lengths to make a clock tree, by rebalancing branch lengths. More...
 
static double convertToClockTree2 (Tree &tree, int nodeId)
 Modify a tree's branch lengths to make a clock tree, by rescaling subtrees. More...
 
static double getDistanceBetweenAnyTwoNodes (const Tree &tree, int nodeId1, int nodeId2)
 Get the total distance between two nodes. More...
 
static DistanceMatrixgetDistanceMatrix (const Tree &tree)
 Compute a distance matrix from a tree. More...
 
static void midpointRooting (Tree &tree)
 (Re)root the tree using the midpoint method. More...
 
static size_t initBranchLengthsGrafen (Tree &tree, int nodeId) throw (NodeNotFoundException)
 
static void computeBranchLengthsGrafen (Tree &tree, int nodeId, double power, double total, double &height, double &heightRaised) throw (NodeNotFoundException,NodeException)
 

Some properties.

static const std::string BOOTSTRAP = "bootstrap"
 Bootstrap tag. More...
 
static Moments_ statFromNode_ (Tree &tree, int rootId)
 
static double bestRootPosition_ (Tree &tree, int nodeId1, int nodeId2, double length)
 

Detailed Description

Generic utilitary methods dealing with trees.

These methods work with all Tree object. However, depending on the tree implementation, they may not be the most efficient.

See also
TreeTemplateTools

Definition at line 66 of file TreeTools.h.

Constructor & Destructor Documentation

bpp::TreeTools::TreeTools ( )
inline

Definition at line 69 of file TreeTools.h.

Member Function Documentation

double TreeTools::bestRootPosition_ ( Tree tree,
int  nodeId1,
int  nodeId2,
double  length 
)
staticprivate
BipartitionList * TreeTools::bipartitionOccurrences ( const std::vector< Tree * > &  vecTr,
std::vector< size_t > &  bipScore 
)
static

Counts the total number of occurrences of every bipartition from the input trees.

Returns the list of distinct bipartitions found at least once in the set of input trees, and writes the number of occurrence of each of these bipartitions in vector bipScore.

Author
Nicolas Galtier
Parameters
vecTrVector of input trees (must share a common set of leaves - not checked in this function)
bipScoreOutput as the numbers of occurrences of the returned distinct bipartitions
Returns
A BipartitionList object including only distinct bipartitions

Definition at line 958 of file TreeTools.cpp.

References bpp::BipartitionList::addTrivialBipartitions(), bpp::BipartitionList::areIdentical(), bpp::BipartitionList::deleteBipartition(), bpp::BipartitionList::getNumberOfBipartitions(), bpp::BipartitionList::getNumberOfElements(), bpp::BipartitionList::getPartitionSize(), bpp::BipartitionTools::mergeBipartitionLists(), and bpp::BipartitionList::removeTrivialBipartitions().

Referenced by ~TreeTools().

bool TreeTools::checkIds ( const Tree tree,
bool  throwException 
)
throw (Exception
)
static

Check if the ids are uniques.

Parameters
treeThe tree to check.
throwExceptionIf set to true, the function throws qn exception if a duplicated is found.
Returns
true if the tree has uniqe ids.

Definition at line 783 of file TreeTools.cpp.

References bpp::TextTools::toString().

Referenced by bpp::AbstractHomogeneousTreeLikelihood::init_(), bpp::AbstractNonHomogeneousTreeLikelihood::init_(), and ~TreeTools().

void TreeTools::computeBootstrapValues ( Tree tree,
const std::vector< Tree * > &  vecTr,
bool  verbose = true,
int  format = 0 
)
static

Compute bootstrap values.

Parameters
treeInput tree. the BOOTSTRAP banch property of the tree will be modified if it already exists.
vecTrA list of trees to compare to 'tree'.
verboseTell if a progress bar should be displayed.
formatIf null or positive, bootstrap values are reported as percentage, with the given number of decimal digits. If negative, bootstrap calues are the raw number of tree occurrences.

Definition at line 1124 of file TreeTools.cpp.

References bpp::BipartitionTools::areIdentical(), bpp::ApplicationTools::displayGauge(), bpp::BipartitionList::getNumberOfBipartitions(), bpp::Tree::isLeaf(), and bpp::Tree::setBranchProperty().

Referenced by ~TreeTools().

void TreeTools::computeBranchLengthsGrafen ( Tree tree,
double  power = 1,
bool  init = true 
)
throw (NodeException
)
static

Compute branch lengths using Grafen's method.

The 'height' of each node is devided by the total height of the tree, and the ratio is raised at power 'rho'. A value of rho=0 hence returns a star tree.

Reference: Grafen A. The phylogenetic regression. Philos Trans R Soc Lond B Biol Sci. 1989; 326(1233):119-57

Parameters
treeThe tree to use.
powerThe rho parameter.
initTell if the height must be initialized by calling the initBranchLengthsGrafen() method. Otherwise use branch lengths.
Exceptions
NodeExceptionIf init=false and one branch length is lacking.

Definition at line 618 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::computeBranchLengthsGrafen ( Tree tree,
int  nodeId,
double  power,
double  total,
double &  height,
double &  heightRaised 
)
throw (NodeNotFoundException,
NodeException
)
staticprivate

Definition at line 583 of file TreeTools.cpp.

void TreeTools::constrainedMidPointRooting ( Tree tree)
static

Determine the mid-point position of the root along the branch that already contains the root. Consequently, the topology of the rooted tree remains identical.

This code uses two inner functions to compute the mid-point position: statFromNode_ and bestRootPosition_. This code is inspired by a code performing a similar calculation in Seaview (Guindon et al., 2010, Mol. Biol. Evol. 27(2):221-4).

Parameters
treeThe rooted tree for which the root has to be moved to its mid-point position, along the branch where it already stands.

Definition at line 1205 of file TreeTools.cpp.

References bpp::Tree::getDistanceToFather(), bpp::Tree::getRootId(), bpp::Tree::getSonsId(), bpp::Tree::isMultifurcating(), bpp::Tree::isRooted(), and bpp::Tree::setDistanceToFather().

Referenced by ~TreeTools().

double TreeTools::convertToClockTree ( Tree tree,
int  nodeId,
bool  noneg = false 
)
static

Modify a tree's branch lengths to make a clock tree, by rebalancing branch lengths.

The height of each node is set to the mean height of all son nodes. This may however lead to negative branch lengths, since the mean heigth may be inferior to one of the son heights, due to short branch lengths. If the 'noneg' is set to yes, the mean height is checked against all son heights. If it is inferior to one of the son heights, the maximum son height is used instead. This results in a multifurcation.

This method is recursive and will be applied on all sons nodes.

Parameters
treeThe tree to use.
nodeIdThe node defining the subtree.
nonegTell if the correction for non negative branch lengths must be used.
Returns
The modified height of the node.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf one branch length is lacking.

Definition at line 634 of file TreeTools.cpp.

References bpp::Tree::getDistanceToFather(), bpp::Tree::getSonsId(), bpp::Tree::hasDistanceToFather(), bpp::Tree::hasNode(), and bpp::Tree::setDistanceToFather().

Referenced by ~TreeTools().

double TreeTools::convertToClockTree2 ( Tree tree,
int  nodeId 
)
static

Modify a tree's branch lengths to make a clock tree, by rescaling subtrees.

The height of each node is set to the mean height of all son nodes. All branch lengths of the corresponding subtrees are updated proportionally. This algorithm is smaller than the convertToClockTree method, but may be more accurate.

This method is recursive and will be applied on all sons nodes.

Parameters
treeThe tree to use.
nodeIdThe node defining the subtree.
Returns
The modified height of the node.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf one branch length is lacking.

Definition at line 669 of file TreeTools.cpp.

References bpp::Tree::getDistanceToFather(), bpp::Tree::getSonsId(), bpp::Tree::hasDistanceToFather(), and bpp::Tree::hasNode().

Referenced by ~TreeTools().

TreeTemplate< Node > * TreeTools::fullyResolvedConsensus ( const std::vector< Tree * > &  vecTr,
bool  checkNames = true 
)
static

Fully-resolved greedy consensus tree method.

Calls thresholdConsensus with threshold=0, i.e. no constraint on the number of occurrence of bipartitions. The resulting tree is fully resolved.

Author
Nicolas Galtier
Parameters
vecTrVector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNamesTell whether we should check the trees first.

Definition at line 1074 of file TreeTools.cpp.

Referenced by ~TreeTools().

vector< int > TreeTools::getAncestors ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
static

Get a list of all ids of parents nodes, from the current node (not included) to the root of the tree.

Parameters
treeThe tree to use.
nodeIdThe id of node defining the subtree.
Returns
The list of ancestors ids.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 1158 of file TreeTools.cpp.

Referenced by ~TreeTools().

Vdouble TreeTools::getBranchLengths ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException,
NodeException
)
static

Get all the branch lengths of a subtree.

Parameters
treeThe tree.
nodeIdThe node defining the subtree.
Returns
A vector with all branch lengths.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf a branch length is lacking.

Definition at line 472 of file TreeTools.cpp.

Referenced by ~TreeTools().

size_t TreeTools::getDepth ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
static

Get the depth of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'.

ex:

+----------A
|
---+ N1 +-------B
| |
+--------+ N2
|
+------C

Depth of node 'N1' id 2, depth of node 'N2' is 1, depth of leaves is 0.

Parameters
treeThe tree.
nodeIdThe id of node defining the subtree.
Returns
The depth of the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 174 of file TreeTools.cpp.

Referenced by ~TreeTools().

size_t TreeTools::getDepths ( const Tree tree,
int  nodeId,
std::map< int, size_t > &  depths 
)
throw (NodeNotFoundException
)
static

Get the depths for all nodes of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'.

ex:

*    +----------A
*    |
* ---+ N1     +-------B
*    |        |
*    +--------+ N2
*             |
*             +------C
* 

Depth of node 'N1' id 2, depth of node 'N2' is 1, depth of leaves is 0.

Parameters
treeThe tree.
nodeIdThe id of node defining the subtree.
depthsThe map that will contain all the depths of the nodes, with node ids as keys.
Returns
The depth of the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 191 of file TreeTools.cpp.

Referenced by ~TreeTools().

double TreeTools::getDistanceBetweenAnyTwoNodes ( const Tree tree,
int  nodeId1,
int  nodeId2 
)
static

Get the total distance between two nodes.

Sum all branch lengths between two nodes.

Parameters
treeThe tree to consider.
nodeId1First node id.
nodeId2Second node id.
Returns
The sum of all branch lengths between the two nodes.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 455 of file TreeTools.cpp.

References bpp::Tree::getDistanceToFather(), and bpp::Tree::hasNode().

Referenced by ~TreeTools().

DistanceMatrix * TreeTools::getDistanceMatrix ( const Tree tree)
static

Compute a distance matrix from a tree.

Compute all distances between each leaves and store them in a matrix. A new DistanceMatrix object is created, and a pointer toward it is returned. The destruction of this matrix is left up to the user.

See also
getDistanceBetweenAnyTwoNodes
Parameters
treeThe tree to use.
Returns
The distance matrix computed from tree.

Definition at line 702 of file TreeTools.cpp.

References bpp::Tree::getLeafId(), and bpp::Tree::getLeavesNames().

Referenced by ~TreeTools().

double TreeTools::getHeight ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException,
NodeException
)
static

Get the height of the subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree.

The distance do not include the branch length of the subtree root node. The height of a leaf is hence 0.

Parameters
treeThe tree.
nodeIdThe id of node defining the subtree.
Returns
The height of the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf a branch length is lacking.

Definition at line 209 of file TreeTools.cpp.

Referenced by ~TreeTools().

double TreeTools::getHeights ( const Tree tree,
int  nodeId,
std::map< int, double > &  heights 
)
throw (NodeNotFoundException,
NodeException
)
static

Get the heights of all nodes within a subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree.

The height of a leaf is 0.

Parameters
treeThe tree.
nodeIdThe id of node defining the subtree.
heightsThe map that will contain all the heights of the nodes, with node ids as keys.
Returns
The height of the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf a branch length is lacking.

Definition at line 231 of file TreeTools.cpp.

Referenced by ~TreeTools().

int TreeTools::getLastCommonAncestor ( const Tree tree,
const std::vector< int > &  nodeIds 
)
throw (NodeNotFoundException,
Exception
)
static

Get the id of the last common ancestors of all specified nodes.

Nodes id need not correspond to leaves.

Author
Simon Carrignon
Parameters
treeThe tree to use.
nodeIdsThe ids of the input nodes.
Exceptions
NodeNotFoundExceptionIf at least of of input node is not found.

Definition at line 1172 of file TreeTools.cpp.

Referenced by ~TreeTools().

int TreeTools::getLeafId ( const Tree tree,
int  nodeId,
const std::string &  name 
)
throw (NodeNotFoundException
)
static

Get the id of a leaf given its name in a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
nameThe name of the node.
Returns
The id of the node.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 118 of file TreeTools.cpp.

Referenced by ~TreeTools().

vector< int > TreeTools::getLeavesId ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
static

Retrieve all leaves from a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
Returns
A vector with the ids of all leaves in the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 76 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::getLeavesId ( const Tree tree,
int  nodeId,
std::vector< int > &  leaves 
)
throw (NodeNotFoundException
)
static

Retrieve all leaves from a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
leavesA vector with the ids of all leaves in the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 83 of file TreeTools.cpp.

int TreeTools::getMaxId ( const Tree tree,
int  id 
)
static

Get the maximum identifier used in a (sub)tree.

This is a recursive method.

Parameters
treeThe tree to check.
idThe identifier of the subtree from which the recursion will be performed. Use id=tree.getRootId() to search for the whole tree.
Returns
The identifier number with maximum value.

Definition at line 752 of file TreeTools.cpp.

References bpp::Tree::getSonsId().

Referenced by ~TreeTools().

int TreeTools::getMPNUId ( const Tree tree,
int  id 
)
static

Get the minimum positive non-used identifier in a (sub)tree.

This method uses the recursive method getNodesId, and then sort the ids.

Parameters
treeThe tree to check.
idThe identifier of the subtree from which the recursion will be performed. Use id=tree.getRootId() to search for the whole tree.
Returns
A non-used identifier number.

Definition at line 767 of file TreeTools.cpp.

Referenced by bpp::TreeTemplate< bpp::NodeTemplate >::getNextId(), bpp::TreeTemplateTools::midRoot(), and ~TreeTools().

vector< int > TreeTools::getNodesId ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
static

Retrieve all nodes ids nodes from a subtree.

Parameters
treeThe tree
nodeIdThe id of the node that defines the subtree.
Returns
A vector of ids of each node in the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 153 of file TreeTools.cpp.

Referenced by bpp::RNonHomogeneousMixedTreeLikelihood::init(), and ~TreeTools().

void TreeTools::getNodesId ( const Tree tree,
int  nodeId,
std::vector< int > &  nodes 
)
throw (NodeNotFoundException
)
static

Retrieve all nodes ids from a subtree.

Parameters
treeThe tree
nodeIdThe id of the node that defines the subtree.
nodesA vector of ids of each node in the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 160 of file TreeTools.cpp.

size_t TreeTools::getNumberOfLeaves ( const Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
static

Count the number of leaves from a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 98 of file TreeTools.cpp.

Referenced by ~TreeTools().

vector< int > TreeTools::getPathBetweenAnyTwoNodes ( const Tree tree,
int  nodeId1,
int  nodeId2,
bool  includeAncestor = true 
)
throw (NodeNotFoundException
)
static

Get a vector of ancestor nodes between to nodes.

Parameters
treeThe tree to use.
nodeId1Id of first node.
nodeId2Id of second node.
includeAncestorTell if the common ancestor must be included in the vector.
Returns
A vector of ancestor nodes ids.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 401 of file TreeTools.cpp.

Referenced by ~TreeTools().

double TreeTools::getTotalLength ( const Tree tree,
int  nodeId,
bool  includeAncestor = true 
)
throw (NodeNotFoundException,
NodeException
)
static

Get the total length (sum of all branch lengths) of a subtree.

Parameters
treeThe tree.
nodeIdThe node defining the subtree.
includeAncestorTell if the branch length of the most ancient node should be included in the counting. (this should be set to false if this node is the root of the tree for instance).
Returns
The total length of the subtree.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf a branch length is lacking.

Definition at line 495 of file TreeTools.cpp.

Referenced by ~TreeTools().

bool TreeTools::haveSameTopology ( const Tree tr1,
const Tree tr2 
)
static
void TreeTools::initBranchLengthsGrafen ( Tree tree)
static

Grafen's method to initialize branch lengths.

Each height of the node (total distance from the leaves) is set equal to the number of leaf nodes for the corresponding subtrees - 1 for inner nodes, 0 for leaves.

If the tree already has branch lengths, they will be ignored.

Reference: Grafen A. The phylogenetic regression. Philos Trans R Soc Lond B Biol Sci. 1989; 326(1233):119-57

Parameters
treeThe tree.

Definition at line 576 of file TreeTools.cpp.

References bpp::Tree::getRootId().

Referenced by ~TreeTools().

size_t TreeTools::initBranchLengthsGrafen ( Tree tree,
int  nodeId 
)
throw (NodeNotFoundException
)
staticprivate

Definition at line 558 of file TreeTools.cpp.

TreeTemplate< Node > * TreeTools::majorityConsensus ( const std::vector< Tree * > &  vecTr,
bool  checkNames = true 
)
static

Majority consensus tree method.

Calls thresholdConsensus with threshold=0.5: internal branches present in a majority of trees are kept.

Author
Nicolas Galtier
Parameters
vecTrVector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNamesTell whether we should check the trees first.

Definition at line 1081 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::midpointRooting ( Tree tree)
static

(Re)root the tree using the midpoint method.

This methods compute the pairwise distance matrix from the tree and get the maximum distance. The root is then set on the branch located at half this distance.

Parameters
treeThe tree to (re)root.
Deprecated:
Use TreeTemplateTools::midRoot instead!

Definition at line 719 of file TreeTools.cpp.

References bpp::DistanceMatrix::asMatrix(), bpp::Tree::getDistanceToFather(), bpp::Tree::getFatherId(), bpp::Tree::getLeafId(), bpp::DistanceMatrix::getName(), bpp::Tree::getRootId(), bpp::Tree::getSonsId(), bpp::Tree::isRooted(), bpp::Tree::newOutGroup(), bpp::Tree::setDistanceToFather(), bpp::Tree::unroot(), and bpp::MatrixTools::whichMax().

Referenced by ~TreeTools().

Tree * TreeTools::MRP ( const std::vector< Tree * > &  vecTr)
static

Matrix Representation Parsimony supertree method.

This implementation of the MRP method takes a BIONJ tree (Jukes-Cantor distances) as the starting tree and optimizes the parsimony score using only NNI (in a PHYML-like way).

Author
Nicolas Galtier
Parameters
vecTrA vector of trees.
Returns
The MRP super tree.

Definition at line 1095 of file TreeTools.cpp.

References bpp::BioNJ::computeTree(), bpp::OutputStream::endLine(), bpp::VectorSiteContainer::getAlphabet(), bpp::DistanceEstimation::getMatrix(), bpp::AbstractAgglomerativeDistanceMethod::getTree(), bpp::ApplicationTools::message, MRPEncode(), bpp::OptimizationTools::optimizeTreeNNI(), and bpp::BioNJ::setDistanceMatrix().

Referenced by ~TreeTools().

VectorSiteContainer * TreeTools::MRPEncode ( const std::vector< Tree * > &  vecTr)
static

Creates a sequence data set corresponding to the Matrix Representation of the input trees.

Author
Nicolas Galtier Trees can have distinct sets of elements - missing data will be represented as 'N'. The output alignment (DNA sequences including only A, C and N)) is ready for maximum parsimony analysis according to the MRP supertree method.

Definition at line 801 of file TreeTools.cpp.

References bpp::BipartitionTools::MRPEncode().

Referenced by MRP(), MRPMultilabel(), and ~TreeTools().

VectorSiteContainer * TreeTools::MRPEncodeMultilabel ( const std::vector< Tree * > &  vecTr)
static

Creates a sequence data set corresponding to the Matrix Representation of the input multilabel trees.

Author
Nicolas Galtier and Bastien Boussau Trees can have distinct sets of elements - missing data will be represented as 'N'. The output alignment (DNA sequences including only A, C and N)) is ready for maximum parsimony analysis according to the MRP supertree method.

Definition at line 821 of file TreeTools.cpp.

References bpp::BipartitionTools::MRPEncodeMultilabel().

Referenced by ~TreeTools().

Tree * TreeTools::MRPMultilabel ( const std::vector< Tree * > &  vecTr)
static

Matrix Representation Parsimony supertree method for multilabel trees.

This implementation of the MRP method takes a BIONJ tree (Jukes-Cantor distances) as the starting tree and optimizes the parsimony score using only NNI (in a PHYML-like way).

Author
Nicolas Galtier slightly modified by Bastien Boussau
Parameters
vecTrA vector of trees.
Returns
The MRP super tree.

Definition at line 1287 of file TreeTools.cpp.

References bpp::BioNJ::computeTree(), bpp::OutputStream::endLine(), bpp::VectorSiteContainer::getAlphabet(), bpp::DistanceEstimation::getMatrix(), bpp::AbstractAgglomerativeDistanceMethod::getTree(), bpp::ApplicationTools::message, MRPEncode(), bpp::OptimizationTools::optimizeTreeNNI(), and bpp::BioNJ::setDistanceMatrix().

Referenced by ~TreeTools().

string TreeTools::nodeToParenthesis ( const Tree tree,
int  nodeId,
bool  writeId = false 
)
throw (NodeNotFoundException
)
static

Get the parenthesis description of a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
writeIdTells if node ids must be printed. This will overwrite bootstrap values if there are ones. Leaves id will be added to the leave names, separated by a '_' character.
Returns
A string in the parenthesis format.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 254 of file TreeTools.cpp.

Referenced by ~TreeTools().

string TreeTools::nodeToParenthesis ( const Tree tree,
int  nodeId,
bool  bootstrap,
const std::string &  propertyName 
)
throw (NodeNotFoundException
)
static

Get the parenthesis description of a subtree.

Parameters
treeThe tree
nodeIdThe node defining the subtree.
bootstrapTell is bootstrap values must be writen. If so, the content of the property with name TreeTools::BOOTSTRAP will be written as bootstrap value. The property should be a Number<double> object. Otherwise, the content of the property with name 'propertyName' will be written. In this later case, the property should be a String object.
propertyNameThe name of the property to use. Only used if bootstrap = false.
Returns
A string in the parenthesis format.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 292 of file TreeTools.cpp.

int TreeTools::robinsonFouldsDistance ( const Tree tr1,
const Tree tr2,
bool  checkNames = true,
int *  missing_in_tr2 = NULL,
int *  missing_in_tr1 = NULL 
)
throw (Exception
)
static

Calculates the Robinson-Foulds topological distance between two trees.

The two trees must share a common set of leaves (checked if checkNames is true) Three numbers are calculated:

Author
Nicolas Galtier
Parameters
tr1First input tree.
tr2Second input tree.
missing_in_tr2Output as the number of bipartitions occurring in the first tree but not the second
missing_in_tr1Output as the number of bipartitions occurring in the second tree but not the first
checkNamesTell whether we should check the trees first.
Returns
Robinson-Foulds distance = *missing_in_tr1 + *missing_in_tr2
Exceptions
ExceptionIf checkNames is set to true and trees do not share the same leaves names.

Definition at line 892 of file TreeTools.cpp.

References bpp::BipartitionTools::areIdentical(), bpp::BipartitionList::getNumberOfBipartitions(), bpp::BipartitionList::getPartitionSize(), bpp::VectorTools::haveSameElements(), bpp::BipartitionList::removeTrivialBipartitions(), and bpp::BipartitionList::sortByPartitionSize().

Referenced by bpp::OptimizationTools::buildDistanceTree(), and ~TreeTools().

void TreeTools::scaleTree ( Tree tree,
int  nodeId,
double  factor 
)
throw (NodeNotFoundException,
NodeException
)
static

Scale a given tree.

Multiply all branch lengths by a given factor.

Parameters
treeThe tree.
nodeIdThe node defining the subtree.
factorThe factor to multiply all branch lengths with.
Exceptions
NodeNotFoundExceptionIf the node is not found.
NodeExceptionIf a branch length is lacking.

Definition at line 539 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::searchLeaf ( const Tree tree,
int  nodeId,
const std::string &  name,
int *&  id 
)
throw (NodeNotFoundException
)
static

Get the id of a leaf given its name in a subtree.

Parameters
treeThe tree
nodeIdThe id of node defining the subtree.
nameThe name of the node.
idThe id of the node.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 133 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::setBranchLengths ( Tree tree,
int  nodeId,
double  brLen 
)
throw (NodeNotFoundException
)
static

Set all the branch lengths of a subtree.

Parameters
treeThe tree.
nodeIdThe node defining the subtree.
brLenThe branch length to apply.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 512 of file TreeTools.cpp.

Referenced by ~TreeTools().

void TreeTools::setVoidBranchLengths ( Tree tree,
int  nodeId,
double  brLen 
)
throw (NodeNotFoundException
)
static

Give a length to branches that don't have one in a subtree.

Parameters
treeThe tree.
nodeIdThe node defining the subtree.
brLenThe branch length to apply.
Exceptions
NodeNotFoundExceptionIf the node is not found.

Definition at line 525 of file TreeTools.cpp.

Referenced by ~TreeTools().

TreeTemplate< Node > * TreeTools::strictConsensus ( const std::vector< Tree * > &  vecTr,
bool  checkNames = true 
)
static

Strict consensus tree method.

Calls thresholdConsensus with threshold=1: only internal branches present in all trees are kept.

Author
Nicolas Galtier
Parameters
vecTrVector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNamesTell whether we should check the trees first.

Definition at line 1088 of file TreeTools.cpp.

Referenced by ~TreeTools().

TreeTemplate< Node > * TreeTools::thresholdConsensus ( const std::vector< Tree * > &  vecTr,
double  threshold,
bool  checkNames = true 
)
throw (Exception
)
static

General greedy consensus tree method.

Calculates the consensus tree of a set of trees defined from the number of occurrences of bipartitions. Bipartitions are considered in decreasing score order. A bipartition is included if it is compatible with all previously included bipartitions, and if its score is higher than a threshold.

Author
Nicolas Galtier
Parameters
vecTrVector of input trees (must share a common set of leaves - checked if checkNames is true)
thresholdMinimal acceptable score =number of occurrence of a bipartition/number of trees (0.<=threshold<=1.)
checkNamesTell whether we should check the trees first.

Definition at line 1022 of file TreeTools.cpp.

References bpp::BipartitionList::areCompatible(), bpp::BipartitionList::deleteBipartition(), bpp::BipartitionList::getNumberOfBipartitions(), bpp::BipartitionList::getPartitionSize(), bpp::VectorTools::haveSameElements(), and bpp::BipartitionList::toTree().

Referenced by ~TreeTools().

string TreeTools::treeToParenthesis ( const Tree tree,
bool  writeId = false 
)
static

Get the parenthesis description of a tree.

Parameters
treeThe tree to convert.
writeIdTells if node ids must be printed. This will overwrite bootstrap values if there are ones. Leaves id will be added to the leave names, separated by a '_' character.
Returns
A string in the parenthesis format.

Definition at line 330 of file TreeTools.cpp.

References bpp::Tree::getNodeName(), bpp::Tree::getRootId(), bpp::Tree::getSonsId(), and bpp::Tree::isLeaf().

Referenced by bpp::NexusIOTree::write_(), bpp::Newick::write_(), and ~TreeTools().

string TreeTools::treeToParenthesis ( const Tree tree,
bool  bootstrap,
const std::string &  propertyName 
)
static

Get the parenthesis description of a tree.

Parameters
treeThe tree to convert.
bootstrapTell is bootstrap values must be writen. If so, the content of the property with name TreeTools::BOOTSTRAP will be written as bootstrap value. The property should be a Number<double> object. Otherwise, the content of the property with name 'propertyName' will be written. In this later case, the property should be a String object.
propertyNameThe name of the property to use. Only used if bootstrap = false.
Returns
A string in the parenthesis format.

Definition at line 362 of file TreeTools.cpp.

References bpp::Tree::getBranchProperty(), bpp::Tree::getNodeName(), bpp::Tree::getRootId(), bpp::Tree::getSonsId(), bpp::Tree::hasBranchProperty(), and bpp::Tree::isLeaf().

Member Data Documentation


The documentation for this class was generated from the following files: