Generic utilitary methods dealing with trees. More...

#include <Bpp/Phyl/Tree/TreeTools.h>

Collaboration diagram for bpp::TreeTools:

Classes
struct	Moments_

Public Member Functions
	TreeTools ()

virtual	~TreeTools ()

Static Public Member Functions
static std::unique_ptr< Tree >	MRP (const std::vector< std::unique_ptr< Tree > > &vecTr)
	Matrix Representation Parsimony supertree method. More...

static void	computeBootstrapValues (Tree &tree, const std::vector< std::unique_ptr< 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 std::unique_ptr< Tree >	MRPMultilabel (const std::vector< std::unique_ptr< Tree > > &vecTr)
	Matrix Representation Parsimony supertree method for multilabel trees. More...

Retrieve topology information
static std::vector< int >	getLeavesId (const Tree &tree, int nodeId)
	Retrieve all leaves from a subtree. More...

static void	getLeavesId (const Tree &tree, int nodeId, std::vector< int > &leaves)
	Retrieve all leaves from a subtree. More...

static size_t	getNumberOfLeaves (const Tree &tree, int nodeId)
	Count the number of leaves from a subtree. More...

static int	getLeafId (const Tree &tree, int nodeId, const std::string &name)
	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)
	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)
	Get a vector of ancestor nodes between to nodes. More...

static std::vector< int >	getAncestors (const Tree &tree, int nodeId)
	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)
	Get the id of the last common ancestors of all specified nodes. More...

static size_t	getDepth (const Tree &tree, int nodeId)
	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)
	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)
	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)
	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)
	Get the parenthesis description of a subtree. More...

static std::string	nodeToParenthesis (const Tree &tree, int nodeId, bool bootstrap, const std::string &propertyName)
	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)
	Retrieve all nodes ids nodes from a subtree. More...

static void	getNodesId (const Tree &tree, int nodeId, std::vector< int > &nodes)
	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)
	Check if the ids are uniques. More...

Topology methods
static std::unique_ptr< VectorSiteContainer >	MRPEncode (const std::vector< std::unique_ptr< Tree > > &vecTr)
	Creates a sequence data set corresponding to the Matrix Representation of the input trees. More...

static std::unique_ptr< VectorSiteContainer >	MRPEncodeMultilabel (const std::vector< std::unique_ptr< 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)
	Calculates the Robinson-Foulds topological distance between two trees. More...

static std::unique_ptr< BipartitionList >	bipartitionOccurrences (const std::vector< std::unique_ptr< Tree > > &vecTr, std::vector< size_t > &bipScore)
	Counts the total number of occurrences of every bipartition from the input trees. More...

static std::unique_ptr< TreeTemplate< Node > >	thresholdConsensus (const std::vector< std::unique_ptr< Tree > > &vecTr, double threshold, bool checkNames=true)
	General greedy consensus tree method. More...

static std::unique_ptr< TreeTemplate< Node > >	fullyResolvedConsensus (const std::vector< std::unique_ptr< Tree > > &vecTr, bool checkNames=true)
	Fully-resolved greedy consensus tree method. More...

static std::unique_ptr< TreeTemplate< Node > >	majorityConsensus (const std::vector< std::unique_ptr< Tree > > &vecTr, bool checkNames=true)
	Majority consensus tree method. More...

static std::unique_ptr< TreeTemplate< Node > >	strictConsensus (const std::vector< std::unique_ptr< Tree > > &vecTr, bool checkNames=true)
	Strict consensus tree method. More...

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)

Act on branch lengths.
static Vdouble	getBranchLengths (const Tree &tree, int nodeId)
	Get all the branch lengths of a subtree. More...

static double	getTotalLength (const Tree &tree, int nodeId, bool includeAncestor=true)
	Get the total length (sum of all branch lengths) of a subtree. More...

static void	setBranchLengths (Tree &tree, int nodeId, double brLen)
	Set all the branch lengths of a subtree. More...

static void	setVoidBranchLengths (Tree &tree, int nodeId, double brLen)
	Give a length to branches that don't have one in a subtree. More...

static void	scaleTree (Tree &tree, int nodeId, double factor)
	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)
	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 std::unique_ptr< DistanceMatrix >	getDistanceMatrix (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)

static void	computeBranchLengthsGrafen (Tree &tree, int nodeId, double power, double total, double &height, double &heightRaised)

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 30 of file TreeTools.h.

Constructor & Destructor Documentation

◆ TreeTools()

bpp::TreeTools::TreeTools ( )

inline

Definition at line 33 of file TreeTools.h.

◆ ~TreeTools()

virtual bpp::TreeTools::~TreeTools ( )

inlinevirtual

Definition at line 34 of file TreeTools.h.

Member Function Documentation

◆ bestRootPosition_()

double TreeTools::bestRootPosition_	(	Tree &	tree,
		int	nodeId1,
		int	nodeId2,
		double	length
	)

staticprivate

Definition at line 1169 of file TreeTools.cpp.

References bpp::TreeTools::Moments_::N, statFromNode_(), and bpp::TreeTools::Moments_::sum.

Referenced by constrainedMidPointRooting().

◆ bipartitionOccurrences()

unique_ptr< BipartitionList > TreeTools::bipartitionOccurrences	(	const std::vector< std::unique_ptr< 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

vecTr	Vector of input trees (must share a common set of leaves - not checked in this function)
bipScore	Output as the numbers of occurrences of the returned distinct bipartitions

Returns: A BipartitionList object including only distinct bipartitions

Definition at line 907 of file TreeTools.cpp.

References bpp::BipartitionTools::mergeBipartitionLists().

Referenced by computeBootstrapValues(), and thresholdConsensus().

◆ checkIds()

bool TreeTools::checkIds	(	const Tree &	tree,
		bool	throwException
	)

static

Check if the ids are uniques.

Parameters

tree	The tree to check.
throwException	If set to true, the function throws qn exception if a duplicated is found.

Returns: true if the tree has unique ids.

Definition at line 746 of file TreeTools.cpp.

References bpp::Tree::getNodesId(), and bpp::TextTools::toString().

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

◆ computeBootstrapValues()

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

static

Compute bootstrap values.

Parameters

tree	Input tree. the BOOTSTRAP branch property of the tree will be modified if it already exists.
vecTr	A list of trees to compare to 'tree'.
verbose	Tell if a progress bar should be displayed.
format	The output format of the tree.

Definition at line 1066 of file TreeTools.cpp.

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

◆ computeBranchLengthsGrafen() [1/2]

void TreeTools::computeBranchLengthsGrafen	(	Tree &	tree,
		double	power = `1`,
		bool	init = `true`
	)

static

Compute branch lengths using Grafen's method.

The 'height' of each node is divided 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

tree	The tree to use.
power	The rho parameter.
init	Tell if the height must be initialized by calling the initBranchLengthsGrafen() method. Otherwise use branch lengths.

Exceptions

NodeException If init=false and one branch length is lacking.

Definition at line 583 of file TreeTools.cpp.

References computeBranchLengthsGrafen(), getHeight(), bpp::Tree::getRootId(), and initBranchLengthsGrafen().

Referenced by computeBranchLengthsGrafen(), and bpp::LegacyPhylogeneticsApplicationTools::getTrees().

◆ computeBranchLengthsGrafen() [2/2]

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

staticprivate

Definition at line 549 of file TreeTools.cpp.

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

◆ constrainedMidPointRooting()

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

tree	The 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 1147 of file TreeTools.cpp.

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

Referenced by bpp::LegacyPhylogeneticsApplicationTools::getTrees().

◆ convertToClockTree()

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 height 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

tree	The tree to use.
nodeId	The node defining the subtree.
noneg	Tell if the correction for non negative branch lengths must be used.

Returns: The modified height of the node.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If one branch length is lacking.

Definition at line 598 of file TreeTools.cpp.

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

Referenced by convertToClockTree(), and bpp::LegacyPhylogeneticsApplicationTools::getTrees().

◆ convertToClockTree2()

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

tree	The tree to use.
nodeId	The node defining the subtree.

Returns: The modified height of the node.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If one branch length is lacking.

Definition at line 633 of file TreeTools.cpp.

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

Referenced by convertToClockTree2().

◆ fullyResolvedConsensus()

unique_ptr< TreeTemplate< Node > > TreeTools::fullyResolvedConsensus	(	const std::vector< std::unique_ptr< 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

vecTr	Vector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNames	Tell whether we should check the trees first.

Definition at line 1018 of file TreeTools.cpp.

References thresholdConsensus().

◆ getAncestors()

vector< int > TreeTools::getAncestors	(	const Tree &	tree,
		int	nodeId
	)

static

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

Parameters

tree	The tree to use.
nodeId	The id of node defining the subtree.

Returns: The list of ancestors ids.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 1100 of file TreeTools.cpp.

References bpp::Tree::getFatherId(), and bpp::Tree::hasFather().

Referenced by getLastCommonAncestor().

◆ getBranchLengths()

Vdouble TreeTools::getBranchLengths	(	const Tree &	tree,
		int	nodeId
	)

static

Get all the branch lengths of a subtree.

Parameters

tree	The tree.
nodeId	The node defining the subtree.

Returns: A vector with all branch lengths.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If a branch length is lacking.

Definition at line 438 of file TreeTools.cpp.

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

Referenced by getBranchLengths().

◆ getDepth()

size_t TreeTools::getDepth	(	const Tree &	tree,
		int	nodeId
	)

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

tree	The tree.
nodeId	The id of node defining the subtree.

Returns: The depth of the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 137 of file TreeTools.cpp.

References getDepth(), bpp::Tree::getSonsId(), and bpp::Tree::hasNode().

Referenced by getDepth().

◆ getDepths()

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

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

tree	The tree.
nodeId	The id of node defining the subtree.
depths	The map that will contain all the depths of the nodes, with node ids as keys.

Returns: The depth of the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 154 of file TreeTools.cpp.

References getDepths(), bpp::Tree::getSonsId(), and bpp::Tree::hasNode().

Referenced by getDepths().

◆ getDistanceBetweenAnyTwoNodes()

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

tree	The tree to consider.
nodeId1	First node id.
nodeId2	Second node id.

Returns: The sum of all branch lengths between the two nodes.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 421 of file TreeTools.cpp.

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

Referenced by getDistanceMatrix(), and midpointRooting().

◆ getDistanceMatrix()

std::unique_ptr< 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

tree	The tree to use.

Returns: The distance matrix computed from tree.

Definition at line 666 of file TreeTools.cpp.

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

Referenced by midpointRooting().

◆ getHeight()

double TreeTools::getHeight	(	const Tree &	tree,
		int	nodeId
	)

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

tree	The tree.
nodeId	The id of node defining the subtree.

Returns: The height of the subtree.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If a branch length is lacking.

Definition at line 172 of file TreeTools.cpp.

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

Referenced by computeBranchLengthsGrafen(), getHeight(), and bpp::LegacyPhylogeneticsApplicationTools::getTrees().

◆ getHeights()

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

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

tree	The tree.
nodeId	The id of node defining the subtree.
heights	The map that will contain all the heights of the nodes, with node ids as keys.

Returns: The height of the subtree.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If a branch length is lacking.

Definition at line 194 of file TreeTools.cpp.

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

Referenced by getHeights().

◆ getLastCommonAncestor()

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

static

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

Nodes id need not correspond to leaves.

Author: Simon Carrignon

Parameters

tree	The tree to use.
nodeIds	The ids of the input nodes.

Exceptions

NodeNotFoundException If at least of of input node is not found.

Definition at line 1114 of file TreeTools.cpp.

References count(), getAncestors(), and bpp::Tree::getRootId().

◆ getLeafId()

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

static

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

Parameters

tree	The tree
nodeId	The id of node defining the subtree.
name	The name of the node.

Returns: The id of the node.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 83 of file TreeTools.cpp.

References searchLeaf().

◆ getLeavesId() [1/2]

vector< int > TreeTools::getLeavesId	(	const Tree &	tree,
		int	nodeId
	)

static

Retrieve all leaves from a subtree.

Parameters

tree	The tree
nodeId	The id of node defining the subtree.

Returns: A vector with the ids of all leaves in the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 41 of file TreeTools.cpp.

References getLeavesId().

Referenced by getLeavesId().

◆ getLeavesId() [2/2]

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

static

Retrieve all leaves from a subtree.

Parameters

tree	The tree
nodeId	The id of node defining the subtree.
leaves	A vector with the ids of all leaves in the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 48 of file TreeTools.cpp.

References getLeavesId(), bpp::Tree::getSonsId(), bpp::Tree::hasNode(), and bpp::Tree::isLeaf().

◆ getMaxId()

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

static

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

This is a recursive method.

Parameters

tree	The tree to check.
id	The 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 715 of file TreeTools.cpp.

References getMaxId(), and bpp::Tree::getSonsId().

Referenced by getMaxId().

◆ getMPNUId()

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

tree	The tree to check.
id	The 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 730 of file TreeTools.cpp.

References getNodesId().

Referenced by bpp::TreeTemplate< N >::getNextId(), and bpp::TreeTemplateTools::midRoot().

◆ getNodesId() [1/2]

vector< int > TreeTools::getNodesId	(	const Tree &	tree,
		int	nodeId
	)

static

Retrieve all nodes ids nodes from a subtree.

Parameters

tree	The tree
nodeId	The id of the node that defines the subtree.

Returns: A vector of ids of each node in the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 116 of file TreeTools.cpp.

References getNodesId().

Referenced by getMPNUId(), getNodesId(), bpp::RNonHomogeneousMixedTreeLikelihood::init(), scaleTree(), setBranchLengths(), and setVoidBranchLengths().

◆ getNodesId() [2/2]

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

static

Retrieve all nodes ids from a subtree.

Parameters

tree	The tree
nodeId	The id of the node that defines the subtree.
nodes	A vector of ids of each node in the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 123 of file TreeTools.cpp.

References getNodesId(), bpp::Tree::getSonsId(), and bpp::Tree::hasNode().

◆ getNumberOfLeaves()

size_t TreeTools::getNumberOfLeaves	(	const Tree &	tree,
		int	nodeId
	)

static

Count the number of leaves from a subtree.

Parameters

tree	The tree
nodeId	The id of node defining the subtree.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 63 of file TreeTools.cpp.

References getNumberOfLeaves(), bpp::Tree::getSonsId(), bpp::Tree::hasNode(), and bpp::Tree::isLeaf().

Referenced by bpp::LabelCollapsedNodesTreeDrawingListener::afterDrawNode(), and getNumberOfLeaves().

◆ getPathBetweenAnyTwoNodes()

vector< int > TreeTools::getPathBetweenAnyTwoNodes	(	const Tree &	tree,
		int	nodeId1,
		int	nodeId2,
		bool	includeAncestor = `true`
	)

static

Get a vector of ancestor nodes between to nodes.

Parameters

tree	The tree to use.
nodeId1	Id of first node.
nodeId2	Id of second node.
includeAncestor	Tell if the common ancestor must be included in the vector.

Returns: A vector of ancestor nodes ids.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 368 of file TreeTools.cpp.

References bpp::Tree::getFatherId(), bpp::Tree::hasFather(), and bpp::Tree::hasNode().

Referenced by getDistanceBetweenAnyTwoNodes().

◆ getTotalLength()

double TreeTools::getTotalLength	(	const Tree &	tree,
		int	nodeId,
		bool	includeAncestor = `true`
	)

static

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

Parameters

tree	The tree.
nodeId	The node defining the subtree.
includeAncestor	Tell 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

NodeNotFoundException	If the node is not found.
NodeException	If a branch length is lacking.

Definition at line 461 of file TreeTools.cpp.

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

Referenced by getTotalLength().

◆ haveSameTopology()

bool TreeTools::haveSameTopology	(	const Tree &	tr1,
		const Tree &	tr2
	)

static

Tells whether two trees have the same unrooted topology.

Author: Nicolas Galtier Note that the location of the root, if any, is ignored.

Definition at line 790 of file TreeTools.cpp.

References bpp::BipartitionTools::areIdentical(), bpp::Tree::getLeavesNames(), and bpp::VectorTools::haveSameElements().

◆ initBranchLengthsGrafen() [1/2]

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

tree The tree.

Definition at line 542 of file TreeTools.cpp.

References bpp::Tree::getRootId(), and initBranchLengthsGrafen().

Referenced by computeBranchLengthsGrafen(), and initBranchLengthsGrafen().

◆ initBranchLengthsGrafen() [2/2]

size_t TreeTools::initBranchLengthsGrafen	(	Tree &	tree,
		int	nodeId
	)

staticprivate

Definition at line 524 of file TreeTools.cpp.

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

◆ majorityConsensus()

unique_ptr< TreeTemplate< Node > > TreeTools::majorityConsensus	(	const std::vector< std::unique_ptr< 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

vecTr	Vector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNames	Tell whether we should check the trees first.

Definition at line 1025 of file TreeTools.cpp.

References thresholdConsensus().

◆ midpointRooting()

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

tree	The tree to (re)root.

Definition at line 683 of file TreeTools.cpp.

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

◆ MRP()

unique_ptr< Tree > TreeTools::MRP ( const std::vector< std::unique_ptr< 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

vecTr A vector of trees.

Returns: The MRP super tree.

Definition at line 1039 of file TreeTools.cpp.

References bpp::BioNJ::computeTree(), bpp::DistanceEstimation::getMatrix(), bpp::ApplicationTools::message, MRPEncode(), bpp::LegacyOptimizationTools::optimizeTreeNNI(), bpp::BioNJ::setDistanceMatrix(), and bpp::AbstractAgglomerativeDistanceMethod::tree().

◆ MRPEncode()

unique_ptr< VectorSiteContainer > TreeTools::MRPEncode ( const std::vector< std::unique_ptr< 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 764 of file TreeTools.cpp.

References bpp::BipartitionTools::MRPEncode().

Referenced by MRP(), and MRPMultilabel().

◆ MRPEncodeMultilabel()

unique_ptr< VectorSiteContainer > TreeTools::MRPEncodeMultilabel ( const std::vector< std::unique_ptr< 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 777 of file TreeTools.cpp.

References bpp::BipartitionTools::MRPEncodeMultilabel().

◆ MRPMultilabel()

unique_ptr< Tree > TreeTools::MRPMultilabel ( const std::vector< std::unique_ptr< 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

vecTr A vector of trees.

Returns: The MRP super tree.

Definition at line 1229 of file TreeTools.cpp.

References bpp::BioNJ::computeTree(), bpp::DistanceEstimation::getMatrix(), bpp::ApplicationTools::message, MRPEncode(), bpp::LegacyOptimizationTools::optimizeTreeNNI(), bpp::BioNJ::setDistanceMatrix(), and bpp::AbstractAgglomerativeDistanceMethod::tree().

◆ nodeToParenthesis() [1/2]

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

static

Get the parenthesis description of a subtree.

Parameters

tree	The tree
nodeId	The node defining the subtree.
bootstrap	Tell is bootstrap values must be written. 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.
propertyName	The name of the property to use. Only used if bootstrap = false.

Returns: A string in the parenthesis format.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 255 of file TreeTools.cpp.

References BOOTSTRAP, bpp::Tree::getBranchProperty(), bpp::Tree::getDistanceToFather(), bpp::Tree::getNodeName(), bpp::Tree::getSonsId(), bpp::Tree::hasBranchProperty(), bpp::Tree::hasDistanceToFather(), bpp::Tree::hasNode(), bpp::Tree::hasNoSon(), and nodeToParenthesis().

◆ nodeToParenthesis() [2/2]

string TreeTools::nodeToParenthesis	(	const Tree &	tree,
		int	nodeId,
		bool	writeId = `false`
	)

static

Get the parenthesis description of a subtree.

Parameters

tree	The tree
nodeId	The id of node defining the subtree.
writeId	Tells 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

NodeNotFoundException If the node is not found.

Definition at line 217 of file TreeTools.cpp.

References BOOTSTRAP, bpp::Tree::getBranchProperty(), bpp::Tree::getDistanceToFather(), bpp::Tree::getNodeName(), bpp::Tree::getSonsId(), bpp::Tree::hasBranchProperty(), bpp::Tree::hasDistanceToFather(), bpp::Tree::hasNode(), bpp::Tree::hasNoSon(), and nodeToParenthesis().

Referenced by nodeToParenthesis(), and treeToParenthesis().

◆ robinsonFouldsDistance()

int TreeTools::robinsonFouldsDistance	(	const Tree &	tr1,
		const Tree &	tr2,
		bool	checkNames = `true`,
		int *	missing_in_tr2 = `NULL`,
		int *	missing_in_tr1 = `NULL`
	)

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

tr1	First input tree.
tr2	Second input tree.
missing_in_tr2	Output as the number of bipartitions occurring in the first tree but not the second
missing_in_tr1	Output as the number of bipartitions occurring in the second tree but not the first
checkNames	Tell whether we should check the trees first.

Returns: Robinson-Foulds distance = *missing_in_tr1 + *missing_in_tr2

Exceptions

Exception If checkNames is set to true and trees do not share the same leaves names.

Definition at line 841 of file TreeTools.cpp.

References bpp::BipartitionTools::areIdentical(), bpp::Tree::getLeavesNames(), and bpp::VectorTools::haveSameElements().

Referenced by bpp::OptimizationTools::buildDistanceTree().

◆ scaleTree()

void TreeTools::scaleTree	(	Tree &	tree,
		int	nodeId,
		double	factor
	)

static

Scale a given tree.

Multiply all branch lengths by a given factor.

Parameters

tree	The tree.
nodeId	The node defining the subtree.
factor	The factor to multiply all branch lengths with.

Exceptions

NodeNotFoundException	If the node is not found.
NodeException	If a branch length is lacking.

Definition at line 505 of file TreeTools.cpp.

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

Referenced by convertToClockTree2().

◆ searchLeaf()

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

static

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

Parameters

tree	The tree
nodeId	The id of node defining the subtree.
name	The name of the node.
id	The id of the node.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 97 of file TreeTools.cpp.

References bpp::Tree::getNodeName(), bpp::Tree::hasNoSon(), and searchLeaf().

Referenced by getLeafId(), and searchLeaf().

◆ setBranchLengths()

void TreeTools::setBranchLengths	(	Tree &	tree,
		int	nodeId,
		double	brLen
	)

static

Set all the branch lengths of a subtree.

Parameters

tree	The tree.
nodeId	The node defining the subtree.
brLen	The branch length to apply.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 478 of file TreeTools.cpp.

References getNodesId(), bpp::Tree::hasNode(), and bpp::Tree::setDistanceToFather().

◆ setVoidBranchLengths()

void TreeTools::setVoidBranchLengths	(	Tree &	tree,
		int	nodeId,
		double	brLen
	)

static

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

Parameters

tree	The tree.
nodeId	The node defining the subtree.
brLen	The branch length to apply.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 491 of file TreeTools.cpp.

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

◆ statFromNode_()

TreeTools::Moments_ TreeTools::statFromNode_	(	Tree &	tree,
		int	rootId
	)

staticprivate

Definition at line 1198 of file TreeTools.cpp.

References bpp::Tree::getDistanceToFather(), bpp::Tree::getSonsId(), bpp::Tree::isLeaf(), bpp::TreeTools::Moments_::N, bpp::TreeTools::Moments_::squaredSum, statFromNode_(), and bpp::TreeTools::Moments_::sum.

Referenced by bestRootPosition_(), and statFromNode_().

◆ strictConsensus()

unique_ptr< TreeTemplate< Node > > TreeTools::strictConsensus	(	const std::vector< std::unique_ptr< 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

vecTr	Vector of input trees (must share a common set of leaves - checked if checkNames is true)
checkNames	Tell whether we should check the trees first.

Definition at line 1032 of file TreeTools.cpp.

References thresholdConsensus().

◆ thresholdConsensus()

unique_ptr< TreeTemplate< Node > > TreeTools::thresholdConsensus	(	const std::vector< std::unique_ptr< Tree > > &	vecTr,
		double	threshold,
		bool	checkNames = `true`
	)

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

vecTr	Vector of input trees (must share a common set of leaves - checked if checkNames is true)
threshold	Minimal acceptable score =number of occurrence of a bipartition/number of trees (0.<=threshold<=1.)
checkNames	Tell whether we should check the trees first.

Definition at line 968 of file TreeTools.cpp.

References bipartitionOccurrences(), and bpp::VectorTools::haveSameElements().

Referenced by fullyResolvedConsensus(), majorityConsensus(), and strictConsensus().

◆ treeToParenthesis() [1/2]

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

static

Get the parenthesis description of a tree.

Parameters

tree	The tree to convert.
bootstrap	Tell is bootstrap values must be written. 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.
propertyName	The name of the property to use. Only used if bootstrap = false.

Returns: A string in the parenthesis format.

Definition at line 327 of file TreeTools.cpp.

References BOOTSTRAP, bpp::Tree::getBranchProperty(), bpp::Tree::getNodeName(), bpp::Tree::getRootId(), bpp::Tree::getSonsId(), bpp::Tree::hasBranchProperty(), bpp::Tree::hasNoSon(), and nodeToParenthesis().

◆ treeToParenthesis() [2/2]

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

static

Get the parenthesis description of a tree.

Parameters

tree	The tree to convert.
writeId	Tells 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 295 of file TreeTools.cpp.

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

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

Member Data Documentation

◆ BOOTSTRAP

const string TreeTools::BOOTSTRAP = "bootstrap"

static

Bootstrap tag.

Definition at line 684 of file TreeTools.h.

Referenced by bpp::BootstrapValuesTreeDrawingListener::afterDrawBranch(), computeBootstrapValues(), bpp::Node::getBootstrapValue(), bpp::Node::hasBootstrapValue(), bpp::Nhx::Nhx(), bpp::TreeTemplateTools::nodeToParenthesis(), nodeToParenthesis(), bpp::TreeTemplateTools::parenthesisToNode(), treeToParenthesis(), and bpp::TreeTemplateTools::treeToParenthesis().

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

Bpp/Phyl/Tree/TreeTools.h
Bpp/Phyl/Tree/TreeTools.cpp

Classes

Public Member Functions

Static Public Member Functions

Some properties.

Act on branch lengths.

Detailed Description

Constructor & Destructor Documentation

◆ TreeTools()

◆ ~TreeTools()

Member Function Documentation

◆ bestRootPosition_()

◆ bipartitionOccurrences()

◆ checkIds()

◆ computeBootstrapValues()

◆ computeBranchLengthsGrafen() [1/2]

◆ computeBranchLengthsGrafen() [2/2]

◆ constrainedMidPointRooting()

◆ convertToClockTree()

◆ convertToClockTree2()

◆ fullyResolvedConsensus()

◆ getAncestors()

◆ getBranchLengths()

◆ getDepth()

◆ getDepths()

◆ getDistanceBetweenAnyTwoNodes()

◆ getDistanceMatrix()

◆ getHeight()

◆ getHeights()

◆ getLastCommonAncestor()

◆ getLeafId()

◆ getLeavesId() [1/2]

◆ getLeavesId() [2/2]

◆ getMaxId()

◆ getMPNUId()

◆ getNodesId() [1/2]

◆ getNodesId() [2/2]

◆ getNumberOfLeaves()

◆ getPathBetweenAnyTwoNodes()

◆ getTotalLength()

◆ haveSameTopology()

◆ initBranchLengthsGrafen() [1/2]

◆ initBranchLengthsGrafen() [2/2]

◆ majorityConsensus()

◆ midpointRooting()

◆ MRP()

◆ MRPEncode()

◆ MRPEncodeMultilabel()

◆ MRPMultilabel()

◆ nodeToParenthesis() [1/2]

◆ nodeToParenthesis() [2/2]

◆ robinsonFouldsDistance()

◆ scaleTree()

◆ searchLeaf()

◆ setBranchLengths()

◆ setVoidBranchLengths()

◆ statFromNode_()

◆ strictConsensus()

◆ thresholdConsensus()

◆ treeToParenthesis() [1/2]

◆ treeToParenthesis() [2/2]

Member Data Documentation

◆ BOOTSTRAP