Skip to content

API Reference (Tree Module)

Jump to bottom
Alexey Kozlov edited this page Jul 31, 2019 · 9 revisions

Tree rearrangements

Additional utilities

Data structures

List of functions

pll_utree_TBR
int pll_utree_tbr(pll_unode_t * b_edge,
                  pll_tree_edge_t * r_edge,
                  pll_tree_rollback_t * rollback_info);

Applies a TBR move (tree bisection and reconnection) to the tree by bisecting the tree at b_edge and reconnect the edges r_edge.parent and r_edge.child. If rollback_info is not null, it fills the structure such that the move can be undone.

TBR move 1

1 Bisect tree. p_edge and the adjacent edges are removed. The result of this operation is 2 unconnected trees.

TBR move 2

2 Reconnect tree. r_edge.parent and r_edge.child are joint together.

TBR move 3

3 The result is a new tree. Nodes and branches were rearranged for clarity.

TBR move 3

pll_utree_SPR
int pll_utree_spr(pll_unode_t * p_edge,
                  pll_unode_t * r_edge,
                  pll_tree_rollback_t * rollback_info);

Applies a SPR move (subtree pruning and regrafting) to the tree by prunning p_edge and regrafting it into r_edge. If rollback_info is not null, it fills the structure such that the move can be undone.

SPR move 1

1 Prune subtree. p_edge is detached from the tree and the adjacent edges are joint together.

SPR move 2

2 Regraft subtree. The node is attached to r_edge.

SPR move 3

3 Rollback information.

SPR move rollback 1 SPR move rollback 2

pll_utree_NNI
int pll_utree_nni(pll_unode_t * edge,
                  int type,
                  pll_tree_rollback_t * rollback_info);

Applies a NNI move (nearest neighbor interchange) to the tree by interchanging the branch adjacent to edge with one of the branches at the complementary side.

NNI move 1

1 Adjacent branch to edge is interchange with a non-adjacent one according to type, that chooses between the 2 possible NNI moves across one branch.

NNI move 2

2 Rollback information.

NNI move rollback

pll_utree_traverse_apply
int pll_utree_traverse_apply(pll_unode_t * root,
                             int (*cb_pre_trav)(pll_unode_t *, void *),
                             int (*cb_post_trav)(pll_unode_t *, void *),
                             void *data);

Apply callback function by traversing the tree in pre- and post-order. Both callback functions are applied together while traversing the tree. cb_pre_trav will be applied in pre-order, and cb_post_trav in post-order. The callback functions contain two parameters. The first one, pll_utree_t * is the node where the function was called. The second one is the data void pointer, containing whatever information is required by the functions.

utree traverse apply 1

For the above topology, pll_utree_traverse_apply will traverse the tree as depicted in the following image:

utree traverse apply 2

The pre-order callback function, cb_pre_trav is called the first time each node is visited: {9,5,6,10,7,1,2,8,3,4}

utree traverse apply 3

The post-order callback function, cb_post_trav is called the last time each node is visited: {5,6,9,1,2,7,3,4,8,10}. In addition, cb_post_trav returns an integer value that determines whether the function should continue traversing, or it should stop.

utree traverse apply 4

If both functions are defined, the calls are still executed in the described order, so they will be called interleaved: {pre(9), pre(5), post(5), pre(6), post(6), post(9), pre(10), pre(7), pre(1), post(1), pre(2), post(2), post(7), pre(8), pre(3), post(3), pre(4), post(4), post(8), post(10)}

utree traverse apply 3

pll_utree_is_tip
inline int pll_utree_is_tip(pll_unode_t * node);

Returns true if node is a tip.

pll_utree_set_length
inline void pll_utree_set_length(pll_unode_t * edge,
                                 double length);

Sets the length of the edge node.

pll_utree_compute_lk
double pll_utree_compute_lk(pll_partition_t * partition,
                            pll_unode_t * tree,
                            unsigned int params_index,
                            unsigned int freqs_index,
                            int update_pmatrices,
                            int update_partials);

Computes the likelihood directly from a tree structure, rooted at tree without the need to build a traversal descriptor. The last 2 arguments, update_pmatrices and update_partials are flags that determine whether the p-matrices or conditional likelihood vectors should be recomputed.

pllmod_utree_serialize
pll_utree_t * pllmod_utree_serialize(pll_unode_t * tree, 
                                     unsigned int tip_count);

Serializes an unrooted tree structure such that it can be easily be shared between processes or saved into a binary file. Only node and branch fix-length attributes are saved, so for example tips/node names or data pointers are set to NULL.

Returns an array of 2*tip_count - 2 (i.e., the number of nodes), but all pointers are set to NULL, so keep in mind that you need to call pllmod_utree_expand before using the return value as a regular tree structure.

pllmod_utree_expand
pll_utree_t * pllmod_utree_expand(pll_unode_t * serialized_tree,
                                  unsigned int tip_count);

Expands a serialized unrooted tree structure into a functional tree. The input arguments are not changed.

Clone this wiki locally