Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
120 lines (98 sloc) 4.76 KB
/* Phylogenetic trees.
*
* SRE, Tue May 2 13:54:30 2006 [St. Louis]
*/
#ifndef eslTREE_INCLUDED
#define eslTREE_INCLUDED
#include "esl_config.h"
#include "esl_dmatrix.h"
#include "esl_random.h"
/* Object: ESL_TREE
*
* All trees are represented as rooted trees, starting from
* node 0. For N taxa, there are N-1 internal nodes, numbered
* 0..N-2. Taxa on leaves are numbered 0..N-1, and represented
* in <left> and <right> as negative numbers.
*
*/
typedef struct {
int N; /* number of taxa */
/* (Mandatory) information for the internal nodes of a rooted tree.
* There are N-1 nodes, numbered 0..N-2, with the root at 0,
* so each array below is indexed [0..N-2].
* When an internal node has a left or right branch to a taxon,
* <left>/<right> are <= 0, negative <taxon #>; if they're to
* be used as array indices, flip their sign.
* There is no ambiguity between taxon 0/root node 0, because
* a taxon can't be a parent, and the root node can't be a child.
* For an unrooted tree, by convention, taxon 0 is the outgroup: T->left[0] = 0,
* and T->rd[0] = 0.0.
*/
int *parent; /* index of parent of node: values are 0..N-2; parent of root 0 = 0 */
int *left; /* index of left child: values are -(N-1)..0=taxa; 1..N-2=nodes */
int *right; /* index of right child: values are -(N-1)..0=taxa; 1..N-2=nodes */
double *ld; /* left branch length under node: values are >= 0 */
double *rd; /* right branch length under node: values are >= 0 */
/* in linkage trees, ld[x]=rd[x]= "height" (linkage value) of node, not branch lengths */
/* Derived (optional) information, that we can reconstruct if
* we need to from the mandatory info above.
*/
int *taxaparent; /* for taxa [0..N-1]: index of its parent node, 0..N-2. [esl_tree_SetTaxaParents()] */
int *cladesize; /* for nodes [0..N-2]: # taxa in this clade, 1..N [esl_tree_SetCladesizes()] */
/* Optional information */
char **taxonlabel; /* labels for taxa: [0..N-1] array of char strings */
char **nodelabel; /* labels for nodes: [0..N-2] array of char strings */
/* Tree mode options. */
int is_linkage_tree; /* TRUE if this is a linkage tree; if FALSE, it's an additive tree */
/* Tree output options. */
int show_unrooted; /* TRUE to output 'root' as a trifurcation (a la PHYLIP) */
int show_node_labels; /* TRUE to output labels for interior nodes */
int show_root_branchlength; /* TRUE to show 0.0 branch length to root node (a la TreeAlign) */
int show_branchlengths; /* TRUE to output branch lengths */
int show_quoted_labels; /* TRUE to output ALL labels as quoted labels */
int show_numeric_taxonlabels;/* TRUE to output taxa labels as their 0..N-1 indices if no other taxonlabel is present */
/* Memory allocation information, when growing a tree (on input, for example)
*/
int nalloc; /* current allocated # of taxa */
} ESL_TREE;
/* UPGMA, average-link, minimum-link, and maximum-link clustering are
* all implemented by one algorithm, cluster_engine(), in esl_tree.c.
* We define some flags (within the scope of the tree module) to
* control the behavior, as we call the algorithm engine from four
* different API functions.
*/
#define eslUPGMA 0
#define eslWPGMA 1
#define eslSINGLE_LINKAGE 2
#define eslCOMPLETE_LINKAGE 3
/* 1. The ESL_TREE object.
*/
extern ESL_TREE *esl_tree_Create(int ntaxa);
extern ESL_TREE *esl_tree_CreateGrowable(int nalloc);
extern ESL_TREE *esl_tree_CreateFromString(char *s);
extern int esl_tree_Grow(ESL_TREE *T);
extern int esl_tree_SetTaxaParents(ESL_TREE *T);
extern int esl_tree_SetCladesizes(ESL_TREE *T);
extern int esl_tree_SetTaxonlabels(ESL_TREE *T, char **names);
extern int esl_tree_RenumberNodes(ESL_TREE *T);
extern int esl_tree_VerifyUltrametric(ESL_TREE *T);
extern int esl_tree_Validate(ESL_TREE *T, char *errbuf);
extern void esl_tree_Destroy(ESL_TREE *T);
/* 2. Newick format i/o
*/
extern int esl_tree_WriteNewick(FILE *fp, ESL_TREE *T);
extern int esl_tree_ReadNewick(FILE *fp, char *errbuf, ESL_TREE **ret_T);
/* 3. Tree comparison algorithms.
*/
extern int esl_tree_Compare(ESL_TREE *T1, ESL_TREE *T2);
/* 4. Clustering algorithms for distance-based tree construction.
*/
extern int esl_tree_UPGMA(ESL_DMATRIX *D, ESL_TREE **ret_T);
extern int esl_tree_WPGMA(ESL_DMATRIX *D, ESL_TREE **ret_T);
extern int esl_tree_SingleLinkage(ESL_DMATRIX *D, ESL_TREE **ret_T);
extern int esl_tree_CompleteLinkage(ESL_DMATRIX *D, ESL_TREE **ret_T);
/* 5. Generating simulated trees.
*/
extern int esl_tree_Simulate(ESL_RANDOMNESS *r, int N, ESL_TREE **ret_T);
extern int esl_tree_ToDistanceMatrix(ESL_TREE *T, ESL_DMATRIX **ret_D);
#endif /*eslTREE_INCLUDED*/
You can’t perform that action at this time.