src/clustal/muscle_tree.h File Reference

#include <stdio.h>
#include "util.h"

Include dependency graph for muscle_tree.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	tree_t
	guide-tree structure More...
Typedefs
typedef unsigned int	uint
Functions
void	MuscleTreeCreate (tree_t tree, uint uLeafCount, uint uRoot, const uint Left, const uint Right, const float LeftLength, const float RightLength, const uint LeafIds, char **LeafNames)
	create a muscle tree
void	MuscleTreeToFile (FILE fp, tree_t tree)
	write a muscle tree to a file in newick format (distances and all names)
int	MuscleTreeFromFile (tree_t tree, char ftree)
void	FreeMuscleTree (tree_t *tree)
void	LogTree (tree_t tree, FILE fp)
bool	IsRooted (tree_t *tree)
	check if tree is a rooted tree
uint	GetNodeCount (tree_t *tree)
uint	GetLeafCount (tree_t *tree)
uint	FirstDepthFirstNode (tree_t *tree)
	returns first leaf node for a depth-first traversal of tree
uint	NextDepthFirstNode (uint nodeindex, tree_t *tree)
	returns next leaf node index for depth-first traversal of tree
bool	IsLeaf (uint nodeindex, tree_t *tree)
	check if given node is a leaf node
void	SetLeafId (tree_t *tree, uint uNodeIndex, uint uId)
uint	GetLeafId (uint nodeindex, tree_t *tree)
char *	GetLeafName (unsigned uNodeIndex, tree_t *tree)
uint	GetLeft (uint nodeindex, tree_t *tree)
uint	GetRight (uint nodeindex, tree_t *tree)
uint	GetRootNodeIndex (tree_t *tree)
bool	IsRoot (uint uNodeIndex, tree_t *tree)
uint	GetParent (unsigned uNodeIndex, tree_t *tree)
double	GetEdgeLength (uint uNodeIndex1, uint uNodeIndex2, tree_t *tree)
uint	LeafIndexToNodeIndex (uint uLeafIndex, tree_t *prTree)
void	AppendTree (tree_t prDstTree, uint uDstTreeNodeIndex, tree_t prSrcTree)
	Append a (source) tree to a (dest) tree to a given node which will be replaced. All other nodes in that tree will stay the same.
void	TreeValidate (tree_t *tree)

Typedef Documentation

typedef unsigned int uint

Function Documentation

void AppendTree	(	tree_t *	prDstTree,
		uint	uDstTreeReplaceNodeIndex,
		tree_t *	prSrcTree
	)

Append a (source) tree to a (dest) tree to a given node which will be replaced. All other nodes in that tree will stay the same.

Parameters:

`[out]`	prDstTree	The tree to append to
`[in]`	uDstTreeReplaceNodeIndex	Dest tree node to which source tree will be appended
`[in]`	prSrcTree	The tree to append

Note:: No nodes inside prDstTree will change except uDstTreeReplaceNodeIndex

Warning:: : Function won't check or touch the m_Ids/leaf-indices! That means if you want to join two trees with leaf indices 1-10 and 1-10 your m_Ids/leaf-indices won't be unique anymore and the association between your sequences and the tree are broken. Make sure m_Ids are unique before calling me.

The easiest would have been to do this by recursively calling AppendBranch() (after adding uSrcTreeNodeIndex as extra argument to this function). But recursion is evil. Yet another version would be to setup all the data and call MuscleTreeCreate() to create a third tree, which seems complicated and wasteful. The approach taken here is the following: increase dest tree memory, copy over each src tree node data and update the indices and counters. This is tricky and has a lot of potential for bugs if tree interface is changed (and even if it isn't).

uint FirstDepthFirstNode ( tree_t * tree )

returns first leaf node for a depth-first traversal of tree

Parameters:

[in] tree tree to traverse

Returns:: node index of first leaf node for depth-first traversal

Note:: called FirstDepthFirstNode in Muscle3.7

void FreeMuscleTree ( tree_t * tree )

double GetEdgeLength	(	uint	uNodeIndex1,
		uint	uNodeIndex2,
		tree_t *	tree
	)

uint GetLeafCount ( tree_t * tree )

replaces m_uLeafCount

uint GetLeafId	(	uint	uNodeIndex,
		tree_t *	tree
	)

Parameters:

`[in]`	uNodeIndex	node to examine
`[in]`	tree	tree to examine

Returns:: leaf id of current node

char* GetLeafName	(	unsigned	uNodeIndex,
		tree_t *	tree
	)

Note:: originally called GetLeafName

uint GetLeft	(	uint	uNodeIndex,
		tree_t *	tree
	)

Parameters:

`[in]`	uNodeIndex	node to examine
`[in]`	tree	tree to examine

Returns:: id of left node

Note:: called GetRight in Muscle3.7

uint GetNodeCount ( tree_t * tree )

uint GetParent	(	unsigned	uNodeIndex,
		tree_t *	tree
	)

uint GetRight	(	uint	uNodeIndex,
		tree_t *	tree
	)

Parameters:

`[in]`	uNodeIndex	node to examine
`[in]`	tree	tree to examine

Returns:: id of right node

Note:: called GetRight in Muscle3.7

uint GetRootNodeIndex ( tree_t * tree )

bool IsLeaf	(	uint	uNodeIndex,
		tree_t *	tree
	)

check if given node is a leaf node

Parameters:

`[in]`	uNodeIndex	the node index
	tree	the tree

Returns:: TRUE if given node is a leaf, FALSE otherwise

Note:: called IsLeaf in Muscle3.7. See tree.h in original code

bool IsRoot	(	uint	uNodeIndex,
		tree_t *	tree
	)

bool IsRooted ( tree_t * tree )

check if tree is a rooted tree

Parameters:

[in] tree tree to check

Returns:: TRUE if given tree is rooted, FALSE otherwise

uint LeafIndexToNodeIndex	(	uint	uLeafIndex,
		tree_t *	prTree
	)

Note:: avoid usage if you want to iterate over all indices, because this will be slow

void LogTree	(	tree_t *	tree,
		FILE *	fp
	)

Debug output

LogMe in phy.cpp

void MuscleTreeCreate	(	tree_t *	tree,
		uint	uLeafCount,
		uint	uRoot,
		const uint *	Left,
		const uint *	Right,
		const float *	LeftLength,
		const float *	RightLength,
		const uint *	LeafIds,
		char **	LeafNames
	)

create a muscle tree

Note:: Original comment in Muscle code: "Create rooted tree from a vector description. Node indexes are 0..N-1 for leaves, N..2N-2 for internal nodes. Vector subscripts are i-N and have values for internal nodes only, but those values are node indexes 0..2N-2. So e.g. if N=6 and Left[2]=1, this means that the third internal node (node index 8) has the second leaf (node index 1) as its left child. uRoot gives the vector subscript of the root, so add N to get the node index."

Parameters:

`[out]`	tree	newly created tree
`[in]`	uLeafCount	number of leaf nodes
`[in]`	uRoot	Internal node index of root node
`[in]`	Left	Node index of left sibling of an internal node. Index range: 0--uLeafCount-1
`[in]`	Right	Node index of right sibling of an internal node. Index range: 0--uLeafCount-1
`[in]`	LeftLength	Branch length of left branch of an internal node. Index range: 0--uLeafCount-1
`[in]`	RightLength	Branch length of right branch of an internal node. Index range: 0--uLeafCount-1
`[in]`	LeafIds	Leaf id. Index range: 0--uLeafCount
`[in]`	LeafNames	Leaf label. Index range: 0--uLeafCount

int MuscleTreeFromFile	(	tree_t *	tree,
		char *	ftree
	)

Note:: see phyfromfile.cpp in Muscle3.7. Tree has to be a pointer to an already allocated tree structure.

return non-Zero on failure

leafids will not be set here (FIXME:CHECK if true)

void MuscleTreeToFile	(	FILE *	fp,
		tree_t *	tree
	)

write a muscle tree to a file in newick format (distances and all names)

Parameters:

`[in]`	tree	tree to write
`[out]`	fp	filepointer to write to2

uint NextDepthFirstNode	(	uint	uNodeIndex,
		tree_t *	tree
	)

returns next leaf node index for depth-first traversal of tree

Parameters:

`[in]`	tree	tree to traverse
`[in]`	uNodeIndex	Current node index

Returns:: node index of next leaf node during depth-first traversal

Note:: called NextDepthFirstNode in Muscle3.7

void SetLeafId	(	tree_t *	tree,
		uint	uNodeIndex,
		uint	uId
	)

void TreeValidate ( tree_t * tree )

src/clustal/muscle_tree.h File Reference

Data Structures

Typedefs

Functions

Typedef Documentation

Function Documentation