1 /****************************************************************\ 2 * * 3 * C4 dynamic programming library - suboptimal alignments * 4 * * 5 * Guy St.C. Slater.. mailto:guy@ebi.ac.uk * 6 * Copyright (C) 2000-2009. All Rights Reserved. * 7 * * 8 * This source code is distributed under the terms of the * 9 * GNU General Public License, version 3. See the file COPYING * 10 * or http://www.gnu.org/licenses/gpl.txt for details * 11 * * 12 * If you use this code, please keep this notice intact. * 13 * * 14 \****************************************************************/ 15 16 #ifndef INCLUDED_SUBOPT_H 17 #define INCLUDED_SUBOPT_H 18 19 #ifdef __cplusplus 20 extern "C" { 21 #endif /* __cplusplus */ 22 23 #include <glib.h> 24 25 #include "alignment.h" 26 #include "region.h" 27 #include "rangetree.h" 28 29 /* Points are stored in a RangeTree, 30 * then put in row/col lists for dp lookup. 31 */ 32 33 typedef struct { 34 gint ref_count; 35 gint query_length; 36 gint target_length; 37 RangeTree *range_tree; 38 gint path_count; 39 } SubOpt; 40 41 SubOpt *SubOpt_create(gint query_length, gint target_length); 42 SubOpt *SubOpt_share(SubOpt *subopt); 43 void SubOpt_destroy(SubOpt *subopt); 44 void SubOpt_add_alignment(SubOpt *subopt, Alignment *alignment); 45 46 typedef gboolean (*SubOpt_FindFunc)(gint query_pos, gint target_pos, 47 gint path_id, gpointer user_data); 48 49 gboolean SubOpt_find(SubOpt *subopt, Region *region, 50 SubOpt_FindFunc find_func, gpointer user_data); 51 gboolean SubOpt_overlaps_alignment(SubOpt *subopt, Alignment *alignment); 52 53 /**/ 54 55 typedef struct { 56 gint *query_pos; 57 gint target_pos; 58 gint total; /* Number of query positions in this row */ 59 } SubOpt_Index_Row; 60 61 typedef struct { 62 Region *region; 63 GPtrArray *row_list; /* Contains SubOpt_Index_Row */ 64 SubOpt_Index_Row *curr_row; 65 gint curr_row_index; 66 gint curr_query_index; 67 SubOpt_Index_Row *blank_row; 68 } SubOpt_Index; 69 70 SubOpt_Index *SubOpt_Index_create(SubOpt *subopt, Region *region); 71 void SubOpt_Index_destroy(SubOpt_Index *soi); 72 void SubOpt_Index_set_row(SubOpt_Index *soi, gint target_pos); 73 /* FIXME: could make SubOpt_Index_set_row a macro for speed */ 74 gboolean SubOpt_Index_is_blocked(SubOpt_Index *soi, 75 gint query_pos); 76 77 #define SubOpt_Index_is_blocked_fast(soi, q_pos) \ 78 ((soi->curr_row->query_pos[ soi->curr_query_index] < q_pos) \ 79 ?(soi->curr_row->query_pos[++soi->curr_query_index] == q_pos) \ 80 :(soi->curr_row->query_pos[ soi->curr_query_index] == q_pos)) 81 /* For SubOpt_Index_set_row() and SubOpt_Index_is_blocked_fast(), 82 * query_pos and target_pos should use the coordinates 83 * of the indexed region, not of the whole sequence 84 * 85 * It is assumed that target_pos increments between 86 * each call to SubOpt_Index_set_row(). 87 * 88 * Multiple calls to SubOpt_Index_is_blocked() must be allowed, 89 * for models with multiple match states. 90 */ 91 92 #ifdef __cplusplus 93 } 94 #endif /* __cplusplus */ 95 96 #endif /* INCLUDED_SUBOPT_H */ 97 98