1 #ifndef VIENNA_RNA_PACKAGE_PATHS_H 2 #define VIENNA_RNA_PACKAGE_PATHS_H 3 4 #ifdef VRNA_WARN_DEPRECATED 5 # if defined(__clang__) 6 # define DEPRECATED(func, msg) func __attribute__ ((deprecated("", msg))) 7 # elif defined(__GNUC__) 8 # define DEPRECATED(func, msg) func __attribute__ ((deprecated(msg))) 9 # else 10 # define DEPRECATED(func, msg) func 11 # endif 12 #else 13 # define DEPRECATED(func, msg) func 14 #endif 15 16 /** 17 * @file ViennaRNA/landscape/paths.h 18 * @ingroup paths 19 * @brief API for computing (optimal) (re-)folding paths between secondary structures 20 */ 21 22 /** 23 * @addtogroup paths 24 * @{ 25 * 26 * @brief API for various RNA folding path algorithms 27 * 28 * This part of our API allows for generating RNA secondary structure (re-)folding paths 29 * between two secondary structures or simply starting from a single structure. 30 * This is most important if an estimate of the refolding energy barrier between two 31 * structures is required, or a structure's corresponding local minimum needs to be 32 * determined, e.g. through a gradient-descent walk. 33 * 34 * This part of the interface is further split into the following sections: 35 * - @ref paths_direct, and 36 * - @ref paths_walk 37 */ 38 39 /** 40 * @brief Typename for the refolding path data structure #vrna_path_s 41 */ 42 typedef struct vrna_path_s vrna_path_t; 43 44 45 /** 46 * @brief Options data structure for (re-)folding path implementations 47 * @ingroup paths 48 */ 49 typedef struct vrna_path_options_s *vrna_path_options_t; 50 51 52 #ifndef VRNA_DISABLE_BACKWARD_COMPATIBILITY 53 54 /** 55 * @brief Old typename of #vrna_path_s 56 * @deprecated Use #vrna_path_t instead! 57 * @ingroup paths_deprecated 58 */ 59 DEPRECATED(typedef struct vrna_path_s path_t, 60 "Use vrna_path_t instead!"); 61 62 #endif 63 64 #include <ViennaRNA/fold_compound.h> 65 #include <ViennaRNA/landscape/move.h> 66 67 /** 68 * @brief Flag to indicate producing a (re-)folding path as list of dot-bracket structures 69 * @see #vrna_path_t, vrna_path_options_findpath(), vrna_path_direct(), vrna_path_direct_ub() 70 */ 71 #define VRNA_PATH_TYPE_DOT_BRACKET 1U 72 73 /** 74 * @brief Flag to indicate producing a (re-)folding path as list of transition moves 75 * @see #vrna_path_t, vrna_path_options_findpath(), vrna_path_direct(), vrna_path_direct_ub() 76 */ 77 #define VRNA_PATH_TYPE_MOVES 2U 78 79 /** 80 * @brief An element of a refolding path list 81 * 82 * Usually, one has to deal with an array of vrna_path_s, e.g. returned from one of 83 * the refolding-path algorithms. 84 * 85 * Since in most cases the length of the list is not known in advance, such lists 86 * have an <em>end-of-list</em> marker, which is either: 87 * - a value of <em>NULL</em> for vrna_path_s::s if vrna_path_s::type = #VRNA_PATH_TYPE_DOT_BRACKET, or 88 * - a vrna_path_s::move with zero in both fields vrna_move_t::pos_5 and vrna_move_t::pos_3 if 89 * vrna_path_s::type = #VRNA_PATH_TYPE_MOVES. 90 * 91 * In the following we show an example for how to cover both cases of iteration: 92 * @code{.c} 93 * vrna_path_t *ptr = path; // path was returned from one of the refolding path functions, e.g. vrna_path_direct() 94 * 95 * if (ptr) { 96 * if (ptr->type == VRNA_PATH_TYPE_DOT_BRACKET) { 97 * for (; ptr->s; ptr++) 98 * printf("%s [%6.2f]\n", ptr->s, ptr->en); 99 * } else if (ptr->type == VRNA_PATH_TYPE_MOVES) { 100 * for (; ptr->move.pos_5 != 0; ptr++) 101 * printf("move %d:%d, dG = %6.2f\n", ptr->move.pos_5, ptr->move.pos_3, ptr->en); 102 * } 103 * } 104 * @endcode 105 * 106 * @see vrna_path_free() 107 */ 108 struct vrna_path_s { 109 unsigned int type; /**< @brief The type of the path element. 110 * @details A value of #VRNA_PATH_TYPE_DOT_BRACKET indicates that 111 * vrna_path_s::s consists of the secondary structure in dot-bracket 112 * notation, and vrna_path_s::en the corresponding free energy.<br> 113 * On the other hand, if the value is #VRNA_PATH_TYPE_MOVES, vrna_path_s::s 114 * is <em>NULL</em> and vrna_path_s::move is set to the transition move 115 * that transforms a previous structure into it's neighbor along the path. 116 * In this case, the attribute vrna_path_s::en states the change in free 117 * energy with respect to the structure before application of vrna_path_s::move. 118 */ 119 double en; /**< @brief Free energy of current structure */ 120 char *s; /**< @brief Secondary structure in dot-bracket notation */ 121 vrna_move_t move; /**< @brief Move that transforms the previous structure into it's next neighbor along the path */ 122 }; 123 124 125 /** 126 * @brief Release (free) memory occupied by a (re-)folding path 127 * 128 * @see vrna_path_direct(), vrna_path_direct_ub(), vrna_path_findpath(), vrna_path_findpath_ub() 129 * @param path The refolding path to be free'd 130 */ 131 void 132 vrna_path_free(vrna_path_t *path); 133 134 135 /** 136 * @brief Release (free) memory occupied by an options data structure for (re-)folding path implementations 137 * @see vrna_path_options_findpath(), vrna_path_direct(), vrna_path_direct_ub() 138 * 139 * @param options The options data structure to be free'd 140 */ 141 void 142 vrna_path_options_free(vrna_path_options_t options); 143 144 145 /** @} */ 146 147 /** 148 * @addtogroup paths_direct 149 * @{ 150 */ 151 152 153 /** 154 * @brief Create options data structure for findpath direct (re-)folding path heuristic 155 * 156 * This function returns an options data structure that switches the vrna_path_direct() 157 * and vrna_path_direct_ub() API functions to use the <em>findpath</em> @cite flamm:2001 158 * heuristic. The parameter @p width specifies the width of the breadth-first search 159 * while the second parameter @p type allows one to set the type of the returned 160 * (re-)folding path. 161 * 162 * Currently, the following return types are available: 163 * - A list of dot-bracket structures and corresponding free energy (flag: #VRNA_PATH_TYPE_DOT_BRACKET) 164 * - A list of transition moves and corresponding free energy changes (flag: #VRNA_PATH_TYPE_MOVES) 165 * 166 * @see #VRNA_PATH_TYPE_DOT_BRACKET, #VRNA_PATH_TYPE_MOVES, vrna_path_options_free(), 167 * vrna_path_direct(), vrna_path_direct_ub() 168 * 169 * @param width Width of the breath-first search strategy 170 * @param type Setting that specifies how the return (re-)folding path should be encoded 171 * @returns An options data structure with settings for the findpath direct path heuristic 172 */ 173 vrna_path_options_t 174 vrna_path_options_findpath(int width, 175 unsigned int type); 176 177 178 /** 179 * @brief Determine an optimal direct (re-)folding path between two secondary structures 180 * 181 * This is the generic wrapper function to retrieve (an optimal) (re-)folding path 182 * between two secondary structures @p s1 and @p s2. The actual algorithm that 183 * is used to generate the (re-)folding path is determined by the settings specified 184 * in the @p options data structure. This data structure also determines the return 185 * type, which might be either: 186 * - a list of dot-bracket structures with corresponding free energy, or 187 * - a list of transition moves with corresponding free energy change 188 * 189 * If the @p options parameter is passed a <em>NULL</em> pointer, this function 190 * defaults to the <em>findpath heuristic</em> @cite flamm:2001 with a breadth-first 191 * search width of @f$ 10 @f$, and the returned path consists of dot-bracket structures 192 * with corresponding free energies. 193 * 194 * @see vrna_path_direct_ub(), vrna_path_options_findpath(), vrna_path_options_free(), 195 * vrna_path_free() 196 * 197 * @param fc The #vrna_fold_compound_t with precomputed sequence encoding and model details 198 * @param s1 The start structure in dot-bracket notation 199 * @param s2 The target structure in dot-bracket notation 200 * @param options An options data structure that specifies the path heuristic and corresponding settings (maybe <em>NULL</em>) 201 * @returns An optimal (re-)folding path between the two input structures 202 */ 203 vrna_path_t * 204 vrna_path_direct(vrna_fold_compound_t *fc, 205 const char *s1, 206 const char *s2, 207 vrna_path_options_t options); 208 209 210 /** 211 * @brief Determine an optimal direct (re-)folding path between two secondary structures 212 * 213 * This function is similar to vrna_path_direct(), but allows to specify an <em>upper-bound</em> 214 * for the saddle point energy. The underlying algorithms will stop determining an (optimal) 215 * (re-)folding path, if none can be found that has a saddle point below the specified 216 * upper-bound threshold @p maxE. 217 * 218 * @warning The argument @p maxE enables one to specify an upper bound, or maximum free 219 * energy for the saddle point between the two input structures. If no path 220 * with @f$E_{saddle} < E_{max}@f$ is found, the function simply returns @em NULL 221 * 222 * @see vrna_path_direct_ub(), vrna_path_options_findpath(), vrna_path_options_free(), 223 * vrna_path_free() 224 * 225 * @param fc The #vrna_fold_compound_t with precomputed sequence encoding and model details 226 * @param s1 The start structure in dot-bracket notation 227 * @param s2 The target structure in dot-bracket notation 228 * @param maxE Upper bound for the saddle point along the (re-)folding path 229 * @param options An options data structure that specifies the path heuristic and corresponding settings (maybe <em>NULL</em>) 230 * @returns An optimal (re-)folding path between the two input structures 231 */ 232 vrna_path_t * 233 vrna_path_direct_ub(vrna_fold_compound_t *fc, 234 const char *s1, 235 const char *s2, 236 int maxE, 237 vrna_path_options_t options); 238 239 240 /** @} */ 241 242 #endif 243