]> git.donarmstrong.com Git - mothur.git/blob - clearcut.h
fixed rf memory issue in constructure
[mothur.git] / 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