| 1 | /* RAxML-VI-HPC (version 2.2) a program for sequential and parallel estimation of phylogenetic trees |
|---|
| 2 | * Copyright August 2006 by Alexandros Stamatakis |
|---|
| 3 | * |
|---|
| 4 | * Partially derived from |
|---|
| 5 | * fastDNAml, a program for estimation of phylogenetic trees from sequences by Gary J. Olsen |
|---|
| 6 | * |
|---|
| 7 | * and |
|---|
| 8 | * |
|---|
| 9 | * Programs of the PHYLIP package by Joe Felsenstein. |
|---|
| 10 | * |
|---|
| 11 | * This program is free software; you may redistribute it and/or modify its |
|---|
| 12 | * under the terms of the GNU General Public License as published by the Free |
|---|
| 13 | * Software Foundation; either version 2 of the License, or (at your option) |
|---|
| 14 | * any later version. |
|---|
| 15 | * |
|---|
| 16 | * This program is distributed in the hope that it will be useful, but |
|---|
| 17 | * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
|---|
| 18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|---|
| 19 | * for more details. |
|---|
| 20 | * |
|---|
| 21 | * |
|---|
| 22 | * For any other enquiries send an Email to Alexandros Stamatakis |
|---|
| 23 | * Alexandros.Stamatakis@epfl.ch |
|---|
| 24 | * |
|---|
| 25 | * When publishing work that is based on the results from RAxML-VI-HPC please cite: |
|---|
| 26 | * |
|---|
| 27 | * Alexandros Stamatakis:"RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models". |
|---|
| 28 | * Bioinformatics 2006; doi: 10.1093/bioinformatics/btl446 |
|---|
| 29 | */ |
|---|
| 30 | |
|---|
| 31 | #if (defined(_WAYNE_MPI) || defined (_QUARTET_MPI)) |
|---|
| 32 | int processes; |
|---|
| 33 | #endif |
|---|
| 34 | |
|---|
| 35 | int processID; |
|---|
| 36 | infoList iList; |
|---|
| 37 | FILE *INFILE; |
|---|
| 38 | |
|---|
| 39 | int Thorough = 0; |
|---|
| 40 | |
|---|
| 41 | int globalArgc; |
|---|
| 42 | char **globalArgv; |
|---|
| 43 | |
|---|
| 44 | char run_id[128] = "", |
|---|
| 45 | workdir[1024] = "", |
|---|
| 46 | seq_file[1024] = "", |
|---|
| 47 | tree_file[1024]="", |
|---|
| 48 | verboseSplitsFileName[1024] = "", |
|---|
| 49 | weightFileName[1024] = "", |
|---|
| 50 | modelFileName[1024] = "", |
|---|
| 51 | excludeFileName[1024] = "", |
|---|
| 52 | bootStrapFile[1024] = "", |
|---|
| 53 | permFileName[1024] = "", |
|---|
| 54 | resultFileName[1024] = "", |
|---|
| 55 | logFileName[1024] = "", |
|---|
| 56 | checkpointFileName[1024] = "", |
|---|
| 57 | infoFileName[1024] = "", |
|---|
| 58 | randomFileName[1024] = "", |
|---|
| 59 | bootstrapFileName[1024] = "", |
|---|
| 60 | bootstrapFileNamePID[1024] = "", |
|---|
| 61 | bipartitionsFileName[1024] = "", |
|---|
| 62 | bipartitionsFileNameBranchLabels[1024] = "", |
|---|
| 63 | icFileNameBranchLabels[1024] = "", |
|---|
| 64 | ratesFileName[1024] = "", |
|---|
| 65 | perSiteLLsFileName[1024] = "", |
|---|
| 66 | lengthFileName[1024] = "", |
|---|
| 67 | lengthFileNameModel[1024] = "", |
|---|
| 68 | proteinModelFileName[1024] = "", |
|---|
| 69 | secondaryStructureFileName[1024] = "", |
|---|
| 70 | binaryModelParamsOutputFileName[1024] = "", |
|---|
| 71 | binaryModelParamsInputFileName[1024] = "", |
|---|
| 72 | quartetGroupingFileName[1024]; |
|---|
| 73 | |
|---|
| 74 | |
|---|
| 75 | |
|---|
| 76 | |
|---|
| 77 | |
|---|
| 78 | char *protModels[NUM_PROT_MODELS] = {"DAYHOFF", "DCMUT", "JTT", "MTREV", "WAG", "RTREV", "CPREV", "VT", |
|---|
| 79 | "BLOSUM62", "MTMAM", "LG", "MTART", "MTZOA", "PMB", "HIVB", "HIVW", |
|---|
| 80 | "JTTDCMUT", "FLU", "DUMMY", "DUMMY2", "AUTO", "LG4M", "LG4X", "PROT_FILE", "GTR_UNLINKED", "GTR"}; |
|---|
| 81 | |
|---|
| 82 | const char binaryStateNames[2] = {'0', '1'}; |
|---|
| 83 | const char dnaStateNames[4] = {'A', 'C', 'G', 'T'}; |
|---|
| 84 | const char protStateNames[20] = {'A','R', 'N', 'D', 'C', 'Q', 'E', 'G', 'H', |
|---|
| 85 | 'I', 'L', 'K', 'M', 'F', 'P', 'S', 'T', 'W', |
|---|
| 86 | 'Y', 'V'}; |
|---|
| 87 | const char genericStateNames[32] = {'0', '1', '2', '3', '4', '5', '6', '7', |
|---|
| 88 | '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', |
|---|
| 89 | 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', |
|---|
| 90 | 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V'}; |
|---|
| 91 | |
|---|
| 92 | const char inverseMeaningBINARY[4] = {'_', '0', '1', '-'}; |
|---|
| 93 | const char inverseMeaningDNA[16] = {'_', 'A', 'C', 'M', 'G', 'R', 'S', 'V', 'T', 'W', 'Y', 'H', 'K', 'D', 'B', '-'}; |
|---|
| 94 | const char inverseMeaningPROT[23] = {'A','R', 'N', 'D', 'C', 'Q', 'E', 'G', 'H', 'I', 'L', 'K', 'M', 'F', 'P', 'S', |
|---|
| 95 | 'T', 'W', 'Y', 'V', 'B', 'Z', '-'}; |
|---|
| 96 | const char inverseMeaningGeneric32[33] = {'0', '1', '2', '3', '4', '5', '6', '7', |
|---|
| 97 | '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', |
|---|
| 98 | 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', |
|---|
| 99 | 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', |
|---|
| 100 | '-'}; |
|---|
| 101 | const char inverseMeaningGeneric64[33] = {'0', '1', '2', '3', '4', '5', '6', '7', |
|---|
| 102 | '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', |
|---|
| 103 | 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', |
|---|
| 104 | 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', |
|---|
| 105 | '-'}; |
|---|
| 106 | |
|---|
| 107 | const unsigned int bitVectorIdentity[256] = {0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 ,26 , |
|---|
| 108 | 27 ,28 ,29 ,30 ,31 ,32 ,33 ,34 ,35 ,36 ,37 ,38 ,39 ,40 ,41 ,42 ,43 ,44 ,45 ,46 ,47 ,48 ,49 ,50 ,51 , |
|---|
| 109 | 52 ,53 ,54 ,55 ,56 ,57 ,58 ,59 ,60 ,61 ,62 ,63 ,64 ,65 ,66 ,67 ,68 ,69 ,70 ,71 ,72 ,73 ,74 ,75 ,76 , |
|---|
| 110 | 77 ,78 ,79 ,80 ,81 ,82 ,83 ,84 ,85 ,86 ,87 ,88 ,89 ,90 ,91 ,92 ,93 ,94 ,95 ,96 ,97 ,98 ,99 ,100 ,101 , |
|---|
| 111 | 102 ,103 ,104 ,105 ,106 ,107 ,108 ,109 ,110 ,111 ,112 ,113 ,114 ,115 ,116 ,117 ,118 ,119 ,120 ,121 ,122 , |
|---|
| 112 | 123 ,124 ,125 ,126 ,127 ,128 ,129 ,130 ,131 ,132 ,133 ,134 ,135 ,136 ,137 ,138 ,139 ,140 ,141 ,142 ,143 , |
|---|
| 113 | 144 ,145 ,146 ,147 ,148 ,149 ,150 ,151 ,152 ,153 ,154 ,155 ,156 ,157 ,158 ,159 ,160 ,161 ,162 ,163 ,164 , |
|---|
| 114 | 165 ,166 ,167 ,168 ,169 ,170 ,171 ,172 ,173 ,174 ,175 ,176 ,177 ,178 ,179 ,180 ,181 ,182 ,183 ,184 ,185 , |
|---|
| 115 | 186 ,187 ,188 ,189 ,190 ,191 ,192 ,193 ,194 ,195 ,196 ,197 ,198 ,199 ,200 ,201 ,202 ,203 ,204 ,205 ,206 , |
|---|
| 116 | 207 ,208 ,209 ,210 ,211 ,212 ,213 ,214 ,215 ,216 ,217 ,218 ,219 ,220 ,221 ,222 ,223 ,224 ,225 ,226 ,227 , |
|---|
| 117 | 228 ,229 ,230 ,231 ,232 ,233 ,234 ,235 ,236 ,237 ,238 ,239 ,240 ,241 ,242 ,243 ,244 ,245 ,246 ,247 ,248 , |
|---|
| 118 | 249 ,250 ,251 ,252 ,253 ,254 ,255}; |
|---|
| 119 | |
|---|
| 120 | |
|---|
| 121 | |
|---|
| 122 | const unsigned int bitVectorAA[23] = {1, 2, 4, 8, 16, 32, 64, 128, |
|---|
| 123 | 256, 512, 1024, 2048, 4096, |
|---|
| 124 | 8192, 16384, 32768, 65536, 131072, 262144, |
|---|
| 125 | 524288, 12 /* N | D */, 96 /*Q | E*/, 1048575 /* - */}; |
|---|
| 126 | |
|---|
| 127 | const unsigned int bitVectorSecondary[256] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, |
|---|
| 128 | 10, 11, 12, 13, 14, 15, 0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, |
|---|
| 129 | 208, 224, 240, 0, 17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, |
|---|
| 130 | 255, 0, 256, 512, 768, 1024, 1280, 1536, 1792, 2048, 2304, 2560, 2816, 3072, 3328, |
|---|
| 131 | 3584, 3840, 0, 257, 514, 771, 1028, 1285, 1542, 1799, 2056, 2313, 2570, 2827, 3084, |
|---|
| 132 | 3341, 3598, 3855, 0, 272, 544, 816, 1088, 1360, 1632, 1904, 2176, 2448, 2720, 2992, |
|---|
| 133 | 3264, 3536, 3808, 4080, 0, 273, 546, 819, 1092, 1365, 1638, 1911, 2184, 2457, 2730, |
|---|
| 134 | 3003, 3276, 3549, 3822, 4095, 0, 4096, 8192, 12288, 16384, 20480, 24576, 28672, 32768, |
|---|
| 135 | 36864, 40960, 45056, 49152, 53248, 57344, 61440, 0, 4097, 8194, 12291, 16388, 20485, 24582, |
|---|
| 136 | 28679, 32776, 36873, 40970, 45067, 49164, 53261, 57358, 61455, 0, 4112, 8224, 12336, 16448, |
|---|
| 137 | 20560, 24672, 28784, 32896, 37008, 41120, 45232, 49344, 53456, 57568, 61680, 0, 4113, 8226, |
|---|
| 138 | 12339, 16452, 20565, 24678, 28791, 32904, 37017, 41130, 45243, 49356, 53469, 57582, 61695, |
|---|
| 139 | 0, 4352, 8704, 13056, 17408, 21760, 26112, 30464, 34816, 39168, 43520, 47872, 52224, 56576, |
|---|
| 140 | 60928, 65280, 0, 4353, 8706, 13059, 17412, 21765, 26118, 30471, 34824, 39177, 43530, 47883, |
|---|
| 141 | 52236, 56589, 60942, 65295, 0, 4368, 8736, 13104, 17472, 21840, 26208, 30576, 34944, 39312, |
|---|
| 142 | 43680, 48048, 52416, 56784, 61152, 65520, 0, 4369, 8738, 13107, 17476, 21845, 26214, 30583, |
|---|
| 143 | 34952, 39321, 43690, 48059, 52428, 56797, 61166, 65535}; |
|---|
| 144 | |
|---|
| 145 | const unsigned int bitVector32[33] = {1, 2, 4, 8, 16, 32, 64, 128, |
|---|
| 146 | 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, |
|---|
| 147 | 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, |
|---|
| 148 | 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648u, |
|---|
| 149 | 4294967295u}; |
|---|
| 150 | |
|---|
| 151 | /*const unsigned int bitVector64[65] = {};*/ |
|---|
| 152 | |
|---|
| 153 | const unsigned int mask32[32] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, |
|---|
| 154 | 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, |
|---|
| 155 | 268435456, 536870912, 1073741824, 2147483648U}; |
|---|
| 156 | |
|---|
| 157 | const char *secondaryModelList[21] = { "S6A (GTR)", "S6B", "S6C", "S6D", "S6E", "S7A (GTR)", "S7B", "S7C", "S7D", "S7E", "S7F", "S16 (GTR)", "S16A", "S16B", "S16C", |
|---|
| 158 | "S16D", "S16E", "S16F", "S16I", "S16J", "S16K"}; |
|---|
| 159 | |
|---|
| 160 | double masterTime; |
|---|
| 161 | int partCount = 0; |
|---|
| 162 | int optimizeRateCategoryInvocations = 1; |
|---|
| 163 | |
|---|
| 164 | |
|---|
| 165 | |
|---|
| 166 | |
|---|
| 167 | |
|---|
| 168 | partitionLengths pLengths[MAX_MODEL] = { |
|---|
| 169 | |
|---|
| 170 | /* BINARY */ |
|---|
| 171 | {4, 4, 1, 4, 2, 1, 2, 8, 2, 2, FALSE, 3, inverseMeaningBINARY, 2, FALSE, bitVectorIdentity}, |
|---|
| 172 | |
|---|
| 173 | /* DNA */ |
|---|
| 174 | {16, 16, 3, 16, 12, 6, 4, 64, 6, 4, FALSE, 15, inverseMeaningDNA, 4, FALSE, bitVectorIdentity}, |
|---|
| 175 | |
|---|
| 176 | /* AA */ |
|---|
| 177 | {400, 400, 19, 400, 380, 190, 20, 460, 190, 20, FALSE, 22, inverseMeaningPROT, 20, TRUE, bitVectorAA}, |
|---|
| 178 | |
|---|
| 179 | /* SECONDARY_DATA */ |
|---|
| 180 | |
|---|
| 181 | {256, 256, 15, 256, 240, 120, 16, 4096, 120, 16, FALSE, 255, (char*)NULL, 16, TRUE, bitVectorSecondary}, |
|---|
| 182 | |
|---|
| 183 | |
|---|
| 184 | /* SECONDARY_DATA_6 */ |
|---|
| 185 | {36, 36, 5, 36, 30, 15, 6, 384, 15, 6, FALSE, 63, (char*)NULL, 6, TRUE, bitVectorIdentity}, |
|---|
| 186 | |
|---|
| 187 | |
|---|
| 188 | /* SECONDARY_DATA_7 */ |
|---|
| 189 | {49, 49, 6, 49, 42, 21, 7, 896, 21, 7, FALSE, 127, (char*)NULL, 7, TRUE, bitVectorIdentity}, |
|---|
| 190 | |
|---|
| 191 | /* 32 states */ |
|---|
| 192 | {1024, 1024, 31, 1024, 992, 496, 32, 1056, 496, 32, FALSE, 32, inverseMeaningGeneric32, 32, TRUE, bitVector32}, |
|---|
| 193 | |
|---|
| 194 | /* 64 states */ |
|---|
| 195 | {4096, 4096, 63, 4096, 4032, 2016, 64, 4160, 64, 2016, FALSE, 64, (char*)NULL, 64, TRUE, (unsigned int*)NULL} |
|---|
| 196 | }; |
|---|
| 197 | |
|---|
| 198 | partitionLengths pLength; |
|---|
| 199 | |
|---|
| 200 | |
|---|
| 201 | |
|---|
| 202 | |
|---|
| 203 | |
|---|
| 204 | |
|---|
| 205 | #ifdef _USE_PTHREADS |
|---|
| 206 | volatile int NumberOfJobs; |
|---|
| 207 | volatile int jobCycle; |
|---|
| 208 | volatile int threadJob; |
|---|
| 209 | volatile int NumberOfThreads; |
|---|
| 210 | |
|---|
| 211 | |
|---|
| 212 | volatile double *reductionBuffer; |
|---|
| 213 | volatile double *reductionBufferTwo; |
|---|
| 214 | volatile double *reductionBufferThree; |
|---|
| 215 | volatile int *reductionBufferParsimony; |
|---|
| 216 | volatile char *barrierBuffer; |
|---|
| 217 | |
|---|
| 218 | volatile branchInfo **branchInfos; |
|---|
| 219 | pthread_mutex_t mutex; |
|---|
| 220 | #endif |
|---|