clearcut.h

/*
 * 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_ */