src/clustal/muscle_tree.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <ctype.h>
#include "util.h"
#include "log.h"
#include "muscle_tree.h"

Include dependency graph for muscle_tree.c:

Enumerations
enum	NEWICK_TOKEN_TYPE { NTT_Unknown, NTT_Lparen, NTT_Rparen, NTT_Colon, NTT_Comma, NTT_Semicolon, NTT_String, NTT_SingleQuotedString, NTT_DoubleQuotedString, NTT_Comment }
Functions
uint	AppendBranch (tree_t *tree, uint uExistingLeafIndex)
uint	GetNeighbor (uint uNodeIndex, uint uNeighborSubscript, tree_t *tree)
uint	GetLeft (uint uNodeIndex, tree_t *tree)
uint	GetRight (uint uNodeIndex, tree_t *tree)
uint	GetLeafId (uint uNodeIndex, tree_t *tree)
char *	GetLeafName (unsigned uNodeIndex, tree_t *tree)
uint	FirstDepthFirstNode (tree_t *tree)
	returns first leaf node for a depth-first traversal of tree
uint	NextDepthFirstNode (uint uNodeIndex, tree_t *tree)
	returns next leaf node index for depth-first traversal of tree
bool	IsRooted (tree_t *tree)
	check if tree is a rooted tree
void	FreeMuscleTree (tree_t *tree)
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)
bool	IsLeaf (uint uNodeIndex, tree_t *tree)
	check if given node is a leaf node
bool	IsRoot (uint uNodeIndex, tree_t *tree)
uint	GetNeighborCount (uint uNodeIndex, tree_t *tree)
uint	GetParent (unsigned uNodeIndex, tree_t *tree)
double	GetEdgeLength (uint uNodeIndex1, uint uNodeIndex2, tree_t *tree)
void	TreeValidate (tree_t *tree)
int	MuscleTreeFromFile (tree_t tree, char ftree)
void	SetLeafName (unsigned uNodeIndex, const char ptrName, tree_t tree)
void	LogTree (tree_t tree, FILE fp)
uint	GetLeafCount (tree_t *tree)
uint	GetNodeCount (tree_t *tree)
void	SetLeafId (tree_t *tree, uint uNodeIndex, uint uId)
uint	GetRootNodeIndex (tree_t *tree)
uint	LeafIndexToNodeIndex (uint uLeafIndex, tree_t *prTree)
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.

Enumeration Type Documentation

enum NEWICK_TOKEN_TYPE

Enumerator:

NTT_Unknown
NTT_Lparen
NTT_Rparen
NTT_Colon
NTT_Comma
NTT_Semicolon
NTT_String
NTT_SingleQuotedString
NTT_DoubleQuotedString
NTT_Comment

Function Documentation

uint AppendBranch	(	tree_t *	tree,
		uint	uExistingLeafIndex
	)

Append a new branch. This adds two new nodes and joins them to an existing leaf node. Return value is k, new nodes have indexes k and k+1 respectively.

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 GetNeighbor	(	uint	uNodeIndex,
		uint	uNeighborSubscript,
		tree_t *	tree
	)

uint GetNeighborCount	(	uint	uNodeIndex,
		tree_t *	tree
	)

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 SetLeafName	(	unsigned	uNodeIndex,
		const char *	ptrName,
		tree_t *	tree
	)

void TreeValidate ( tree_t * tree )

src/clustal/muscle_tree.c File Reference

Enumerations

Functions

Enumeration Type Documentation

Function Documentation