--- /dev/null
+
+
+
+/*
+ * clearcut.h
+ *
+ * $Id$
+ *
+ *****************************************************************************
+ *
+ * Copyright (c) 2004, Luke Sheneman
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * + Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * + Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ * + The names of its contributors may not be used to endorse or promote
+ * products derived from this software without specific prior
+ * written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ *****************************************************************************
+ *
+ * AUTHOR:
+ *
+ * Luke Sheneman
+ * sheneman@cs.uidaho.edu
+ *
+ */
+
+
+#ifndef _INC_CLEARCUT_H_
+#define _INC_CLEARCUT_H_ 1
+
+extern "C" {
+
+#include "common.h"
+#include "cmdargs.h"
+
+#define NJ_VERSION "1.0.9"
+
+
+#define NJ_INTERNAL_NODE -1
+#define NJ_LAST 101
+
+#define NJ_INPUT_MODE_UNKNOWN 0
+#define NJ_INPUT_MODE_DISTANCE 100
+#define NJ_INPUT_MODE_UNALIGNED_SEQUENCES 101
+#define NJ_INPUT_MODE_ALIGNED_SEQUENCES 102
+
+#define NJ_MODEL_NONE 100
+#define NJ_MODEL_JUKES 101
+#define NJ_MODEL_KIMURA 102
+
+
+
+
+/*
+ * DMAT - Distance Matrix
+ *
+ * This is arguably the most important structure in the
+ * program. This is the distance matrix, and it is used
+ * by many functions throughout the application.
+ *
+ * The matrix is architected as a contiguously allocated
+ * upper-diagonal matrix of floats which include the
+ * diagonal.
+ *
+ * Example:
+ *
+ * 0 1 2 3 4 5
+ * 0 0.0 1.0 0.3 0.2 0.1 0.3
+ * 1 0.0 0.3 0.2 0.1 0.8
+ * 2 0.0 0.1 0.3 0.5
+ * 3 0.0 0.2 0.1
+ * 4 0.0 0.2
+ * 5 0.0
+ *
+ * The distance matrix shrinks with every join operation,
+ * so I track the original and working size of the matrix
+ * inside the matrix.
+ *
+ * One fast optimization to shrink the distance matrix
+ * involves incrementing the "val" pointer. Thus, in
+ * addition to tracking the pointer to the distances,
+ * I also track the original pointer to that I can
+ * free the memory associated with the working distance
+ * matrix.
+ *
+ * This also applies to the r and r2 vectors which are
+ * used to compute the transformed distances in the
+ * matrix.
+ *
+ */
+
+typedef struct _STRUCT_DMAT {
+
+ long int ntaxa; /* the original size of the distance matrix */
+ long int size; /* the current/effective size of the distance matrix */
+
+ char **taxaname; /* a pointer to an array of taxa name strings */
+
+ float *val; /* the distances */
+ float *valhandle; /* to track the orig. pointer to free memory */
+
+ float *r, *r2; /* r and r2 vectors (used to compute transformed dists) */
+ float *rhandle, *r2handle; /* track orig. pointers to free memory */
+
+} DMAT;
+
+
+
+/*
+ * NJ_TREE - The Tree Data Structure
+ *
+ *
+ * The tree is represented internally as a rooted
+ * binary tree. Each internal node has a left and a right child.
+ *
+ * Additionally, I track the distance between the current node
+ * and that node's parent (i.e. the branch length).
+ *
+ * Finally, I track the index of the taxa for leaf nodes.
+ *
+ */
+typedef struct _STRUCT_NJ_TREE {
+
+ struct _STRUCT_NJ_TREE *left; /* left child */
+ struct _STRUCT_NJ_TREE *right; /* right child */
+
+ float dist; /* branch length. i.e. dist from node to parent */
+
+ long int taxa_index; /* for terminal nodes, track the taxon index */
+
+} NJ_TREE;
+
+
+
+/*
+ * NJ_VERTEX
+ *
+ * This structure is used for building trees. It is a vector
+ * which, represents the center of the star when building the RNJ/NJ
+ * tree through star-decomposition.
+ *
+ * It contains a vector of tree (node) pointers. These pointers
+ * get joined together by a new internal node, and the new internal
+ * node is placed back into the vector of nodes (which is now smaller).
+ *
+ * To keep this vector in sync. with the shrinking matrix, parts of
+ * the vector are shuffled around, and so a pointer to the originally
+ * allocated vector is stored such that it can be freed from memory
+ * later.
+ *
+ * The original and working sizes of the vector are also tracked.
+ *
+ */
+typedef struct _STRUCT_NJ_VERTEX {
+
+ NJ_TREE **nodes;
+ NJ_TREE **nodes_handle; /* original memory handle for freeing */
+
+ long int nactive; /* number of active nodes in the list */
+ long int size; /* the total size of the vertex */
+
+} NJ_VERTEX;
+
+
+/* some function prototypes */
+int clearcut_main(int, char**);
+
+/* core function for performing Relaxed Neighbor Joining */
+NJ_TREE *
+NJ_relaxed_nj(NJ_ARGS *nj_args, DMAT *dmat);
+
+/* function for performing traditional Neighbor-Joining */
+NJ_TREE *
+NJ_neighbor_joining(NJ_ARGS *nj_args, DMAT *dmat);
+
+/* print the distance matrix (for debugging) */
+void
+NJ_print_distance_matrix(DMAT *dmat);
+
+/* output the computed tree to stdout or to the specified file */
+void
+NJ_output_tree(NJ_ARGS *nj_args,
+ NJ_TREE *tree,
+ DMAT *dmat,
+ long int count);
+
+/* the recursive function for outputting trees */
+void
+NJ_output_tree2(FILE *fp,
+ NJ_ARGS *nj_args,
+ NJ_TREE *tree,
+ NJ_TREE *root,
+ DMAT *dmat);
+
+/* initialize vertex */
+NJ_VERTEX *
+NJ_init_vertex(DMAT *dmat);
+
+/* used to decompose the star topology and build the tree */
+NJ_TREE *
+NJ_decompose(DMAT *dmat,
+ NJ_VERTEX *vertex,
+ long int x,
+ long int y,
+ int last_flag);
+
+/* print the vertex vector (for debugging) */
+void
+NJ_print_vertex(NJ_VERTEX *vertex);
+
+/* print taxa names (for debugging) */
+void
+NJ_print_taxanames(DMAT *dmat);
+
+/* initialize r-vector prior to RNJ/NJ */
+void
+NJ_init_r(DMAT *dmat);
+
+/* print the r-vector (for debugging) */
+void
+NJ_print_r(DMAT *dmat);
+
+/* shuffle the distance matrix, usually after reading in input */
+void
+NJ_shuffle_distance_matrix(DMAT *dmat);
+
+/* free memory from the tree */
+void
+NJ_free_tree(NJ_TREE *node);
+
+/* print permutations (for debugging) */
+void
+NJ_print_permutation(long int *perm,
+ long int size);
+
+/* duplicate a distance matrix for multiple iterations */
+DMAT *
+NJ_dup_dmat(DMAT *src);
+
+/* free the distance matrix */
+void
+NJ_free_dmat(DMAT *dmat);
+
+/* free the vertex vector */
+void
+NJ_free_vertex(NJ_VERTEX *vertex);
+
+/* for computing the global minimum transformed distance in traditional NJ */
+float
+NJ_min_transform(DMAT *dmat,
+ long int *ret_i,
+ long int *ret_j);
+
+}
+
+#endif /* _INC_CLEARCUT_H_ */
+
+
+
+
+
+
+
projects / mothur.git / blobdiff