1 /* 2 * pstep-split.h 3 * 4 * 5 * Part of TREE-PUZZLE 5.2 (July 2004) 6 * 7 * (c) 2003-2004 by Heiko A. Schmidt, Korbinian Strimmer, and Arndt von Haeseler 8 * (c) 1999-2003 by Heiko A. Schmidt, Korbinian Strimmer, 9 * M. Vingron, and Arndt von Haeseler 10 * (c) 1995-1999 by Korbinian Strimmer and Arndt von Haeseler 11 * 12 * All parts of the source except where indicated are distributed under 13 * the GNU public licence. See http://www.opensource.org for details. 14 * 15 * ($Id$) 16 * 17 */ 18 19 /* split based O(n^4) algorithm */ 20 21 #ifndef PSTEP_SPLIT_H 22 #define PSTEP_SPLIT_H 23 24 #include<stdio.h> 25 #include<stdlib.h> 26 #include"puzzle.h" 27 #include"util.h" 28 /* #include"newpstep.h" */ 29 30 #ifndef ONEEDGE 31 # define ONEEDGE ONEEDGE_SPLIT 32 #endif /* ! ONEEDGE_DEFINED */ 33 34 #define NOWHERE 0 35 #define UP 1 36 #define UPDOWNLEFT 2 37 #define UPDOWNRIGHT 3 38 #define DOWNLEFT 4 39 #define DOWNRIGHT 5 40 #define STARTING 6 41 42 43 /* tree structure */ 44 typedef struct oneedge_split { 45 /* pointer to other three edges */ 46 struct oneedge_split *up; 47 struct oneedge_split *downleft; 48 struct oneedge_split *downright; 49 int numedge; /* number of edge (index) */ 50 uli penalty; /* penalty of this edge */ 51 int *split; /* cluster array (up: 0..upsize-1; down: maxspc-1..maxspc-downsize */ 52 int upsize; /* size of root-ward cluster */ 53 int downsize; /* size of non-root-ward cluster */ 54 #if 0 55 uli edgeinfo; /* value of this edge (penalty) */ 56 int *edgemap; /* _orig algorithm: pointer to the local edgemap array */ 57 int *upcluster; /* cluster array of root-ward taxa */ 58 int *downcluster; /* cluster array of non-root-ward taxa */ 59 #endif 60 } ONEEDGE_SPLIT; 61 62 63 /*****************************************************************************/ 64 /* internal functions for representing and building puzzling step trees */ 65 /*****************************************************************************/ 66 67 /* initialize tree with the following starting configuration 68 * 69 * 2 70 * 0 +------- C(=2) 71 * A(=0) -----+ 72 * +------- B(=1) 73 * 1 74 * 75 * 76 * A(=0) 77 * [up =NULL] 78 * [downleft =1] 79 * [downright=2] 80 * [upcluster=0] 81 * [downcluster=1,2] 82 * [upsize=1] 83 * [downsize=2] 84 * 85 * o 86 * | 87 * | 88 * +-------------+--------------+ 89 * | | 90 * | | 91 * o o 92 * 93 * C(=1) B(=2) 94 * [up =0] [up =0] 95 * [downleft =NULL] [downleft =NULL] 96 * [downright=NULL] [downright=NULL] 97 * [upcluster=0,2] [upcluster=0] 98 * [downcluster=1] [downcluster=2] 99 * [upsize=2] [upsize=2] 100 * [downsize=1] [downsize=1] 101 * 102 * nextedge = 3 103 * nextleaf = 3 104 * and set according edge maps 105 * 106 */ 107 void inittree_split(ONEEDGE_SPLIT **edge, /* out: new array of edges */ 108 int **edgeofleaf,/* out: array of external edge ptrs */ 109 int Maxspc, /* in: Number of species (n) */ 110 int Maxbrnch, /* in: Number of branches (2n-3) */ 111 int *nextedge, /* out: next free edge index (=3) */ 112 int *nextleaf); /* out: next free leaf index (=3) */ 113 114 /* add next leaf on the specified edge */ 115 void addnextleaf_split(int dockedge, /* insert here */ 116 ONEEDGE_SPLIT *edge, /* edge array */ 117 int *edgeofleaf, /* ext. edge idx array */ 118 int Maxspc, /* No. of species */ 119 int Maxbrnch, /* No. of branches */ 120 int *nextedge, /* next free edge idx */ 121 int *nextleaf); /* next free leaf idx */ 122 123 /* free memory (to be called after inittree) */ 124 void freetree_split(ONEEDGE_SPLIT *edge, /* edge array */ 125 int *edgeofleaf, /* ext. edge idx array */ 126 int Maxspc); /* No. of species */ 127 128 /* writes OTU sitting on edge ed */ 129 void writeOTU_split(FILE *outfp, /* output file */ 130 int ed, /* edge to subtree */ 131 ONEEDGE_SPLIT *edge, /* edge array */ 132 int *edgeofleaf, /* ext. edge idx array */ 133 int nextedge, /* next free edge idx */ 134 int nextleaf, /* next free leaf idx */ 135 int *column, /* current screen depth */ 136 int *trueID); /* species permutation */ 137 138 /* write tree */ 139 void writetree_split(FILE *outfp, /* output file */ 140 ONEEDGE_SPLIT *edge, /* edge array */ 141 int *edgeofleaf, /* ext. edge idx array */ 142 int nextedge, /* next free edge idx */ 143 int nextleaf, /* next free leaf idx */ 144 int *trueID); /* species permutation */ 145 146 /* clear all edgeinfos */ 147 void resetedgeinfo_split(ONEEDGE_SPLIT *edge, /* edge array */ 148 int nextedge); /* next free edge idx */ 149 150 /* increment all edgeinfo between leaf A and B */ 151 void incrementedgeinfo_split(int A, /* start leaf of penalty path */ 152 int B, /* start leaf of penalty path */ 153 ONEEDGE_SPLIT *edge, /* edge array */ 154 int *edgeofleaf); /* ext. edge idx array */ 155 156 /* checks which edge has the lowest edgeinfo 157 if there are several edges with the same lowest edgeinfo, 158 one of them will be selected randomly */ 159 void minimumedgeinfo_split(ONEEDGE_SPLIT *edge, /* edge array */ 160 int *edgeofleaf, /* ext. edge idx array */ 161 int nextedge, /* next free edge idx */ 162 int nextleaf, /* next free leaf idx */ 163 int *minedge, /* minimum edge set */ 164 uli *mininfo); /* minumum penalty */ 165 166 /*****************************************************************************/ 167 /* global functions for representing and building puzzling step trees */ 168 /*****************************************************************************/ 169 170 /* perform one single puzzling step to produce one intermediate tree */ 171 void onepstep_split( /* PStep (intermediate) tree topol: */ 172 ONEEDGE_SPLIT **edge, /* out: new array of edges */ 173 int **edgeofleaf, /* out: array of extern edge ptrs */ 174 unsigned char *quartettopols, /* in: quartetblock with all topols */ 175 int Maxspc, /* in: Number of species (n) */ 176 ivector permutation); /* in: species permutation (trueID) */ 177 178 /* perform Numtrial single puzzling steps constructing Numtrial intermediate */ 179 /* trees, sort each of them and extract splits for consensus step */ 180 void allpstep_split(uli Numtrial, /* in: no. psteps to perform */ 181 unsigned char *quartetinfo, /* in: quartetblock with all topols*/ 182 int Maxspc, /* in: Number of species (n) */ 183 int fixedorder_optn); /* in: 'fixed' anchored RNG (debug)*/ 184 185 #endif /* PSTEP_SPLIT_H */ 186 187