1 /**
2 * This file is a container for all plotting layout algorithms
3 *
4 * c Ronny Lorenz
5 * The ViennaRNA Package
6 */
7
8 #ifdef HAVE_CONFIG_H
9 #include "config.h"
10 #endif
11
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <math.h>
15 #include <string.h>
16
17 #include "ViennaRNA/utils/basic.h"
18 #include "ViennaRNA/gquad.h"
19
20 #include "ViennaRNA/plotting/layouts.h"
21
22 #ifndef VRNA_DISABLE_BACKWARD_COMPATIBILITY
23
24 PUBLIC int rna_plot_type = 1; /* 0 = simple, 1 = naview, 2 = circular plot */
25
26 #endif
27
28
29 #ifndef PI
30 #define PI 3.141592654
31 #endif
32 #define PIHALF PI / 2.
33
34
35 /*
36 #################################
37 # PRIVATE FUNCTION DECLARATIONS #
38 #################################
39 */
40
41 PRIVATE struct vrna_plot_layout_s *
42 rna_layout(const char *structure,
43 unsigned int plot_type,
44 void *options);
45
46
47 PRIVATE int
48 coords_simple(const short *pt,
49 float **x,
50 float **y);
51
52
53 PRIVATE void
54 loop(const short *pair_table,
55 int i,
56 int j,
57 float *angle,
58 int *stack_size,
59 int *loop_size,
60 int *stk,
61 int *lp);
62
63
64 PRIVATE int
65 coords_circular(const short *pt,
66 float **x,
67 float **y);
68
69
70 /*
71 #################################
72 # BEGIN OF FUNCTION DEFINITIONS #
73 #################################
74 */
75 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout(const char * structure,unsigned int plot_type)76 vrna_plot_layout(const char *structure,
77 unsigned int plot_type)
78 {
79 if (structure)
80 return rna_layout(structure, plot_type, NULL);
81
82 return NULL;
83 }
84
85
86 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout_simple(const char * structure)87 vrna_plot_layout_simple(const char *structure)
88 {
89 return vrna_plot_layout(structure, VRNA_PLOT_TYPE_SIMPLE);
90 }
91
92
93 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout_naview(const char * structure)94 vrna_plot_layout_naview(const char *structure)
95 {
96 return vrna_plot_layout(structure, VRNA_PLOT_TYPE_NAVIEW);
97 }
98
99
100 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout_circular(const char * structure)101 vrna_plot_layout_circular(const char *structure)
102 {
103 return vrna_plot_layout(structure, VRNA_PLOT_TYPE_CIRCULAR);
104 }
105
106
107 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout_turtle(const char * structure)108 vrna_plot_layout_turtle(const char *structure)
109 {
110 return vrna_plot_layout(structure, VRNA_PLOT_TYPE_TURTLE);
111 }
112
113
114 PUBLIC struct vrna_plot_layout_s *
vrna_plot_layout_puzzler(const char * structure,vrna_plot_options_puzzler_t * options)115 vrna_plot_layout_puzzler(const char *structure,
116 vrna_plot_options_puzzler_t *options)
117 {
118 if (structure)
119 return rna_layout(structure, VRNA_PLOT_TYPE_PUZZLER, (void *)options);
120
121 return NULL;
122 }
123
124
125 PUBLIC void
vrna_plot_layout_free(struct vrna_plot_layout_s * layout)126 vrna_plot_layout_free(struct vrna_plot_layout_s *layout)
127 {
128 if (layout) {
129 free(layout->x);
130 free(layout->y);
131 free(layout->arcs);
132 free(layout);
133 }
134 }
135
136
137 PUBLIC int
vrna_plot_coords(const char * structure,float ** x,float ** y,int plot_type)138 vrna_plot_coords(const char *structure,
139 float **x,
140 float **y,
141 int plot_type)
142 {
143 if (structure) {
144 int ret = 0;
145 short *pt = vrna_ptable(structure);
146
147 ret = vrna_plot_coords_pt(pt, x, y, plot_type);
148
149 free(pt);
150
151 return ret;
152 }
153
154 if (x)
155 *x = NULL;
156
157 if (y)
158 *y = NULL;
159
160 return 0;
161 }
162
163
164 PUBLIC int
vrna_plot_coords_pt(const short * pt,float ** x,float ** y,int plot_type)165 vrna_plot_coords_pt(const short *pt,
166 float **x,
167 float **y,
168 int plot_type)
169 {
170 if ((pt) && (x) && (y)) {
171 switch (plot_type) {
172 case VRNA_PLOT_TYPE_SIMPLE:
173 return coords_simple(pt, x, y);
174
175 case VRNA_PLOT_TYPE_NAVIEW:
176 return vrna_plot_coords_naview_pt(pt, x, y);
177
178 case VRNA_PLOT_TYPE_CIRCULAR:
179 return coords_circular(pt, x, y);
180
181 case VRNA_PLOT_TYPE_TURTLE:
182 return vrna_plot_coords_turtle_pt(pt, x, y, NULL);
183
184 case VRNA_PLOT_TYPE_PUZZLER:
185 return vrna_plot_coords_puzzler_pt(pt, x, y, NULL, NULL);
186 }
187 }
188
189 if (x)
190 *x = NULL;
191
192 if (y)
193 *y = NULL;
194
195 return 0;
196 }
197
198
199 PUBLIC int
vrna_plot_coords_simple(const char * structure,float ** x,float ** y)200 vrna_plot_coords_simple(const char *structure,
201 float **x,
202 float **y)
203 {
204 return vrna_plot_coords(structure, x, y, VRNA_PLOT_TYPE_SIMPLE);
205 }
206
207
208 PUBLIC int
vrna_plot_coords_simple_pt(const short * pt,float ** x,float ** y)209 vrna_plot_coords_simple_pt(const short *pt,
210 float **x,
211 float **y)
212 {
213 return vrna_plot_coords_pt(pt, x, y, VRNA_PLOT_TYPE_SIMPLE);
214 }
215
216
217 PUBLIC int
vrna_plot_coords_circular(const char * structure,float ** x,float ** y)218 vrna_plot_coords_circular(const char *structure,
219 float **x,
220 float **y)
221 {
222 return vrna_plot_coords(structure, x, y, VRNA_PLOT_TYPE_CIRCULAR);
223 }
224
225
226 PUBLIC int
vrna_plot_coords_circular_pt(const short * pt,float ** x,float ** y)227 vrna_plot_coords_circular_pt(const short *pt,
228 float **x,
229 float **y)
230 {
231 return vrna_plot_coords_pt(pt, x, y, VRNA_PLOT_TYPE_CIRCULAR);
232 }
233
234
235 /*
236 #####################################
237 # BEGIN OF STATIC HELPER FUNCTIONS #
238 #####################################
239 */
240 PRIVATE struct vrna_plot_layout_s *
rna_layout(const char * structure,unsigned int plot_type,void * options)241 rna_layout(const char *structure,
242 unsigned int plot_type,
243 void *options)
244 {
245 struct vrna_plot_layout_s *layout;
246 short *pt, *pt_g;
247 unsigned int i, n;
248 int xmin, xmax, ymin, ymax, ee, gb, ge, Lg, l[3], r;
249
250
251 n = strlen(structure);
252 layout = (struct vrna_plot_layout_s *)vrna_alloc(sizeof(struct vrna_plot_layout_s));
253 layout->length = n;
254 layout->x = NULL;
255 layout->y = NULL;
256 layout->arcs = NULL;
257
258 /* convert dot-bracket string to pair table */
259 pt = vrna_ptable(structure);
260 pt_g = vrna_ptable_copy(pt);
261
262 /* account for possible G-Quadruplexes in dot-bracket string */
263 ge = 0;
264 while ((ee = parse_gquad(structure + ge, &Lg, l)) > 0) {
265 ge += ee;
266 gb = ge - Lg * 4 - l[0] - l[1] - l[2] + 1;
267 /* add pseudo-base pair encloding gquad */
268 for (i = 0; i < (unsigned int)Lg; i++) {
269 pt_g[ge - i] = gb + i;
270 pt_g[gb + i] = ge - i;
271 }
272 }
273
274 switch (plot_type) {
275 case VRNA_PLOT_TYPE_SIMPLE:
276 i = coords_simple(pt_g,
277 &(layout->x),
278 &(layout->y));
279 break;
280
281 case VRNA_PLOT_TYPE_CIRCULAR:
282 r = 3 * n;
283 i = coords_circular(pt_g,
284 &(layout->x),
285 &(layout->y));
286
287 for (i = 0; i < n; i++) {
288 layout->x[i] *= r;
289 layout->x[i] += r;
290 layout->y[i] *= r;
291 layout->y[i] += r;
292 }
293 break;
294
295 case VRNA_PLOT_TYPE_TURTLE:
296 i = vrna_plot_coords_turtle_pt(pt,
297 &(layout->x),
298 &(layout->y),
299 &(layout->arcs));
300 break;
301
302 case VRNA_PLOT_TYPE_PUZZLER:
303 i = vrna_plot_coords_puzzler_pt(pt,
304 &(layout->x),
305 &(layout->y),
306 &(layout->arcs),
307 (vrna_plot_options_puzzler_t *)options);
308 break;
309
310 default:
311 i = vrna_plot_coords_naview_pt(pt_g,
312 &(layout->x),
313 &(layout->y));
314 break;
315 }
316
317 if (i != n)
318 vrna_message_warning("strange things happening in vrna_plot_layout*()...");
319
320 /* adjust bounding box coordinates */
321 xmin = xmax = layout->x[0];
322 ymin = ymax = layout->y[0];
323
324 for (i = 1; i < n; i++) {
325 xmin = layout->x[i] < xmin ? layout->x[i] : xmin;
326 xmax = layout->x[i] > xmax ? layout->x[i] : xmax;
327 ymin = layout->y[i] < ymin ? layout->y[i] : ymin;
328 ymax = layout->y[i] > ymax ? layout->y[i] : ymax;
329 }
330
331 layout->bbox[0] = xmin;
332 layout->bbox[1] = ymin;
333 layout->bbox[2] = xmax;
334 layout->bbox[3] = ymax;
335
336 return layout;
337 }
338
339
340 PRIVATE int
coords_simple(const short * pt,float ** x,float ** y)341 coords_simple(const short *pt,
342 float **x,
343 float **y)
344 {
345 float INIT_ANGLE = 0.; /* initial bending angle */
346 float INIT_X = 100.; /* coordinate of first digit */
347 float INIT_Y = 100.; /* see above */
348 float RADIUS = 15.;
349
350 int i, length;
351 float alpha;
352
353 float *angle;
354 int *loop_size, *stack_size;
355 int lp, stk;
356
357 length = pt[0];
358 angle = (float *)vrna_alloc((length + 5) * sizeof(float));
359 loop_size = (int *)vrna_alloc(16 + (length / 5) * sizeof(int));
360 stack_size = (int *)vrna_alloc(16 + (length / 5) * sizeof(int));
361 lp = stk = 0;
362
363 *x = (float *)vrna_alloc(sizeof(float) * (length + 1));
364 *y = (float *)vrna_alloc(sizeof(float) * (length + 1));
365
366 loop(pt, 0, length, angle, stack_size, loop_size, &stk, &lp);
367
368 loop_size[lp] -= 2; /* correct for cheating with function loop */
369
370 alpha = INIT_ANGLE;
371 (*x)[0] = INIT_X;
372 (*y)[0] = INIT_Y;
373
374 for (i = 1; i <= length; i++) {
375 (*x)[i] = (*x)[i - 1] + RADIUS * cos(alpha);
376 (*y)[i] = (*y)[i - 1] + RADIUS * sin(alpha);
377 alpha += PI - angle[i + 1];
378 }
379
380 free(angle);
381 free(loop_size);
382 free(stack_size);
383
384 return length;
385 }
386
387
388 /*
389 * i, j are the positions AFTER the last pair of a stack; i.e
390 * i-1 and j+1 are paired.
391 */
392 PRIVATE void
loop(const short * pair_table,int i,int j,float * angle,int * stack_size,int * loop_size,int * stk,int * lp)393 loop(const short *pair_table,
394 int i,
395 int j,
396 float *angle,
397 int *stack_size,
398 int *loop_size,
399 int *stk,
400 int *lp)
401 {
402 int count = 2; /*
403 * counts the VERTICES of a loop polygon; that's
404 * NOT necessarily the number of unpaired bases!
405 * Upon entry the loop has already 2 vertices, namely
406 * the pair i-1/j+1.
407 */
408
409 int r = 0, bubble = 0; /* bubble counts the unpaired digits in loops */
410
411 int i_old, partner, k, l, start_k, start_l, fill, ladder;
412 int begin, v, diff;
413 float polygon;
414
415 short *remember;
416
417 remember = (short *)vrna_alloc((3 + (j - i) / 5) * 2 * sizeof(short));
418
419 i_old = i - 1, j++; /* j has now been set to the partner of the
420 * previous pair for correct while-loop
421 * termination. */
422 while (i != j) {
423 partner = pair_table[i];
424 if ((!partner) || (i == 0)) {
425 i++, count++, bubble++;
426 } else {
427 count += 2;
428 k = i, l = partner; /* beginning of stack */
429 remember[++r] = k;
430 remember[++r] = l;
431 i = partner + 1; /* next i for the current loop */
432
433 start_k = k, start_l = l;
434 ladder = 0;
435 do
436 k++, l--, ladder++; /* go along the stack region */
437 while ((pair_table[k] == l) && (pair_table[k] > k));
438
439 fill = ladder - 2;
440 if (ladder >= 2) {
441 angle[start_k + 1 + fill] += PIHALF; /* Loop entries and */
442 angle[start_l - 1 - fill] += PIHALF; /* exits get an */
443 angle[start_k] += PIHALF; /* additional PI/2. */
444 angle[start_l] += PIHALF; /* Why ? (exercise) */
445 if (ladder > 2) {
446 for (; fill >= 1; fill--) {
447 angle[start_k + fill] = PI; /* fill in the angles */
448 angle[start_l - fill] = PI; /* for the backbone */
449 }
450 }
451 }
452
453 stack_size[++(*stk)] = ladder;
454 if (k <= l)
455 loop(pair_table, k, l, angle, stack_size, loop_size, stk, lp);
456 }
457 }
458 polygon = PI * (count - 2) / (float)count; /* bending angle in loop polygon */
459 remember[++r] = j;
460 begin = i_old < 0 ? 0 : i_old;
461 for (v = 1; v <= r; v++) {
462 diff = remember[v] - begin;
463 for (fill = 0; fill <= diff; fill++)
464 angle[begin + fill] += polygon;
465 if (v > r)
466 break;
467
468 begin = remember[++v];
469 }
470 loop_size[++(*lp)] = bubble;
471 free(remember);
472 }
473
474
475 PRIVATE int
coords_circular(const short * pt,float ** x,float ** y)476 coords_circular(const short *pt,
477 float **x,
478 float **y)
479 {
480 unsigned int length = (unsigned int)pt[0];
481 unsigned int i;
482 float d = 2 * PI / length;
483
484 *x = (float *)vrna_alloc(sizeof(float) * (length + 1));
485 *y = (float *)vrna_alloc(sizeof(float) * (length + 1));
486
487 for (i = 0; i < length; i++) {
488 (*x)[i] = cos(i * d - PIHALF);
489 (*y)[i] = sin(i * d - PIHALF);
490 }
491
492 return length;
493 }
494
495
496 #ifndef VRNA_DISABLE_BACKWARD_COMPATIBILITY
497
498 /*
499 *###########################################
500 *# deprecated functions below #
501 *###########################################
502 */
503 PUBLIC int
simple_xy_coordinates(short * pair_table,float * x,float * y)504 simple_xy_coordinates(short *pair_table,
505 float *x,
506 float *y)
507 {
508 if ((pair_table) && (x) && (y)) {
509 int ret, n;
510 float *xx, *yy;
511
512 n = pair_table[0];
513 ret = coords_simple(pair_table, &xx, &yy);
514
515 memcpy(x, xx, sizeof(float) * (n + 1));
516 memcpy(y, yy, sizeof(float) * (n + 1));
517
518 free(xx);
519 free(yy);
520 }
521
522 return 0;
523 }
524
525
526 PUBLIC int
simple_circplot_coordinates(short * pair_table,float * x,float * y)527 simple_circplot_coordinates(short *pair_table,
528 float *x,
529 float *y)
530 {
531 if ((pair_table) && (x) && (y)) {
532 int ret, n;
533 float *xx, *yy;
534
535 n = pair_table[0];
536 ret = coords_circular(pair_table, &xx, &yy);
537
538 memcpy(x, xx, sizeof(float) * (n + 1));
539 memcpy(y, yy, sizeof(float) * (n + 1));
540
541 free(xx);
542 free(yy);
543 }
544
545 return 0;
546 }
547
548
549 #endif
550