Debian Codegraph @

NAST-iEr/NAST-iEr.c

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <unistd.h>
5
6
7 static int DEBUG = 0;
8
9 /* data structures */
10 typedef struct {
11 int score;
12 int prev; } Cell;
13
14 typedef struct {
15 int x;
16 int y; } Point;
17
18 typedef struct {
19 int G;
20 int A;
21 int T;
22 int C;
23 int gap;
24 } ntCounts;
25
26
27 void add_sequence_to_profile(ntCounts* template, char* seq, int lastIndex);
28 int extract_profile_from_file(char* filename, ntCounts* template); // returns alignment length
29 void report_profile_consensus(ntCounts* profile, int alignmentLength);
30
31 /* prototypes */
32 void usage (char*);
33 void extract_sequence_from_file (char* filename, char* acc, char* sequence);
34 void align_NASTy (ntCounts* templateSeq, int fixedAlignmentLength, char* querySeq, char* templateAlignment, char* queryAlignment);
35 Cell** build_matrix (int x, int y); /* builds a 2D array of cell structs */
36 void init_matrix (Cell** matrix, int x, int y); // initializes the matrix cell values and boundary conditions.
37 void populate_matrix (Cell** matrix, int x, int y, ntCounts* templateSeq, char* querySeq); // builds the DP matrix, assigning scores and pointers.
38 Point get_highest_scoring_cell_coordinates (Cell** matrix, int x, int y); // examines boundary conditions and finds highest scoring global alignment
39 void extract_aligned_sequences (Cell** matrix, int x, int y, Point p, ntCounts* templateSeq, char* querySeq, char* templateAlignment, char* queryAlignment);
40 char* strrev (char* str); // reverse a string in-place.
41 void print_FASTA (char* acc, char* sequence);
42 int compute_match_score(ntCounts n, char c);
43 char get_max_char(ntCounts n);
44 void report_ntCounts_contents(ntCounts n);
45
46
47 /* global vars */
48 static int MAX_SEQ_LENGTH = 20000;
49 static int MAX_ACC_LENGTH = 100;
50 static int FASTA_LENGTH = 60;
51
52 /* scores for computing alignment */
53 static int MATCH = 5;
54 static int MISMATCH = -4;
55 static int GAP = -4;
56
57 /* directions for trace in the matrix */
58 static int UP = 1;
59 static int DIAG = 2;
60 static int LEFT = 3;
61
62
63
64
65 int main (int argc, char* argv[]) {
66
67 /* var declarations */
68 char* templateSeqFilename;
69 char* querySeqFilename;
70
71 int print_both_alignments = 0; // by default, just print the query in NAST format.
72
73 ntCounts templateSeq [MAX_SEQ_LENGTH];
74 int i;
75 for (i = 0; i < MAX_SEQ_LENGTH; i++) {
76 ntCounts* n = &templateSeq[i];
77 n->G = n->A = n->T = n->C = n->gap = 0;
78 }
79
80 char querySeq [MAX_SEQ_LENGTH];
81
82 char queryAcc [MAX_ACC_LENGTH];
83
84 char alignedTemplateSeq [2 * MAX_SEQ_LENGTH];
85 char alignedQuerySeq [2 * MAX_SEQ_LENGTH];
86
87 // other option processing
88 int c;
89
90 while ((c = getopt (argc, argv, "M:N:G:b")) != -1) {
91 switch (c) {
92 case 'M':
93 MATCH = atoi(optarg);
94 break;
95 case 'N':
96 MISMATCH = atoi(optarg);
97 break;
98 case 'G':
99 GAP = atoi(optarg);
100 break;
101 case 'b':
102 print_both_alignments = 1;
103 break;
104
105 case '?':
106 if (isprint (optopt)) {
107 fprintf (stderr, "Unknown option `-%c'.\n", optopt);
108 }
109 else {
110 fprintf (stderr,
111 "Unknown option character `\\x%x'.\n",
112 optopt);
113 }
114 }
115 }
116
117 if (argc < optind + 1) {
118 usage(argv[0]);
119 exit(1);
120 }
121
122 templateSeqFilename = argv[optind];
123 querySeqFilename = argv[optind + 1];
124
125 fprintf(stderr, "Alignment parameters:\nMATCH: %d\nMISMATCH: %d\nGAP: %d\n\n", MATCH, MISMATCH, GAP);
126
127 /* get sequences from files */
128 int fixedAlignmentLength = extract_profile_from_file(templateSeqFilename, templateSeq);
129 extract_sequence_from_file(querySeqFilename, queryAcc, querySeq);
130
131 if (DEBUG) {
132 printf ("Parsed profile of length: %d\n", fixedAlignmentLength);
133 report_profile_consensus(templateSeq, fixedAlignmentLength);
134
135 printf ("\n\nAnd parsed query sequence acc: %s:\n%s\n\n", queryAcc, querySeq);
136
137 }
138
139
140 /* perform NASTy alignment */
141 align_NASTy(templateSeq, fixedAlignmentLength, querySeq, alignedTemplateSeq, alignedQuerySeq);
142
143 /* output the aligned sequences in fasta format */
144 if (print_both_alignments) {
145 print_FASTA("template", alignedTemplateSeq);
146 }
147
148 print_FASTA(queryAcc, alignedQuerySeq);
149
150 return(0);
151 }
152
153
154
155
156
157
158
159 void usage (char* progname) {
160 fprintf(stderr, "\n\nusage: %s [options] templateSeqFilename querySeqFilename\n\n", progname);
161 fprintf(stderr, "Options:\n");
162 fprintf(stderr, "\t-M Match score (default: 5)\n");
163 fprintf(stderr, "\t-N Mismatch score (default: -4)\n");
164 fprintf(stderr, "\t-G Gap penalty (default: -4)\n\n");
165 fprintf(stderr, "\t-b print both the template profile consensus and the query in NAST format\n\n\n");
166
167 }
168
169
170 int extract_profile_from_file(char* filename, ntCounts* templateSeq) {
171 FILE* fp;
172 int letter;
173 int pos = -1;
174
175 char currSeq [MAX_SEQ_LENGTH];
176
177
178
179 if ( (fp = fopen(filename, "r")) == NULL) {
180 fprintf (stderr, "Error, cannot open filename %s", filename);
181 exit(2);
182 }
183
184 while ( (letter = getc(fp)) != EOF) {
185 if (letter == '>') {
186 if (pos != -1) {
187 add_sequence_to_profile(templateSeq, currSeq, pos);
188 }
189 pos = -1; // reinit
190
191 // advance the line
192 while ( (letter = getc(fp)) != '\n') { ; }
193 }
194 else if (letter != ' ' && letter != '\n') {
195 pos++;
196 currSeq[pos] = letter;
197 }
198 }
199
200 // get last one
201 add_sequence_to_profile(templateSeq, currSeq, pos);
202
203 fclose(fp);
204
205 return(pos + 1);
206 }
207
208
209
210 void extract_sequence_from_file (char* filename, char* acc, char* sequence) {
211 FILE* fp;
212 int letter;
213 int pos = -1;
214
215 if ( (fp = fopen(filename, "r")) == NULL) {
216 fprintf (stderr, "Error, cannot open filename %s", filename);
217 exit(2);
218 }
219
220 /* read in the accession */
221 if ( (letter = getc(fp)) != '>') {
222 fprintf (stderr, "Error, filename %s does contain a fasta sequence beginning with '>'", filename);
223 exit(3);
224 }
225 while ( ((letter = getc(fp)) != EOF) && (letter != ' ' && letter != '\n')) {
226 acc[++pos] = letter;
227 }
228 acc[++pos] = '\0'; // terminate the acc string.
229
230 /* read in rest of sequence */
231 while (letter != '\n') {
232 // advance to next line.
233 letter = getc(fp);
234 }
235 pos = -1; // reset to just before sequence
236 while ( (letter = getc(fp)) != EOF) {
237 if (letter != '\n' && letter != ' ') {
238 sequence[++pos] = letter;
239 }
240 }
241 sequence[++pos] = '\0';
242
243 fclose(fp);
244 }
245
246
247 void align_NASTy (ntCounts* templateSeq, int templateSeqLength, char* querySeq, char* templateAlignment, char* queryAlignment) {
248
249 int querySeqLength = strlen(querySeq);
250
251 if (DEBUG) {
252 fprintf (stdout, "lengths:\ntemplate: %d\nquery: %d\n\n", templateSeqLength, querySeqLength);
253 }
254 /* matrix boundaries */
255 int x = templateSeqLength;
256 int y = querySeqLength;
257
258 Cell** matrix = build_matrix(x, y); // need seqlength + 1 for cols and rows, the extra for the boundaries.
259 populate_matrix(matrix, x, y, templateSeq, querySeq);
260
261 Point p = get_highest_scoring_cell_coordinates(matrix, x, y);
262
263 extract_aligned_sequences(matrix, x, y, p, templateSeq, querySeq, templateAlignment, queryAlignment);
264
265
266 }
267
268
269 void populate_matrix (Cell** matrix, int x, int y, ntCounts* templateSeq, char* querySeq) {
270
271 int i, j;
272
273 for (i = 1; i <= x; i++) {
274 ntCounts a = templateSeq[i-1];
275 int numChars = a.G + a.A + a.T + a.C;
276 int numGaps = a.gap;
277
278
279 for (j = 1; j <= y; j++) {
280
281 char b = querySeq[j-1];
282
283 if (DEBUG > 1) {
284 printf ("computing match score of NTs ");
285 report_ntCounts_contents(a);
286 printf ("compared to char: %c\n", b);
287 }
288
289
290 // score the match (or mismatch)
291 int max_score = compute_match_score(a, b) + matrix[i-1][j-1].score;
292 int max_dir = DIAG; // init for this round.
293
294 // insert gap against a template character, penalized for number of non-gap characters. If all gap, there is no penalty at all.
295 int score = matrix[i-1][j].score + (numChars * GAP);
296 if (score > max_score) {
297 max_score = score;
298 max_dir = LEFT;
299 }
300
301
302 if (DEBUG > 1) {
303 fprintf (stdout, "max score(%d,%d): %i, %i\n", i, j, max_score, max_dir);
304 }
305
306 matrix[i][j].score = max_score;
307 matrix[i][j].prev = max_dir;
308
309 //fprintf(stdout, "setting matrix[%d][%d] = %d\n", i, j, max_dir);
310
311 } // end of for j
312
313 } // end of for i
314
315 }
316
317 Cell** build_matrix (int x, int y) {
318
319 Cell** matrix = (Cell**) malloc (sizeof(Cell*) * (x+1));
320
321 int i;
322 for (i = 0; i <= x; i++) {
323 matrix[i] = (Cell*) malloc (sizeof(Cell) * (y+1));
324 }
325
326
327 init_matrix(matrix, x, y);
328
329
330
331 return(matrix);
332 }
333
334
335 void init_matrix (Cell** matrix, int x, int y) {
336
337 /* init all cells */
338 int i,j;
339
340 for (i = 0; i <= x; i++) {
341
342 for (j = 0; j <= y; j++) {
343 Cell* cell = &(matrix[i][j]);
344 cell->score = 0;
345 cell->prev = 0;
346 }
347 }
348
349 /* establish boundary conditions for not penalizing end gaps */
350 for (i = 1; i <= x; i++) {
351 matrix[i][0].prev = LEFT;
352 }
353 for (j = 1; j <= y; j++) {
354 matrix[0][j].prev = UP;
355 }
356
357
358 }
359
360
361 Point get_highest_scoring_cell_coordinates (Cell** matrix, int x, int y) {
362
363 int best_score = -9999999; // short for minus infinity.
364 Point p;
365 int i,j;
366
367
368 for (i = 1; i <= x; i++) {
369 int score = matrix[i][y].score;
370 if (score > best_score) {
371 best_score = score;
372 p.x = i;
373 p.y = y;
374 }
375 }
376
377 for (j = 1; j <= y; j++) {
378 int score = matrix[x][j].score;
379 if (score > best_score) {
380 best_score = score;
381 p.x = x;
382 p.y = j;
383 }
384 }
385
386 fprintf (stderr, "Highest score: %d\n", best_score);
387
388 return(p);
389 }
390
391
392 void extract_aligned_sequences (Cell** matrix, int x, int y, Point p, ntCounts* templateSeq, char* querySeq, char* templateAlignment, char* queryAlignment) {
393
394 int pos_x = p.x;
395 int pos_y = p.y;
396
397 int align_pos = 0;
398
399 if (DEBUG) {
400 fprintf (stdout, "beginning traceback at (%d, %d)\n", pos_x, pos_y);
401 }
402
403 /* build the 3' end-gapped portion of the alignment. */
404
405 int i,j;
406 if (pos_x < x) { // add gap chars at the end of the query alignment, populate reference chars.
407 for (i = x; i > pos_x; i--) {
408 templateAlignment[align_pos] = get_max_char(templateSeq[i-1]);
409 queryAlignment[align_pos] = '.';
410 align_pos++;
411 }
412 }
413
414
415 /* begin traceback of global alignment */
416
417 Cell c = matrix[pos_x][pos_y];
418
419 while (c.prev != 0) {
420
421 if (DEBUG) {
422 fprintf(stdout, "matrix[%d][%d] == %d\n", pos_x, pos_y, c.prev);
423 }
424
425 char a,b;
426
427 if (c.prev == DIAG) {
428 // matching current positions.
429 a = get_max_char(templateSeq[pos_x-1]);
430 b = querySeq[pos_y-1];
431 pos_x--;
432 pos_y--;
433 }
434
435 else if (c.prev == UP) {
436 // no gaps added to end of template, even at ends
437 if (pos_x != 0) {
438 fprintf(stderr, "trying to add gaps to the template and query sequence not fully traversed (pos_x: %d)", pos_x);
439 exit(1);
440 }
441 break;
442
443
444 }
445
446 else if (c.prev == LEFT) {
447 // gap in query sequence
448 char gapchar = (pos_y == 0) ? '.' : '-';
449 a = get_max_char(templateSeq[pos_x-1]);
450 b = gapchar;
451 pos_x--;
452 }
453
454 else {
455 fprintf (stderr, "Error, cannot determine matrix direction: %d at (%d, %d)\n", c.prev, pos_x, pos_y);
456 exit(10);
457 }
458
459
460 templateAlignment[align_pos] = a;
461 queryAlignment[align_pos] = b;
462 align_pos++;
463
464 c = matrix[pos_x][pos_y]; // reset for next round.
465
466 if (DEBUG > 1) {
467 fprintf (stdout, "assigning alignment [%d] = %c <-> %c\n", align_pos, a, b);
468 fprintf (stderr, "alignpos: %d, (%d, %d)\n", align_pos, pos_x, pos_y);
469 }
470 }
471
472 // terminate the alignment strings.
473 templateAlignment[align_pos] = '\0';
474 queryAlignment[align_pos] = '\0';
475
476 int templateAlignmentLength = strlen(templateAlignment);
477 int queryAlignmentLength = strlen(queryAlignment);
478
479 if (DEBUG) {
480 fprintf (stdout, "templateLen: %d\n", templateAlignmentLength);
481 fprintf (stdout, "queryAlignmentLen: %d\n", queryAlignmentLength);
482 }
483
484 if (templateAlignmentLength != queryAlignmentLength) {
485 fprintf (stderr, "Error, template alignment length %d != query alignment length %d",
486 templateAlignmentLength, queryAlignmentLength);
487 exit(1);
488 }
489
490
491 templateAlignment = strrev(templateAlignment);
492 queryAlignment = strrev(queryAlignment);
493
494 }
495
496 char* strrev(char* str) {
497
498 int i,j;
499
500 for (i = 0, j = strlen(str) - 1; i < j; i++, j--) {
501
502 char c = str[j];
503 str[j] = str[i];
504 str[i] = c;
505 }
506
507 return str;
508 }
509
510
511 void print_FASTA (char* acc, char* sequence) {
512
513 fprintf (stdout, ">%s\n", acc);
514 int i;
515 for (i = 0; i < strlen(sequence); i++) {
516 if (i != 0 && i % FASTA_LENGTH == 0) {
517 fprintf (stdout, "\n"); // spacer
518 }
519 fprintf (stdout, "%c", sequence[i]);
520 }
521 fprintf (stdout, "\n");
522
523 }
524
525
526 int compute_match_score (ntCounts n, char c) {
527
528
529 if (c == 'g' || c == 'G') {
530 return (MATCH * n.G + MISMATCH * (n.A + n.T + n.C + n.gap));
531 }
532 else if (c == 'a' || c == 'A') {
533 return (MATCH * n.A + MISMATCH * (n.G + n.T + n.C + n.gap));
534 }
535 else if (c == 't' || c == 'T') {
536 return (MATCH * n.T + MISMATCH * (n.G + n.A + n.C + n.gap));
537 }
538 else if (c == 'c' || c == 'C') {
539 return (MATCH * n.C + MISMATCH * (n.G + n.A + n.T + n.gap));
540 }
541 else {
542
543 // pretend the character is an A
544 return (MATCH * n.A + MISMATCH * (n.G + n.T + n.C + n.gap));
545
546 //fprintf (stderr, "Error, do not recognize character: %c\n", c);
547 //exit(3);
548 }
549
550 }
551
552
553 char get_max_char(ntCounts n) {
554 int max = n.G;
555 char max_char = 'G';
556
557 if (n.A > max) {
558 max = n.A;
559 max_char = 'A';
560 }
561 else if (n.T > max) {
562 max = n.T;
563 max_char = 'T';
564 }
565 else if (n.C > max) {
566 max = n.C;
567 max_char = 'C';
568 }
569 else if (n.gap > max) {
570 max = n.gap;
571 max_char = '-';
572 }
573
574 return (max_char);
575 }
576
577 void add_sequence_to_profile(ntCounts* template, char* seq, int lastIndex) {
578
579 if (DEBUG) {
580 printf ("Adding sequence to profile:\n%s\n\n", seq);
581 }
582
583
584 int i;
585
586 for (i = 0; i <= lastIndex; i++) {
587 char c = seq[i];
588 //printf ("char: %c\n", c);
589 ntCounts* n = &template[i];
590 if (c == 'g' || c == 'G') {
591 n->G++;
592 }
593 else if (c == 'a' || c == 'A') {
594 n->A++;
595 }
596 else if (c == 't' || c == 'T') {
597 n->T++;
598 }
599 else if (c == 'c' || c == 'C') {
600 n->C++;
601 }
602 else if (c == '.' || c == '-') {
603 n->gap++;
604 }
605 else {
606 //fprintf (stderr, "Error, do not recognize char: %c, treating as an \'A\'\n", c);
607 // exit(3);
608 }
609 }
610 }
611
612
613 void report_profile_consensus (ntCounts* profile, int alignmentLength) {
614
615 int i;
616 for (i = 0; i < alignmentLength; i++) {
617 printf ("%c", get_max_char(profile[i]));
618 }
619 printf ("\n\n");
620
621 return;
622 }
623
624 void report_ntCounts_contents (ntCounts n) {
625
626 printf ("G:%d A:%d T:%d C:%d gap:%d\n", n.G, n.A, n.T, n.C, n.gap);
627
628 }