clearcut.h

   1
   2
   3
   4 /*
   5  * clearcut.h
   6  *
   7  * $Id$
   8  *
   9  *****************************************************************************
  10  *
  11  * Copyright (c) 2004,  Luke Sheneman
  12  * All rights reserved.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions
  16  * are met:
  17  *
  18  *  + Redistributions of source code must retain the above copyright
  19  *    notice, this list of conditions and the following disclaimer.
  20  *  + Redistributions in binary form must reproduce the above copyright
  21  *    notice, this list of conditions and the following disclaimer in
  22  *    the documentation and/or other materials provided with the
  23  *    distribution.
  24  *  + The names of its contributors may not be used to endorse or promote
  25  *    products derived  from this software without specific prior
  26  *    written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  29  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  32  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  33  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  34  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  35  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  36  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  37  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  38  * POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  *****************************************************************************
  41  *
  42  * AUTHOR:
  43  *
  44  *   Luke Sheneman
  45  *   sheneman@cs.uidaho.edu
  46  *
  47  */
  48
  49
  50 #ifndef _INC_CLEARCUT_H_
  51 #define _INC_CLEARCUT_H_ 1
  52
  53 extern "C" {
  54
  55 #include "common.h"
  56 #include "cmdargs.h"
  57
  58 #define NJ_VERSION "1.0.9"
  59
  60
  61 #define NJ_INTERNAL_NODE -1
  62 #define NJ_LAST 101
  63
  64 #define NJ_INPUT_MODE_UNKNOWN             0
  65 #define NJ_INPUT_MODE_DISTANCE            100
  66 #define NJ_INPUT_MODE_UNALIGNED_SEQUENCES 101
  67 #define NJ_INPUT_MODE_ALIGNED_SEQUENCES   102
  68
  69 #define NJ_MODEL_NONE    100
  70 #define NJ_MODEL_JUKES   101
  71 #define NJ_MODEL_KIMURA  102
  72
  73
  74
  75
  76 /*
  77  * DMAT - Distance Matrix
  78  *
  79  * This is arguably the most important structure in the
  80  * program.  This is the distance matrix, and it is used
  81  * by many functions throughout the application.
  82  *
  83  * The matrix is architected as a contiguously allocated
  84  * upper-diagonal matrix of floats which include the
  85  * diagonal.
  86  *
  87  * Example:
  88  *
  89  *      0    1    2    3    4    5
  90  *   0 0.0  1.0  0.3  0.2  0.1  0.3
  91  *   1      0.0  0.3  0.2  0.1  0.8
  92  *   2           0.0  0.1  0.3  0.5
  93  *   3                0.0  0.2  0.1
  94  *   4                     0.0  0.2
  95  *   5                          0.0
  96  *
  97  * The distance matrix shrinks with every join operation,
  98  * so I track the original and working size of the matrix
  99  * inside the matrix.
 100  *
 101  * One fast optimization to shrink the distance matrix
 102  * involves incrementing the "val" pointer.  Thus, in
 103  * addition to tracking the pointer to the distances,
 104  * I also track the original pointer to that I can
 105  * free the memory associated with the working distance
 106  * matrix.
 107  *
 108  * This also applies to the r and r2 vectors which are
 109  * used to compute the transformed distances in the
 110  * matrix.
 111  *
 112  */
 113
 114 typedef struct _STRUCT_DMAT {
 115
 116   long int ntaxa;   /* the original size of the distance matrix */
 117   long int size;    /* the current/effective size of the distance matrix */
 118
 119   char **taxaname;  /* a pointer to an array of taxa name strings */
 120
 121   float *val;       /* the distances */
 122   float *valhandle; /* to track the orig. pointer to free memory */
 123
 124   float *r, *r2;    /* r and r2 vectors (used to compute transformed dists) */
 125   float *rhandle, *r2handle;  /* track orig. pointers to free memory */
 126
 127 } DMAT;
 128
 129
 130
 131 /*
 132  * NJ_TREE - The Tree Data Structure
 133  *
 134  *
 135  * The tree is represented internally as a rooted
 136  * binary tree.  Each internal node has a left and a right child.
 137  *
 138  * Additionally, I track the distance between the current node
 139  * and that node's parent (i.e. the branch length).
 140  *
 141  * Finally, I track the index of the taxa for leaf nodes.
 142  *
 143  */
 144 typedef struct _STRUCT_NJ_TREE {
 145
 146   struct _STRUCT_NJ_TREE *left;  /* left child  */
 147   struct _STRUCT_NJ_TREE *right; /* right child */
 148
 149   float dist;  /* branch length.  i.e. dist from node to parent */
 150
 151   long int taxa_index; /* for terminal nodes, track the taxon index */
 152
 153 } NJ_TREE;
 154
 155
 156
 157 /*
 158  * NJ_VERTEX
 159  *
 160  * This structure is used for building trees.  It is a vector
 161  * which, represents the center of the star when building the RNJ/NJ
 162  * tree through star-decomposition.
 163  *
 164  * It contains a vector of tree (node) pointers.  These pointers
 165  * get joined together by a new internal node, and the new internal
 166  * node is placed back into the vector of nodes (which is now smaller).
 167  *
 168  * To keep this vector in sync. with the shrinking matrix, parts of
 169  * the vector are shuffled around, and so a pointer to the originally
 170  * allocated vector is stored such that it can be freed from memory
 171  * later.
 172  *
 173  * The original and working sizes of the vector are also tracked.
 174  *
 175  */
 176 typedef struct _STRUCT_NJ_VERTEX {
 177
 178   NJ_TREE **nodes;
 179   NJ_TREE **nodes_handle;  /* original memory handle for freeing */
 180
 181   long int nactive;  /* number of active nodes in the list */
 182   long int size;     /* the total size of the vertex */
 183
 184 } NJ_VERTEX;
 185
 186
 187 /* some function prototypes */
 188 int clearcut_main(int, char**);
 189
 190 /* core function for performing Relaxed Neighbor Joining */
 191 NJ_TREE *
 192 NJ_relaxed_nj(NJ_ARGS *nj_args, DMAT *dmat);
 193
 194 /* function for performing traditional Neighbor-Joining */
 195 NJ_TREE *
 196 NJ_neighbor_joining(NJ_ARGS *nj_args, DMAT *dmat);
 197
 198 /* print the distance matrix (for debugging) */
 199 void
 200 NJ_print_distance_matrix(DMAT *dmat);
 201
 202 /* output the computed tree to stdout or to the specified file */
 203 void
 204 NJ_output_tree(NJ_ARGS *nj_args,
 205                NJ_TREE *tree,
 206                DMAT *dmat,
 207                long int count);
 208
 209 /* the recursive function for outputting trees */
 210 void
 211 NJ_output_tree2(FILE *fp,
 212                 NJ_ARGS *nj_args,
 213                 NJ_TREE *tree,
 214                 NJ_TREE *root,
 215                 DMAT *dmat);
 216
 217 /* initialize vertex */
 218 NJ_VERTEX *
 219 NJ_init_vertex(DMAT *dmat);
 220
 221 /* used to decompose the star topology and build the tree */
 222 NJ_TREE *
 223 NJ_decompose(DMAT *dmat,
 224              NJ_VERTEX *vertex,
 225              long int x,
 226              long int y,
 227              int last_flag);
 228
 229 /* print the vertex vector (for debugging) */
 230 void
 231 NJ_print_vertex(NJ_VERTEX *vertex);
 232
 233 /* print taxa names (for debugging) */
 234 void
 235 NJ_print_taxanames(DMAT *dmat);
 236
 237 /* initialize r-vector prior to RNJ/NJ */
 238 void
 239 NJ_init_r(DMAT *dmat);
 240
 241 /* print the r-vector (for debugging) */
 242 void
 243 NJ_print_r(DMAT *dmat);
 244
 245 /* shuffle the distance matrix, usually after reading in input */
 246 void
 247 NJ_shuffle_distance_matrix(DMAT *dmat);
 248
 249 /* free memory from the tree */
 250 void
 251 NJ_free_tree(NJ_TREE *node);
 252
 253 /* print permutations (for debugging) */
 254 void
 255 NJ_print_permutation(long int *perm,
 256                      long int size);
 257
 258 /* duplicate a distance matrix for multiple iterations */
 259 DMAT *
 260 NJ_dup_dmat(DMAT *src);
 261
 262 /* free the distance matrix */
 263 void
 264 NJ_free_dmat(DMAT *dmat);
 265
 266 /* free the vertex vector */
 267 void
 268 NJ_free_vertex(NJ_VERTEX *vertex);
 269
 270 /* for computing the global minimum transformed distance in traditional NJ */
 271 float
 272 NJ_min_transform(DMAT *dmat,
 273                  long int *ret_i,
 274                  long int *ret_j);
 275
 276 }
 277
 278 #endif /* _INC_CLEARCUT_H_ */
 279
 280
 281
 282
 283
 284
 285