Clustal Omega 1.2.4
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

◆ 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

◆ AppendBranch()

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.

◆ AppendTree()

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).

◆ FirstDepthFirstNode()

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

◆ FreeMuscleTree()

void FreeMuscleTree ( tree_t * tree)

◆ GetEdgeLength()

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

◆ GetLeafCount()

uint GetLeafCount ( tree_t * tree)

replaces m_uLeafCount

◆ GetLeafId()

uint GetLeafId ( uint uNodeIndex,
tree_t * tree )
Parameters
[in]uNodeIndexnode to examine
[in]treetree to examine
Returns
leaf id of current node

◆ GetLeafName()

char * GetLeafName ( unsigned uNodeIndex,
tree_t * tree )
Note
originally called GetLeafName

◆ GetLeft()

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

◆ GetNeighbor()

uint GetNeighbor ( uint uNodeIndex,
uint uNeighborSubscript,
tree_t * tree )

◆ GetNeighborCount()

uint GetNeighborCount ( uint uNodeIndex,
tree_t * tree )

◆ GetNodeCount()

uint GetNodeCount ( tree_t * tree)

◆ GetParent()

uint GetParent ( unsigned uNodeIndex,
tree_t * tree )

◆ GetRight()

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

◆ GetRootNodeIndex()

uint GetRootNodeIndex ( tree_t * tree)

◆ IsLeaf()

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

◆ IsRoot()

bool IsRoot ( uint uNodeIndex,
tree_t * tree )

◆ IsRooted()

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

◆ LeafIndexToNodeIndex()

uint LeafIndexToNodeIndex ( uint uLeafIndex,
tree_t * prTree )
Note
avoid usage if you want to iterate over all indices, because this will be slow

◆ LogTree()

void LogTree ( tree_t * tree,
FILE * fp )

Debug output

LogMe in phy.cpp

◆ MuscleTreeCreate()

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

◆ MuscleTreeFromFile()

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)

◆ MuscleTreeToFile()

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

◆ NextDepthFirstNode()

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

◆ SetLeafId()

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

◆ SetLeafName()

void SetLeafName ( unsigned uNodeIndex,
const char * ptrName,
tree_t * tree )

◆ TreeValidate()

void TreeValidate ( tree_t * tree)