1#ifndef RNAPUZZLER_SIBLING_INTERSCTIONS_H 2#define RNAPUZZLER_SIBLING_INTERSCTIONS_H 3 4/* 5 * RNApuzzler handle sibling intersections 6 * 7 * c Daniel Wiegreffe, Daniel Alexander, Dirk Zeckzer 8 * ViennaRNA package 9 */ 10 11#include <stdlib.h> 12#include <math.h> 13 14#include "ViennaRNA/utils/basic.h" 15 16#include "../headers/configtree_struct.h" 17#include "configtree.inc" 18#include "definitions.inc" 19#include "vector_math.inc" 20#include "intersectLevelTreeNodes.inc" 21#include "boundingWedge.inc" 22#include "calcDeltas.inc" 23#include "handleConfigChanges.inc" 24 25/** 26 * Check and fix intersections between all siblings of the current node. 27 * 28 * @param node: node to check 29 * @param puzzler: vrna_plot_options_puzzler_t 30 */ 31PRIVATE short 32checkSiblings(treeNode *node, 33 vrna_plot_options_puzzler_t *puzzler); 34 35 36/** 37 * @brief fixIntersectionOfSiblings 38 * Try to fix intersections of sibling subtrees at their common ancestor. 39 * @param tree 40 * common ancestor of intersecting subtrees 41 * @param left 42 * @param right 43 * @param deltaCfg 44 * @param puzzler 45 * @return 46 * 1 if something was changed, 0 otherwise 47 */ 48PRIVATE short 49fixIntersectionOfSiblings(treeNode *tree, 50 const int left, 51 const int right, 52 double *deltaCfg, 53 vrna_plot_options_puzzler_t *puzzler) 54{ 55 double wedgeMin, wedgeMax; 56 57 getBoundingWedge(tree, right, &wedgeMin, &wedgeMax); 58 double minAngle = wedgeMin; 59 getBoundingWedge(tree, left, &wedgeMin, &wedgeMax); 60 double maxAngle = wedgeMax; 61 double targetAngle = minAngle - maxAngle; 62 63 short changed = 0; 64 if (targetAngle < 0) { 65 targetAngle = fmax(targetAngle, -MATH_PI_HALF); /* limit the angle to avoid malformed structures */ 66 double changedAngle = calcDeltas(tree, 67 getParent(tree), 68 left, 69 right, 70 (-1) * targetAngle, 71 puzzler, 72 deltaCfg); 73 74 if (changedAngle != 0.0) { 75 treeNode *leftNode = getChild(tree, left); 76 treeNode *rightNode = getChild(tree, right); 77 78 /* apply all changes */ 79 changed = checkAndApplyConfigChanges(tree, deltaCfg, siblings, puzzler); 80 } 81 } 82 83 return changed; 84} 85 86 87/** 88 * @brief handleIntersectionOfSiblings 89 * Try to fix intersections of sibling subtrees at their common ancestor. 90 * @param tree 91 * common ancestor of intersecting subtrees 92 * @param listOfIntersections 93 * list of pairs of indices of subtrees that are intersecting. 94 * [numberOfIntersections, [i1, j1], [i2, j2], ...] 95 * @return 96 * 1 if something was changed, 0 otherwise 97 */ 98PRIVATE short 99handleIntersectionOfSiblings(treeNode *tree, 100 const int *listOfIntersections, 101 vrna_plot_options_puzzler_t *puzzler) 102{ 103 char *fnName = "FIX INTERSECTION OF SIBLINGS"; 104 105 /* 106 * idea: 107 * measure each intersection by calculating an overlap angle 108 * increase the spaces between intersectors and decrease spaces that are not between them 109 * distribute the overlap angle equally to all participating spaces 110 * check for new or remaining intersections (at the end) 111 */ 112 113 if (puzzler->numberOfChangesAppliedToConfig > puzzler->maximumNumberOfConfigChangesAllowed) 114 return -1; 115 116 short changed = 0; 117 int intersectionCount = listOfIntersections[0]; 118 119 int childCount = tree->childCount; 120 int configSize = childCount + 1; 121 122 double *deltaCfg = (double *)vrna_alloc(configSize * sizeof(double)); 123 124 /* init deltas with zero */ 125 for (int i = 0; i < configSize; i++) 126 127 deltaCfg[i] = 0.0; 128 129 /* fix intersections of siblings */ 130 for (int k = 0; k < intersectionCount; k++) { 131 /* for all intersections - start */ 132 133 int left = listOfIntersections[2 * k + 1]; 134 int right = listOfIntersections[2 * k + 2]; 135 136 changed = fixIntersectionOfSiblings(tree, left, right, deltaCfg, puzzler); 137 138 if (changed) 139 140 break; 141 } 142 143 free(deltaCfg); 144 145 return changed; 146} 147 148 149PRIVATE short 150checkSiblings(treeNode *node, 151 vrna_plot_options_puzzler_t *puzzler) 152{ 153 char *fnName = "CHECK SIBLINGS"; 154 short ret = _false; 155 156 int childCount = node->childCount; 157 /* create array to store all information about overlapping neighbors */ 158 int *intersectorsBranches = (int *)vrna_alloc((childCount * childCount) * sizeof(int)); 159 160 for (int i = 0; i < childCount * childCount; i++) 161 162 intersectorsBranches[i] = -1; 163 164 /* actually check for those intersections */ 165 for (int i = 0; i < childCount; i++) { 166 int intersectorsCount = 0; 167 168 for (int j = i + 1; j < childCount; j++) { 169 treeNode *childI = getChild(node, i); 170 treeNode *childJ = getChild(node, j); 171 172 if (intersectTrees(childI, childJ)) { 173 intersectorsBranches[i * childCount + intersectorsCount] = j; 174 intersectorsCount++; 175 } 176 } 177 } 178 179 /* and count them */ 180 int intersectionCount = 0; 181 182 for (int i = 0; i < (childCount * childCount); i++) { 183 if (intersectorsBranches[i] != -1) 184 185 intersectionCount++; 186 } 187 188 if (intersectionCount > 0) { 189 ret |= _intersect; 190 191 /* 192 * transform intersection information into format 193 * [ count, [intersector_a, intersector_b], [intersector_a, intersector_b], ... ] 194 * where count states how many pairs of a/b are there 195 * the i-th intersection has index a=2*i+1; b=2*i+2 196 */ 197 int *listOfIntersections = (int *)vrna_alloc((1 + 2 * intersectionCount) * sizeof(int)); 198 listOfIntersections[0] = intersectionCount; 199 200 int counter = 0; 201 for (int i = 0; i < (childCount * childCount); i++) { 202 if (intersectorsBranches[i] != -1) { 203 listOfIntersections[2 * counter + 1] = i / childCount; 204 listOfIntersections[2 * counter + 2] = intersectorsBranches[i]; 205 counter++; 206 } 207 } 208 209 /* resolve all of those intersections for this node's subtrees */ 210 short retFix = handleIntersectionOfSiblings(node, listOfIntersections, puzzler); 211 212 if (retFix < 0) 213 ret = retFix; 214 else if (retFix) 215 ret |= _changed; 216 217 free(listOfIntersections); 218 } 219 220 free(intersectorsBranches); 221 222 return ret; 223} 224 225 226#endif 227