Clustal Omega  1.2.1
Enumerations | Functions
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 More...
 
uint NextDepthFirstNode (uint uNodeIndex, tree_t *tree)
 returns next leaf node index for depth-first traversal of tree More...
 
bool IsRooted (tree_t *tree)
 check if tree is a rooted tree More...
 
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 More...
 
void MuscleTreeToFile (FILE *fp, tree_t *tree)
 write a muscle tree to a file in newick format (distances and all names) More...
 
bool IsLeaf (uint uNodeIndex, tree_t *tree)
 check if given node is a leaf node More...
 
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. More...
 

Enumeration Type Documentation

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]prDstTreeThe tree to append to
[in]uDstTreeReplaceNodeIndexDest tree node to which source tree will be appended
[in]prSrcTreeThe 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]treetree 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]uNodeIndexnode to examine
[in]treetree 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]uNodeIndexnode to examine
[in]treetree 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]uNodeIndexnode to examine
[in]treetree 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]uNodeIndexthe node index
treethe 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]treetree 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]treenewly created tree
[in]uLeafCountnumber of leaf nodes
[in]uRootInternal node index of root node
[in]LeftNode index of left sibling of an internal node. Index range: 0–uLeafCount-1
[in]RightNode index of right sibling of an internal node. Index range: 0–uLeafCount-1
[in]LeftLengthBranch length of left branch of an internal node. Index range: 0–uLeafCount-1
[in]RightLengthBranch length of right branch of an internal node. Index range: 0–uLeafCount-1
[in]LeafIdsLeaf id. Index range: 0–uLeafCount
[in]LeafNamesLeaf 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]treetree to write
[out]fpfilepointer to write to2
uint NextDepthFirstNode ( uint  uNodeIndex,
tree_t tree 
)

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

Parameters
[in]treetree to traverse
[in]uNodeIndexCurrent 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)