initial commit
[jalview.git] / forester / archive / RIO / others / phylip_mod / src / seqboot.c
1 #include "phylip.h"
2 #include "seq.h"
3
4 /* version 3.6. (c) Copyright 1993-2005 by the University of Washington.
5    Written by Joseph Felsenstein, Akiko Fuseki, Sean Lamont, Andrew Keeffe,
6    and Doug Buxton.
7    Permission is granted to copy and use this program provided no fee is
8    charged for it and provided that this copyright notice is not removed. */
9
10 typedef enum {
11   seqs, morphology, restsites, genefreqs
12 } datatype;
13
14 typedef enum {
15   dna, rna, protein
16 } seqtype;
17
18
19 #ifndef OLDC
20 /* function prototypes */
21 void   getoptions(void);
22 void   seqboot_inputnumbers(void);
23 void   seqboot_inputfactors(void);
24 void   inputoptions(void);
25 void   seqboot_inputdata(void);
26 void   allocrest(void);
27 void   allocnew(void);
28 void   doinput(int argc, Char *argv[]);
29 void   bootweights(void);
30 void   sppermute(long);
31 void   charpermute(long, long);
32 void   writedata(void);
33 void   writeweights(void);
34 void   writecategories(void);
35 void   writeauxdata(steptr, FILE*);
36 void   writefactors(void);
37 void   bootwrite(void);
38 void   seqboot_inputaux(steptr, FILE*);
39 /* function prototypes */
40 #endif
41
42
43 FILE *outcatfile, *outweightfile, *outmixfile, *outancfile, *outfactfile;
44 Char infilename[FNMLNGTH], outfilename[FNMLNGTH], catfilename[FNMLNGTH], outcatfilename[FNMLNGTH],
45   weightfilename[FNMLNGTH], outweightfilename[FNMLNGTH], mixfilename[FNMLNGTH], outmixfilename[FNMLNGTH], ancfilename[FNMLNGTH], outancfilename[FNMLNGTH],
46   factfilename[FNMLNGTH], outfactfilename[FNMLNGTH];
47 long sites, loci, maxalleles, groups, newsites, newersites,
48   newgroups, newergroups, nenzymes, reps, ws, blocksize, categs, maxnewsites;
49 boolean bootstrap, permute, ild, lockhart, jackknife, regular, xml, nexus,
50   weights, categories, factors, enzymes, all, justwts, progress, mixture,
51   firstrep, ancvar;
52 double fracsample;
53 datatype data;
54 seqtype seq;
55 steptr oldweight, where, how_many, newwhere, newhowmany,
56   newerwhere, newerhowmany, factorr, newerfactor, mixdata, ancdata;
57 steptr *charorder;
58 Char *factor;
59 long *alleles;
60 Char **nodep;
61 double **nodef;
62 long **sppord;
63 longer seed;
64
65
66 void getoptions()
67 {
68   /* interactively set options */
69   long reps0;
70   long inseed, inseed0, loopcount, loopcount2;
71   Char ch;
72   boolean done1;
73
74   data = seqs;
75   seq = dna;
76   bootstrap = true;
77   jackknife = false;
78   permute = false;
79   ild = false;
80   lockhart = false;
81   blocksize = 1;
82   regular = true;
83   fracsample = 1.0;
84   all = false;
85   reps = 100;
86   weights = false;
87   mixture = false;
88   ancvar = false;
89   categories = false;
90   justwts = false;
91   printdata = false;
92   dotdiff = true;
93   progress = true;
94   interleaved = true;
95   xml = false;
96   nexus = false;
97   factors = false;
98   loopcount = 0;
99   for (;;) {
100     cleerhome();
101     printf("\nBootstrapping algorithm, version %s\n\n",VERSION);
102     printf("Settings for this run:\n");
103     printf("  D      Sequence, Morph, Rest., Gene Freqs?  %s\n",
104            (data == seqs       ) ? "Molecular sequences"      :
105            (data == morphology ) ? "Discrete Morphology"      :
106            (data == restsites)   ? "Restriction Sites"        :
107            (data == genefreqs)   ? "Gene Frequencies" : "");
108     if (data == restsites)
109       printf("  E                       Number of enzymes?  %s\n",
110              enzymes ? "Present in input file" :
111                        "Not present in input file");
112     if (data == genefreqs)
113       printf("  A       All alleles present at each locus?  %s\n",
114              all ? "Yes" : "No, one absent at each locus");
115     if (data == morphology)
116       printf("  F                 Use factors information?  %s\n",
117            factors ? "Yes" : "No");
118
119     printf("  J  Bootstrap, Jackknife, Permute, Rewrite?  %s\n",
120            regular && jackknife ? "Delete-half jackknife" :
121            (!regular) && jackknife ? "Delete-fraction jackknife" :
122            permute   ? "Permute species for each character" :
123            ild ? "Permute character order" :
124            lockhart ? "Permute within species" :
125            regular && bootstrap ? "Bootstrap" :
126            (!regular) && bootstrap ? "Partial bootstrap" :
127            "Rewrite data");
128     if (bootstrap || jackknife) {
129       printf("  ");
130       putchar('%');
131       printf("    Regular or altered sampling fraction?  ");
132       if (regular)
133         printf("regular\n");
134       else {
135         if (fabs(fracsample*100 - (int)(fracsample*100)) > 0.01) {
136           if (fracsample < 1)
137             printf("%2.1lf", 100.0*fracsample);
138           else
139             printf("%3.1lf", 100.0*fracsample);
140         } else { if (fracsample < 1)
141             printf("%2.0lf", 100.0*fracsample);
142           else
143             printf("%3.0lf", 100.0*fracsample);
144         }
145         putchar('%');
146         printf(" sampled\n");
147       }
148     }
149     if ((data == seqs)
150         && !(jackknife || permute || bootstrap || ild || lockhart)) {
151       printf("  P     PHYLIP, NEXUS, or XML output format?  %s\n",
152            nexus ? "NEXUS" : xml ? "XML" : "PHYLIP");
153       if (xml || ((data == seqs) && nexus)) {
154         printf("  S             Type of molecular sequences?  " );
155         switch (seq) {
156           case (dna) : printf("DNA\n"); break;
157           case (rna) : printf("RNA\n"); break;
158           case (protein) : printf("Protein\n"); break;
159         }
160       }
161     }
162     if ((data == morphology) && !(jackknife || permute || ild
163                                   || lockhart || bootstrap))
164       printf("  P           PHYLIP or NEXUS output format?  %s\n",
165                                          nexus ? "NEXUS" : "PHYLIP");
166     if (bootstrap) {
167       if (blocksize > 1)
168       printf("  B      Block size for block-bootstrapping?  %ld\n", blocksize);
169       else
170         printf("  B      Block size for block-bootstrapping?  %ld (regular bootstrap)\n", blocksize);
171     }
172     if (bootstrap || jackknife || permute || ild || lockhart)
173       printf("  R                     How many replicates?  %ld\n", reps);
174     if (jackknife || bootstrap || permute) {
175       printf("  W              Read weights of characters?  %s\n",
176           (weights ? "Yes" : "No"));
177       if(data == morphology){
178         printf("  X                       Read mixture file?  %s\n",
179                (mixture ? "Yes" : "No"));
180         printf("  N                     Read ancestors file?  %s\n",
181                (ancvar ? "Yes" : "No"));
182       }
183       if (data == seqs)
184         printf("  C                Read categories of sites?  %s\n",
185           (categories ? "Yes" : "No"));
186       if ((!permute)) {
187         printf("  S     Write out data sets or just weights?  %s\n",
188           (justwts ? "Just weights" : "Data sets"));
189       }
190     }
191     if (data == seqs || data == restsites)
192       printf("  I             Input sequences interleaved?  %s\n",
193              interleaved ? "Yes" : "No, sequential");
194     printf("  0      Terminal type (IBM PC, ANSI, none)?  %s\n",
195            ibmpc ? "IBM PC" : ansi  ? "ANSI" : "(none)");
196     printf("  1       Print out the data at start of run  %s\n",
197            printdata ? "Yes" : "No");
198     if (printdata)
199       printf("  .     Use dot-differencing to display them  %s\n",
200            dotdiff ? "Yes" : "No");
201     printf("  2     Print indications of progress of run  %s\n",
202            progress ? "Yes" : "No");
203     printf("\n  Y to accept these or type the letter for one to change\n");
204 #ifdef WIN32
205     phyFillScreenColor();
206 #endif
207     scanf("%c%*[^\n]", &ch);
208     getchar();
209     uppercase(&ch);
210     if (ch == 'Y')
211            break;
212     if (
213         (bootstrap && (strchr("ABCDEFSJPRWXNI%1.20",ch) != NULL)) ||
214         (jackknife && (strchr("ACDEFSJPRWXNI%1.20",ch) != NULL)) ||
215         ((permute || ild || lockhart)
216          && (strchr("ACDEFSJPRXNI%1.20",ch) != NULL)) ||
217         ((!(bootstrap || jackknife || permute || ild || lockhart)) &&
218          ((!xml) && (strchr("ADEFJPI1.20",ch) != NULL))) ||
219         (((data == morphology) || (data == seqs))
220          && (nexus || xml) && (strchr("ADEFJPSI1.20",ch) != NULL))
221         ) {
222       switch (ch) {
223         
224       case 'D':
225         if (data == genefreqs)
226           data = seqs;
227         else
228           data = (datatype)((long)data + 1);
229         break;
230         
231       case 'A':
232         all = !all;
233         break;
234         
235       case 'E':
236         enzymes = !enzymes;
237         break;
238         
239       case 'J':
240         if (permute) {
241           permute = false;
242           ild = true;
243         } else if (ild) {
244             ild = false;
245             lockhart = true;
246           } else if (lockhart)
247               lockhart = false;
248             else if (jackknife) {
249                 jackknife = false;
250                 permute = true;
251             } else if (bootstrap) {
252                   bootstrap = false;
253                   jackknife = true;
254               } else
255                   bootstrap = true;
256         break;
257         
258       case '%':
259         regular = !regular;
260         if (!regular) {
261           loopcount2 = 0;
262           do {
263             printf("Samples as percentage of");
264             if ((data == seqs) || (data == restsites))
265               printf(" sites?\n");
266             if (data == morphology)
267             printf(" characters?\n");
268             if (data == genefreqs)
269               printf(" loci?\n");
270             scanf("%lf%*[^\n]", &fracsample);
271             getchar();
272             done1 = (fracsample > 0.0);
273             if (!done1) {
274               printf("BAD NUMBER: must be positive\n");
275             }
276             fracsample = fracsample/100.0;
277             countup(&loopcount2, 10);
278           } while (done1 != true);
279         }
280         break;
281
282       case 'P':
283         if (data == seqs) {
284           if (!xml && !nexus)
285             nexus = true;
286           else {
287             if (nexus) {
288               nexus = false;
289               xml = true;
290               }
291             else xml = false;
292             }
293           }
294         if (data == morphology) {
295           nexus = !nexus;
296           xml = false;
297           }
298         break;
299         
300       case 'S':
301         if(jackknife || permute || bootstrap || ild || lockhart){
302           justwts = !justwts;          
303         } else {
304           switch (seq) {
305           case (dna): seq = rna; break;
306           case (rna): seq = protein; break;
307           case (protein): seq = dna; break;
308           }
309         }
310         break;
311         
312       case 'B':
313         loopcount2 = 0;
314         do {
315           printf("Block size?\n");
316 #ifdef WIN32
317           phyFillScreenColor();
318 #endif
319           scanf("%ld%*[^\n]", &blocksize);
320           getchar();
321           done1 = (blocksize > 0);
322           if (!done1) {
323             printf("BAD NUMBER: must be positive\n");
324           }
325           countup(&loopcount2, 10);
326         } while (done1 != true);
327         break;
328
329       case 'R':
330         reps0 = reps;
331         loopcount2 = 0;
332         do {
333           printf("Number of replicates?\n");
334 #ifdef WIN32
335           phyFillScreenColor();
336 #endif
337           scanf("%ld%*[^\n]", &reps);
338           getchar();
339           done1 = (reps > 0);
340           if (!done1) {
341             printf("BAD NUMBER: must be positive\n");
342             reps = reps0;
343           }
344           countup(&loopcount2, 10);
345         } while (done1 != true);
346         break;
347
348       case 'W':
349         weights = !weights;
350         break;
351
352       case 'X':
353         mixture = !mixture;
354         break;
355
356       case 'N':
357         ancvar = !ancvar;
358         break;
359
360       case 'C':
361         categories = !categories;
362         break;
363
364       case 'F':
365         factors = !factors;
366         break;
367
368       case 'I':
369         interleaved = !interleaved;
370         break;
371         
372       case '0':
373         initterminal(&ibmpc, &ansi);
374         break;
375         
376       case '1':
377         printdata = !printdata;
378         break;
379         
380       case '.':
381         dotdiff = !dotdiff;
382         break;
383         
384       case '2':
385         progress = !progress;
386         break;
387       }
388     } else
389       printf("Not a possible option!\n");
390     countup(&loopcount, 100);
391   }
392   if (bootstrap || jackknife) {
393     if (jackknife && regular)
394       fracsample = 0.5;
395     if (bootstrap && regular)
396       fracsample = 1.0;
397   }
398   if (bootstrap || jackknife || permute || ild || lockhart)
399     initseed(&inseed, &inseed0, seed);
400   xml = xml && (data == seqs);
401   categories = categories && (data == seqs);
402   mixture = mixture && (data == morphology);
403   ancvar = ancvar && (data == morphology);
404 }  /* getoptions */
405
406
407 void seqboot_inputnumbers()
408 {
409   /* read numbers of species and of sites */
410   long i;
411
412   fscanf(infile, "%ld%ld", &spp, &sites);
413   loci = sites;
414   maxalleles = 1;
415   if (data == restsites && enzymes)
416     fscanf(infile, "%ld", &nenzymes);
417   if (data == genefreqs) {
418     alleles = (long *)Malloc(sites*sizeof(long));
419     scan_eoln(infile);
420     sites = 0;
421     for (i = 0; i < (loci); i++) {
422       if (eoln(infile)) 
423         scan_eoln(infile);
424       fscanf(infile, "%ld", &alleles[i]);
425       if (alleles[i] > maxalleles)
426          maxalleles = alleles[i];
427       if (all)
428          sites += alleles[i];
429       else
430          sites += alleles[i] - 1;
431     }
432     if (!all)
433       maxalleles--;
434     scan_eoln(infile);
435   }
436 }  /* seqboot_inputnumbers */
437
438
439 void seqboot_inputfactors()
440 {
441   long i, j;
442   Char ch, prevch;
443
444   prevch = ' ';
445   j = 0;
446   for (i = 0; i < (sites); i++) {
447     do {
448       if (eoln(factfile)) 
449         scan_eoln(factfile);
450       ch = gettc(factfile);
451     } while (ch == ' ');
452     if (ch != prevch)
453       j++;
454     prevch = ch;
455     factorr[i] = j;
456   }
457   scan_eoln(factfile);
458 }  /* seqboot_inputfactors */
459
460
461 void inputoptions()
462 {
463   /* input the information on the options */
464   long weightsum, maxfactsize, i, j, k, l, m;
465
466   if (data == genefreqs) {
467     k = 0;
468     l = 0;
469     for (i = 0; i < (loci); i++) {
470       if (all)
471         m = alleles[i];
472       else
473         m = alleles[i] - 1;
474       k++;
475       for (j = 1; j <= m; j++) {
476         l++;
477         factorr[l - 1] = k;
478       }
479     }
480   } else {
481     for (i = 1; i <= (sites); i++)
482       factorr[i - 1] = i;
483   }
484   if(factors){
485     seqboot_inputfactors();
486   }
487   for (i = 0; i < (sites); i++)
488     oldweight[i] = 1;
489   if (weights)
490     inputweights2(0, sites, &weightsum, oldweight, &weights, "seqboot");
491   if (factors && printdata) {
492     for(i = 0; i < sites; i++)
493       factor[i] = (char)('0' + (factorr[i]%10));
494     printfactors(outfile, sites, factor, " (least significant digit)");
495   }
496   if (weights && printdata)
497     printweights(outfile, 0, sites, oldweight, "Sites");
498   for (i = 0; i < (loci); i++)
499     how_many[i] = 0;
500   for (i = 0; i < (loci); i++)
501     where[i] = 0;
502   for (i = 1; i <= (sites); i++) {
503     how_many[factorr[i - 1] - 1]++;
504     if (where[factorr[i - 1] - 1] == 0)
505       where[factorr[i - 1] - 1] = i;
506   }
507   groups = factorr[sites - 1];
508   newgroups = 0;
509   newsites = 0;
510   maxfactsize = 0;
511   for(i = 0 ; i < loci ; i++){
512     if(how_many[i] > maxfactsize){
513       maxfactsize = how_many[i];
514     }
515   }
516   maxnewsites = groups * maxfactsize;
517   allocnew();
518   for (i = 0; i < (groups); i++) {
519     if (oldweight[where[i] - 1] > 0) {
520       newgroups++;
521       newsites += how_many[i];
522       newwhere[newgroups - 1] = where[i];
523       newhowmany[newgroups - 1] = how_many[i];
524     }
525   }
526 }  /* inputoptions */
527
528
529 void seqboot_inputdata()
530 {
531   /* input the names and sequences for each species */
532   long i, j, k, l, m, n, basesread, basesnew=0;
533   double x;
534   Char charstate;
535   boolean allread, done;
536
537   if (data == genefreqs) {
538     nodef = (double **)Malloc(spp*sizeof(double *));
539     for (i = 0; i < (spp); i++)
540       nodef[i] = (double *)Malloc(sites*sizeof(double));
541   } else {
542     nodep = (Char **)Malloc(spp*sizeof(Char *));
543     for (i = 0; i < (spp); i++)
544       nodep[i] = (Char *)Malloc(sites*sizeof(Char));
545   }
546   j = nmlngth + (sites + (sites - 1) / 10) / 2 - 5;
547   if (j < nmlngth - 1)
548     j = nmlngth - 1;
549   if (j > 37)
550     j = 37;
551   if (printdata) {
552     fprintf(outfile, "\nBootstrapping algorithm, version %s\n\n\n",VERSION);
553     if (bootstrap)  {
554       if (blocksize > 1) {
555         if (regular)      
556       fprintf(outfile, "Block-bootstrap with block size %ld\n\n", blocksize);
557         else
558           fprintf(outfile, "Partial (%2.0f%%) block-bootstrap with block size %ld\n\n",
559                   100*fracsample, blocksize);
560       } else {
561         if (regular)
562           fprintf(outfile, "Bootstrap\n\n");
563         else 
564           fprintf(outfile, "Partial (%2.0f%%) bootstrap\n\n", 100*fracsample);
565       }
566     } else {
567       if (jackknife) {
568         if (regular)
569           fprintf(outfile, "Delete-half Jackknife\n\n");
570         else
571     fprintf(outfile, "Delete-%2.0f%% Jackknife\n\n", 100*(1.0-fracsample));
572       } else {
573         if (permute) {
574           fprintf(outfile, "Species order permuted separately for each");
575           if (data == genefreqs)
576             fprintf(outfile, " locus\n\n");
577           if (data == seqs)
578             fprintf(outfile, " site\n\n");
579           if (data == morphology)
580             fprintf(outfile, " character\n\n");
581           if (data == restsites)
582             fprintf(outfile, " site\n\n");
583         }
584         else {
585           if (ild) {
586             if (data == genefreqs)
587               fprintf(outfile, "Locus");
588             if (data == seqs)
589               fprintf(outfile, "Site");
590             if (data == morphology)
591               fprintf(outfile, "Character");
592             if (data == restsites)
593               fprintf(outfile, "Site");
594             fprintf(outfile, " order permuted\n\n");
595           } else {
596             if (lockhart)
597               if (data == genefreqs)
598                 fprintf(outfile, "Locus");
599               if (data == seqs)
600                 fprintf(outfile, "Site");
601               if (data == morphology)
602                 fprintf(outfile, "Character");
603               if (data == restsites)
604                 fprintf(outfile, "Site");
605          fprintf(outfile, " order permuted separately for each species\n\n");
606           }
607         }
608       }
609     }
610     if (data == genefreqs)
611       fprintf(outfile, "%3ld species, %3ld  loci\n\n", spp, loci);
612     else {
613       fprintf(outfile, "%3ld species, ", spp);
614       if (data == seqs)
615         fprintf(outfile, "%3ld  sites\n\n", sites);
616         else if (data == morphology)
617           fprintf(outfile, "%3ld  characters\n\n", sites);
618           else if (data == restsites)
619             fprintf(outfile, "%3ld  sites\n\n", sites);
620     }
621     fprintf(outfile, "Name");
622     for (i = 1; i <= j; i++)
623       putc(' ', outfile);
624     fprintf(outfile, "Data\n");
625     fprintf(outfile, "----");
626     for (i = 1; i <= j; i++)
627       putc(' ', outfile);
628     fprintf(outfile, "----\n\n");
629   }
630   interleaved = (interleaved && ((data == seqs) || (data == restsites)));
631   if (data == genefreqs) {
632     for (i = 1; i <= (spp); i++) {
633       initname(i - 1);
634       j = 1;
635       while (j <= sites && !eoff(infile)) {
636         if (eoln(infile)) 
637           scan_eoln(infile);
638         fscanf(infile, "%lf", &x);
639         if ((unsigned)x > 1.0) {
640           printf("GENE FREQ OUTSIDE [0,1] in species %ld\n", i);
641           exxit(-1);
642         } else {
643           nodef[i - 1][j - 1] = x;
644           j++;
645         }
646       }
647       scan_eoln(infile);
648     }
649     return;
650   }
651   basesread = 0;
652   allread = false;
653   while (!allread) {
654     /* eat white space -- if the separator line has spaces on it*/
655     do {
656       charstate = gettc(infile);
657     } while (charstate == ' ' || charstate == '\t');
658     ungetc(charstate, infile);
659     if (eoln(infile)) 
660       scan_eoln(infile);
661     i = 1;
662     while (i <= spp) {
663       if ((interleaved && basesread == 0) || !interleaved)
664         initname(i-1);
665       j = interleaved ? basesread : 0;
666       done = false;
667       while (!done && !eoff(infile)) {
668         if (interleaved)
669           done = true;
670         while (j < sites && !(eoln(infile) ||eoff(infile))) {
671           charstate = gettc(infile);
672           if (charstate == '\n' || charstate == '\t')
673             charstate = ' ';
674           if (charstate == ' ' ||
675               (data == seqs && charstate >= '0' && charstate <= '9'))
676             continue;
677           uppercase(&charstate);
678           j++;
679           if (charstate == '.')
680             charstate = nodep[0][j-1];
681           nodep[i-1][j-1] = charstate;
682         }
683         if (interleaved)
684           continue;
685         if (j < sites) 
686           scan_eoln(infile);
687         else if (j == sites)
688           done = true;
689       }
690       if (interleaved && i == 1)
691         basesnew = j;
692       scan_eoln(infile);
693       if ((interleaved && j != basesnew) || ((!interleaved) && j != sites)){
694         printf("\n\nERROR: sequences out of alignment at site %ld", j+1);
695         printf(" of species %ld\n\n", i);
696         exxit(-1);}
697       i++;
698     }
699     if (interleaved) {
700       basesread = basesnew;
701       allread = (basesread == sites);
702     } else
703       allread = (i > spp);
704   }
705   if (!printdata)
706     return;
707   if (data == genefreqs)
708     m = (sites - 1) / 8 + 1;
709   else
710     m = (sites - 1) / 60 + 1;
711   for (i = 1; i <= m; i++) {
712     for (j = 0; j < spp; j++) {
713       for (k = 0; k < nmlngth; k++)
714         putc(nayme[j][k], outfile);
715       fprintf(outfile, "   ");
716       if (data == genefreqs)
717         l = i * 8;
718       else
719         l = i * 60;
720       if (l > sites)
721         l = sites;
722       if (data == genefreqs)
723         n = (i - 1) * 8;
724       else
725         n = (i - 1) * 60;
726       for (k = n; k < l; k++) {
727         if (data == genefreqs)
728           fprintf(outfile, "%8.5f", nodef[j][k]);
729         else {
730           if (j + 1 > 1 && nodep[j][k] == nodep[0][k])
731             charstate = '.';
732           else
733             charstate = nodep[j][k];
734           putc(charstate, outfile);
735           if ((k + 1) % 10 == 0 && (k + 1) % 60 != 0)
736             putc(' ', outfile);
737         
738         }
739       }
740       putc('\n', outfile);
741     }
742     putc('\n', outfile);
743   }
744   putc('\n', outfile);
745 }  /* seqboot_inputdata */
746
747
748 void allocrest()
749 { /* allocate memory for bookkeeping arrays */
750
751   oldweight = (steptr)Malloc(sites*sizeof(long));
752   weight = (steptr)Malloc(sites*sizeof(long));
753   if (categories)
754     category = (steptr)Malloc(sites*sizeof(long));
755   if (mixture)
756     mixdata = (steptr)Malloc(sites*sizeof(long));
757   if (ancvar)
758     ancdata = (steptr)Malloc(sites*sizeof(long));
759   where = (steptr)Malloc(loci*sizeof(long));
760   how_many = (steptr)Malloc(loci*sizeof(long));
761   factor = (Char *)Malloc(sites*sizeof(Char));
762   factorr = (steptr)Malloc(sites*sizeof(long));
763   nayme = (naym *)Malloc(spp*sizeof(naym));
764 }  /* allocrest */
765
766 void allocnew(void)
767 { /* allocate memory for arrays that depend on the lenght of the 
768      output sequence*/
769   long i;
770
771   newwhere = (steptr)Malloc(loci*sizeof(long));
772   newhowmany = (steptr)Malloc(loci*sizeof(long));
773   newerwhere = (steptr)Malloc(loci*sizeof(long));
774   newerhowmany = (steptr)Malloc(loci*sizeof(long));
775   newerfactor = (steptr)Malloc(maxnewsites*maxalleles*sizeof(long));
776   charorder = (steptr *)Malloc(spp*sizeof(steptr));
777   for (i = 0; i < spp; i++)
778     charorder[i] = (steptr)Malloc(maxnewsites*sizeof(long));
779 }
780
781 void doinput(int argc, Char *argv[])
782 { /* reads the input data */
783   getoptions();
784   seqboot_inputnumbers();
785   allocrest();
786   if (weights)
787     openfile(&weightfile,WEIGHTFILE,"input weight file",
788                "r",argv[0],weightfilename);
789   if (mixture){
790     openfile(&mixfile,MIXFILE,"mixture file", "r",argv[0],mixfilename);
791     openfile(&outmixfile,"outmixture","output mixtures file","w",argv[0],
792                outmixfilename);
793     seqboot_inputaux(mixdata, mixfile);
794   }
795   if (ancvar){
796     openfile(&ancfile,ANCFILE,"ancestor file", "r",argv[0],ancfilename);
797     openfile(&outancfile,"outancestors","output ancestors file","w",argv[0],
798                outancfilename);
799     seqboot_inputaux(ancdata, ancfile);
800   }
801   if (categories) {
802     openfile(&catfile,CATFILE,"input category file","r",argv[0],catfilename);
803     openfile(&outcatfile,"outcategories","output category file","w",argv[0],
804                outcatfilename);
805     inputcategs(0, sites, category, 9, "SeqBoot");
806   }
807   if (factors){
808     openfile(&factfile,FACTFILE,"factors file","r",argv[0],factfilename);
809     openfile(&outfactfile,"outfactors","output factors file","w",argv[0],
810                outfactfilename);
811   }
812   if (justwts && !permute)
813     openfile(&outweightfile,"outweights","output weight file",
814                "w",argv[0],outweightfilename);
815   else {
816     openfile(&outfile,OUTFILE,"output data file","w",argv[0],outfilename);
817   }
818   inputoptions();
819   seqboot_inputdata();
820 }  /* doinput */
821
822
823 void bootweights()
824 { /* sets up weights by resampling data */
825   long i, j, k, blocks;
826   double p, q, r;
827
828   ws = newgroups;
829   for (i = 0; i < (ws); i++)
830     weight[i] = 0;
831   if (jackknife) {
832     if (fabs(newgroups*fracsample - (long)(newgroups*fracsample+0.5))
833        > 0.00001) {
834       if (randum(seed)
835           < (newgroups*fracsample - (long)(newgroups*fracsample))
836             /((long)(newgroups*fracsample+1.0)-(long)(newgroups*fracsample)))
837         q = (long)(newgroups*fracsample)+1;
838       else
839         q = (long)(newgroups*fracsample);
840     } else
841       q = (long)(newgroups*fracsample+0.5);
842     r = newgroups;
843     p = q / r;
844     ws = 0;
845     for (i = 0; i < (newgroups); i++) {
846       if (randum(seed) < p) {
847         weight[i]++;
848         ws++;
849         q--;
850       }
851       r--;
852       if (i + 1 < newgroups)
853         p = q / r;
854     }
855   } else if (permute) {
856     for (i = 0; i < (newgroups); i++)
857       weight[i] = 1;
858   } else if (bootstrap) {
859     blocks = fracsample * newgroups / blocksize;
860     for (i = 1; i <= (blocks); i++) {
861       j = (long)(newgroups * randum(seed)) + 1;
862       for (k = 0; k < blocksize; k++) {
863         weight[j - 1]++;
864         j++;
865         if (j > newgroups)
866           j = 1;
867       }
868     }
869   } else             /* case of rewriting data */
870     for (i = 0; i < (newgroups); i++)
871       weight[i] = 1;
872   for (i = 0; i < (newgroups); i++)
873     newerwhere[i] = 0;
874   for (i = 0; i < (newgroups); i++)
875     newerhowmany[i] = 0;
876   newergroups = 0;
877   newersites = 0;
878   for (i = 0; i < (newgroups); i++) {
879     for (j = 1; j <= (weight[i]); j++) {
880       newergroups++;
881       for (k = 1; k <= (newhowmany[i]); k++) {
882         newersites++;
883         newerfactor[newersites - 1] = newergroups;
884       }
885       newerwhere[newergroups - 1] = newwhere[i];
886       newerhowmany[newergroups - 1] = newhowmany[i];
887     }
888   }
889 }  /* bootweights */
890
891
892 void sppermute(long n)
893 { /* permute the species order as given in array sppord */
894   long i, j, k;
895
896   for (i = 1; i <= (spp - 1); i++) {
897     k = (long)((i+1) * randum(seed));
898     j = sppord[n - 1][i];
899     sppord[n - 1][i] = sppord[n - 1][k];
900     sppord[n - 1][k] = j;
901   }
902 }  /* sppermute */
903
904
905 void charpermute(long m, long n)
906 { /* permute the n+1 characters of species m+1 */
907   long i, j, k;
908
909   for (i = 1; i <= (n-1); i++) {
910     k = (long)((i+1) * randum(seed));
911     j = charorder[m][i];
912     charorder[m][i] = charorder[m][k];
913     charorder[m][k] = j;
914   }
915 } /* charpermute */
916
917
918 void writedata()
919 {
920   /* write out one set of bootstrapped sequences */
921   long i, j, k, l, m, n, n2;
922   double x;
923   Char charstate;
924
925   sppord = (long **)Malloc(newergroups*sizeof(long *));
926   for (i = 0; i < (newergroups); i++)
927     sppord[i] = (long *)Malloc(spp*sizeof(long));
928   for (j = 1; j <= spp; j++)
929     sppord[0][j - 1] = j;
930   for (i = 1; i < newergroups; i++) {
931     for (j = 1; j <= (spp); j++)
932       sppord[i][j - 1] = sppord[i - 1][j - 1];
933   }
934   if (!justwts || permute) {
935     if (data == restsites && enzymes)
936       fprintf(outfile, "%5ld %5ld% 4ld\n", spp, newergroups, nenzymes);
937     else if (data == genefreqs)
938       fprintf(outfile, "%5ld %5ld\n", spp, newergroups);
939     else {
940       if ((data == seqs)
941           && !(bootstrap || jackknife || permute || ild || lockhart) && xml)
942         fprintf(outfile, "<alignment>\n");
943       else 
944         if (!(bootstrap || jackknife || permute || ild || lockhart) && nexus) {
945           fprintf(outfile, "#NEXUS\n");
946           fprintf(outfile, "BEGIN DATA;\n");
947           fprintf(outfile, "  DIMENSIONS NTAX=%ld NCHAR=%ld;\n",
948                     spp, newersites);
949           fprintf(outfile, "  FORMAT");
950           if (interleaved)
951             fprintf(outfile, " interleave=yes");
952           else
953             fprintf(outfile, " interleave=no");
954           fprintf(outfile, " DATATYPE=");
955           if (data == seqs) {
956             switch (seq) { 
957               case (dna): fprintf(outfile, "DNA missing=N gap=-"); break;
958               case (rna): fprintf(outfile, "RNA missing=N gap=-"); break;
959               case (protein):
960                 fprintf(outfile, "protein missing=? gap=-");
961                 break;
962               }
963           }
964           if (data == morphology)
965             fprintf(outfile, "STANDARD");
966           fprintf(outfile, ";\n  MATRIX\n");
967           }
968         else fprintf(outfile, "%5ld %5ld\n", spp, newersites);
969     }
970     if (data == genefreqs) {
971       for (i = 0; i < (newergroups); i++)
972         fprintf(outfile, " %3ld", alleles[factorr[newerwhere[i] - 1] - 1]);
973       putc('\n', outfile);
974     }
975   }
976   l = 1;
977   if ((!(bootstrap || jackknife || permute || ild || lockhart | nexus))
978        && ((data == seqs) || (data == restsites))) {
979     interleaved = !interleaved;
980     if (!(bootstrap || jackknife || permute || ild || lockhart) && xml)
981       interleaved = false;
982   }
983   if (interleaved)
984     m = 60;
985   else
986     m = newergroups;
987   do {
988     if (m > newergroups)
989       m = newergroups;
990     for (j = 0; j < spp; j++) {
991       n = 0;
992       if ((l == 1) || (interleaved && nexus)) {
993         if (!(bootstrap || jackknife || permute || ild || lockhart) && xml) {
994           fprintf(outfile, "   <sequence");
995           switch (seq) {
996             case (dna): fprintf(outfile, " type=\"dna\""); break;
997             case (rna): fprintf(outfile, " type=\"rna\""); break;
998             case (protein): fprintf(outfile, " type=\"protein\""); break;
999           }
1000           fprintf(outfile, ">\n");
1001           fprintf(outfile, "      <name>");
1002         }
1003         n2 = nmlngth;
1004         if (!(bootstrap || jackknife || permute || ild || lockhart)
1005             && (xml || nexus)) {
1006           while (nayme[j][n2-1] == ' ')
1007             n2--;
1008         }
1009         if (nexus)
1010           fprintf(outfile, "  ");
1011         for (k = 0; k < n2; k++)
1012           if (nexus && (nayme[j][k] == ' ') && (k < n2))
1013             putc('_', outfile);
1014           else
1015             putc(nayme[j][k], outfile);
1016         if (!(bootstrap || jackknife || permute || ild || lockhart) && xml)
1017           fprintf(outfile, "</name>\n      <data>");
1018       } else {
1019         if (!(bootstrap || jackknife || permute || ild || lockhart) && xml) {
1020           fprintf(outfile, "      ");
1021         }
1022         else {
1023           for (k = 1; k <= nmlngth; k++)
1024             putc(' ', outfile);
1025         }
1026       }
1027       if (!xml) {
1028         for (k = 0; k < nmlngth-n2; k++)
1029           fprintf(outfile, " "); 
1030         fprintf(outfile, " "); 
1031       }
1032       for (k = l - 1; k < m; k++) {
1033         if (permute && j + 1 == 1)
1034           sppermute(newerfactor[n]);    /* we can assume chars not permuted */
1035         for (n2 = -1; n2 <= (newerhowmany[k] - 2); n2++) {
1036           n++;
1037           if (data == genefreqs) {
1038             if (n > 1 && (n & 7) == 1)
1039               fprintf(outfile, "\n              ");
1040             x = nodef[sppord[newerfactor[charorder[j][n - 1]] - 1][j] - 1]
1041                     [newerwhere[charorder[j][k]] + n2];
1042             fprintf(outfile, "%8.5f", x);
1043           } else {
1044             if (!(bootstrap || jackknife || permute || ild || lockhart) && xml
1045                 && (n > 1) && (n % 60 == 1))
1046               fprintf(outfile, "\n            ");
1047             else if (!nexus && !interleaved && (n > 1) && (n % 60 == 1))
1048                 fprintf(outfile, "\n           ");
1049             charstate = nodep[sppord[newerfactor[charorder[j][n - 1]] - 1]
1050                              [j] - 1][newerwhere[charorder[j][k]] + n2];
1051             putc(charstate, outfile);
1052             if (n % 10 == 0 && n % 60 != 0)
1053               putc(' ', outfile);
1054           }
1055         }
1056       }
1057       if (!(bootstrap || jackknife || permute || ild || lockhart ) && xml) {
1058         fprintf(outfile, "</data>\n   </sequence>\n");
1059       }
1060       putc('\n', outfile);
1061     }
1062     if (interleaved) {
1063       if ((m <= newersites) && (newersites > 60))
1064         putc('\n', outfile);
1065       l += 60;
1066       m += 60;
1067     }
1068   } while (interleaved && l <= newersites);
1069   if ((data == seqs) &&
1070       (!(bootstrap || jackknife || permute || ild || lockhart) && xml))
1071     fprintf(outfile, "</alignment>\n");
1072   if (!(bootstrap || jackknife || permute || ild || lockhart) && nexus)
1073     fprintf(outfile, "  ;\nEND;\n");
1074   for (i = 0; i < (newergroups); i++)
1075     free(sppord[i]);
1076   free(sppord);
1077 }  /* writedata */
1078
1079
1080 void writeweights()
1081 { /* write out one set of post-bootstrapping weights */
1082   long j, k, l, m, n, o;
1083
1084   j = 0;
1085   l = 1;
1086   if (interleaved)
1087     m = 60;
1088   else
1089     m = sites;
1090   do {
1091     if(m > sites)
1092       m = sites;
1093     n = 0;
1094     for (k = l - 1; k < m; k++) {
1095       for(o = 0 ; o < how_many[k] ; o++){
1096         if(oldweight[k]==0){
1097           fprintf(outweightfile, "0");
1098           j++;
1099         }
1100         else{
1101           if (weight[k-j] < 10)
1102             fprintf(outweightfile, "%c", (char)('0'+weight[k-j]));
1103           else
1104             fprintf(outweightfile, "%c", (char)('A'+weight[k-j]-10));
1105           n++;
1106           if (!interleaved && n > 1 && n % 60 == 1) {
1107             fprintf(outweightfile, "\n");
1108             if (n % 10 == 0 && n % 60 != 0)
1109               putc(' ', outweightfile);
1110           }
1111         }
1112       }
1113     }
1114     putc('\n', outweightfile);
1115     if (interleaved) {
1116       l += 60;
1117       m += 60;
1118     }
1119   } while (interleaved && l <= sites);
1120 }  /* writeweights */
1121
1122
1123 void writecategories()
1124 {
1125   /* write out categories for the bootstrapped sequences */
1126   long k, l, m, n, n2;
1127   Char charstate;
1128   if(justwts){
1129     if (interleaved)
1130       m = 60;
1131     else
1132       m = sites;
1133     l=1;
1134     do {
1135       if(m > sites)
1136         m = sites;
1137       n=0;
1138       for(k=l-1 ; k < m ; k++){
1139         n++;
1140         if (!interleaved && n > 1 && n % 60 == 1)
1141           fprintf(outcatfile, "\n ");
1142         charstate =  '0' + category[k];
1143         putc(charstate, outcatfile);
1144       }
1145       if (interleaved) {
1146         l += 60;
1147         m += 60;
1148       }
1149     }while(interleaved && l <= sites);
1150     fprintf(outcatfile, "\n");
1151     return;
1152   }
1153
1154   l = 1;
1155   if (interleaved)
1156     m = 60;
1157   else
1158     m = newergroups;
1159   do {
1160     if (m > newergroups)
1161       m = newergroups;
1162     n = 0;
1163     for (k = l - 1; k < m; k++) {
1164       for (n2 = -1; n2 <= (newerhowmany[k] - 2); n2++) {
1165         n++;
1166         if (!interleaved && n > 1 && n % 60 == 1)
1167           fprintf(outcatfile, "\n ");
1168         charstate = '0' + category[newerwhere[k] + n2];
1169         putc(charstate, outcatfile);
1170         if (n % 10 == 0 && n % 60 != 0)
1171           putc(' ', outcatfile);
1172       }
1173     }
1174     if (interleaved) {
1175       l += 60;
1176       m += 60;
1177     }
1178   } while (interleaved && l <= newersites);
1179   fprintf(outcatfile, "\n");
1180 }  /* writecategories */
1181
1182
1183 void writeauxdata(steptr auxdata, FILE *outauxfile)
1184 {
1185   /* write out auxiliary option data (mixtures, ancestors, ect) to
1186      appropriate file.  Samples parralel to data, or just gives one
1187      output entry if justwts is true */
1188   long k, l, m, n, n2;
1189   Char charstate;
1190
1191   /* if we just output weights (justwts), and this is first set
1192      just output the data unsampled */
1193   if(justwts){
1194     if(firstrep){
1195       if (interleaved)
1196         m = 60;
1197       else
1198         m = sites;
1199       l=1;
1200       do {
1201         if(m > sites)
1202           m = sites;
1203         n = 0;
1204         for(k=l-1 ; k < m ; k++){
1205         n++;
1206         if (!interleaved && n > 1 && n % 60 == 1)
1207           fprintf(outauxfile, "\n ");
1208           charstate = auxdata[k];
1209           putc(charstate, outauxfile);
1210         }
1211         if (interleaved) {
1212           l += 60;
1213           m += 60;
1214         }
1215       }while(interleaved && l <= sites);
1216       fprintf(outauxfile, "\n");
1217     }
1218     return;
1219   }
1220
1221   l = 1;
1222   if (interleaved)
1223     m = 60;
1224   else
1225     m = newergroups;
1226   do {
1227     if (m > newergroups)
1228       m = newergroups;
1229     n = 0;
1230     for (k = l - 1; k < m; k++) {
1231       for (n2 = -1; n2 <= (newerhowmany[k] - 2); n2++) {
1232         n++;
1233         if (!interleaved && n > 1 && n % 60 == 1)
1234           fprintf(outauxfile, "\n ");
1235         charstate = auxdata[newerwhere[k] + n2];
1236         putc(charstate, outauxfile);
1237         if (n % 10 == 0 && n % 60 != 0)
1238           putc(' ', outauxfile);
1239       }
1240     }
1241     if (interleaved) {
1242       l += 60;
1243       m += 60;
1244     }
1245   } while (interleaved && l <= newersites);
1246   fprintf(outauxfile, "\n");
1247 }  /* writeauxdata */
1248
1249 void writefactors(void)
1250 {
1251   long k, l, m, n, prevfact, writesites;
1252   char symbol;
1253   steptr wfactor;
1254
1255   if(!justwts || firstrep){
1256     if(justwts){
1257       writesites = sites;
1258       wfactor = factorr;
1259     } else {
1260       writesites = newersites;
1261       wfactor = newerfactor;
1262     }
1263     prevfact = wfactor[0];
1264     symbol = '+';
1265     if (interleaved)
1266       m = 60;
1267     else
1268       m = writesites;
1269     l=1;
1270     do {
1271       if(m > writesites)
1272         m = writesites;
1273       n = 0;
1274       for(k=l-1 ; k < m ; k++){
1275         n++;
1276         if (!interleaved && n > 1 && n % 60 == 1)
1277           fprintf(outfactfile, "\n ");
1278         if(prevfact != wfactor[k]){
1279           symbol = (symbol == '+') ? '-' : '+';
1280           prevfact = wfactor[k];
1281         }
1282         putc(symbol, outfactfile);
1283         if (n % 10 == 0 && n % 60 != 0)
1284           putc(' ', outfactfile);
1285       }
1286       if (interleaved) {
1287         l += 60;
1288         m += 60;
1289       }
1290     }while(interleaved && l <= writesites);
1291     fprintf(outfactfile, "\n");
1292   }
1293 } /* writefactors */
1294
1295
1296 void bootwrite()
1297 { /* does bootstrapping and writes out data sets */
1298   long i, j, rr, repdiv10;
1299
1300   if (!(bootstrap || jackknife || permute || ild || lockhart))
1301     reps = 1;
1302   repdiv10 = reps / 10;
1303   if (repdiv10 < 1)
1304     repdiv10 = 1;
1305   if (progress)
1306     putchar('\n');
1307   for (rr = 1; rr <= (reps); rr++) {
1308     for (i = 0; i < spp; i++)
1309       for (j = 0; j < maxnewsites; j++)
1310         charorder[i][j] = j;
1311     if(rr==1)
1312       firstrep = true;
1313     else
1314       firstrep = false;
1315     if (ild) {
1316       charpermute(0, maxnewsites);
1317       for (i = 1; i < spp; i++)
1318         for (j = 0; j < maxnewsites; j++)
1319           charorder[i][j] = charorder[0][j];
1320     }
1321     if (lockhart)
1322       for (i = 0; i < spp; i++)
1323         charpermute(i, maxnewsites);
1324     bootweights();
1325     if (!justwts || permute || ild || lockhart)
1326       writedata();
1327     if (justwts && !(permute || ild || lockhart))
1328       writeweights();
1329     if (categories)
1330       writecategories();
1331     if (factors)
1332       writefactors();
1333     if (mixture)
1334       writeauxdata(mixdata, outmixfile);
1335     if (ancvar)
1336       writeauxdata(ancdata, outancfile);
1337     if (progress && (bootstrap || jackknife || permute || ild || lockhart)
1338           && ((reps < 10) || rr % repdiv10 == 0)) {
1339       printf("completed replicate number %4ld\n", rr);
1340 #ifdef WIN32
1341       phyFillScreenColor();
1342 #endif
1343     }
1344   }
1345   if (progress) {
1346     if (justwts)
1347       printf("\nOutput weights written to file \"%s\"\n\n", outweightfilename);
1348     else
1349       printf("\nOutput written to file \"%s\"\n\n", outfilename);
1350   }
1351 }  /* bootwrite */
1352
1353
1354 void seqboot_inputaux(steptr dataptr, FILE* auxfile)
1355 { /* input auxiliary option data (mixtures, ancestors, ect) for 
1356      new style input, assumes that data is correctly formated
1357      in input files*/
1358   long i, j, k;
1359   Char ch;
1360
1361   j = 0;
1362   k = 1;
1363   for (i = 0; i < (sites); i++) {
1364     do {
1365       if (eoln(auxfile))
1366         scan_eoln(auxfile);
1367       ch = gettc(auxfile);
1368       if (ch == '\n')
1369         ch = ' ';
1370     } while (ch == ' ');
1371     dataptr[i] = ch;
1372   }
1373   scan_eoln(auxfile);
1374 }  /* seqboot_inputaux */
1375
1376
1377 int main(int argc, Char *argv[])
1378 {  /* Read in sequences or frequencies and bootstrap or jackknife them */
1379 #ifdef MAC
1380   argc = 1;                /* macsetup("SeqBoot","");                */
1381   argv[0] = "SeqBoot";
1382 #endif
1383   init(argc,argv);
1384   openfile(&infile, INFILE, "input file", "r", argv[0], infilename);
1385   ibmpc = IBMCRT;
1386   ansi = ANSICRT;
1387   doinput(argc, argv);
1388   bootwrite();
1389   FClose(infile);
1390   if (weights)
1391     FClose(weightfile);
1392   if (categories) {
1393     FClose(catfile);
1394     FClose(outcatfile);
1395   }
1396   if(mixture)
1397     FClose(outmixfile);
1398   if(ancvar)
1399     FClose(outancfile);
1400   if (justwts && !permute) {
1401     FClose(outweightfile);
1402   }
1403   else
1404     FClose(outfile);
1405 #ifdef MAC
1406   fixmacfile(outfilename);
1407   if (justwts && !permute)
1408     fixmacfile(outweightfilename);
1409   if (categories)
1410     fixmacfile(outcatfilename);
1411   if (mixture)
1412     fixmacfile(outmixfilename);
1413 #endif
1414   printf("Done.\n\n");
1415 #ifdef WIN32
1416   phyRestoreConsoleAttributes();
1417 #endif
1418   return 0;
1419 }