← Back to branch summary

~ubuntu-branches/ubuntu/edgy/ncbi-tools6/edgy

« back to all changes in this revision

Viewing changes to algo/blast/composition_adjustment/redo_alignment.h

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese
  • Date: 2006-07-19 23:28:07 UTC
  • mfrom: (1.1.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20060719232807-et3cdmcjgmnyleyx
Tags: 6.1.20060507-3ubuntu1
Re-merge with Debian

Show diffs side-by-side

added added

removed removed

Lines of Context:
algo/blast/composition_adjustment/redo_alignment.h
1
 
/* $Id: redo_alignment.h,v 1.1 2005/12/01 13:52:42 gertz Exp $
 
1
/* $Id: redo_alignment.h,v 1.7 2006/05/03 14:07:41 gertz Exp $
2
2
 * ===========================================================================
3
3
 *
4
4
 *                            PUBLIC DOMAIN NOTICE
21
21
 *
22
22
 *  Please cite the author in any work or product based on this material.
23
23
 *
24
 
 * ===========================================================================*/
 
24
 * ==========================================================================*/
25
25
/**
26
 
 * @file kappa_common.h
27
 
 * @author Alejandro Schaffer, E. Michael Gertz
28
 
 *
 
26
 * @file redo_alignment.h
29
27
 * Definitions used to redo a set of alignments, using either
30
28
 * composition matrix adjustment or the Smith-Waterman algorithm (or
31
29
 * both.)
33
31
 * Definitions with the prefix 'BlastCompo_' are primarily intended for use
34
32
 * by glue code that interfaces with this module, i.e. the definitions
35
33
 * need to be externally available so that glue code may be written, but
36
 
 * are not intended for general use. 
 
34
 * are not intended for general use.
 
35
 *
 
36
 * @author Alejandro Schaffer, E. Michael Gertz
37
37
 */
38
38
#ifndef __REDO_ALIGNMENT__
39
39
#define __REDO_ALIGNMENT__
40
40
 
41
41
#include <algo/blast/composition_adjustment/composition_adjustment.h>
 
42
#include <algo/blast/composition_adjustment/composition_constants.h>
42
43
#include <algo/blast/composition_adjustment/smith_waterman.h>
43
44
#include <algo/blast/composition_adjustment/compo_heap.h>
44
45
 
52
53
 */
53
54
typedef struct BlastCompo_Alignment {
54
55
    int score;           /**< the score of this alignment */
55
 
    ECompoAdjustModes comp_adjustment_mode;  /**< how the score was computed */
 
56
    EMatrixAdjustRule matrix_adjust_rule; 
 
57
    /**< how the score matrix was computed */
56
58
    int queryIndex;      /**< index of the query in a concatenated query */
57
59
    int queryStart;      /**< the start of the alignment in the query */
58
60
    int queryEnd;        /**< one past the end of the alignment in the query */
65
67
                                              list */
66
68
} BlastCompo_Alignment;
67
69
 
 
70
 
 
71
/**
 
72
 * Create a new BlastCompo_Alignment; parameters to this function
 
73
 * correspond directly to fields of BlastCompo_Alignment */
68
74
NCBI_XBLAST_EXPORT
69
75
BlastCompo_Alignment *
70
76
BlastCompo_AlignmentNew(int score,
71
 
                        ECompoAdjustModes comp_adjustment_mode,
 
77
                        EMatrixAdjustRule whichRule,
72
78
                        int queryIndex, int queryStart, int queryEnd,
73
79
                        int matchStart, int matchEnd, int frame,
74
80
                        void * context);
75
81
 
 
82
 
 
83
/**
 
84
 * Recursively free all alignments in the singly linked list whose
 
85
 * head is *palign. Set *palign to NULL.
 
86
 *
 
87
 * @param palign            pointer to the head of a singly linked list
 
88
 *                          of alignments.
 
89
 * @param free_context      a function capable of freeing the context
 
90
 *                          field of an alignment, or NULL if the
 
91
 *                          context field should not be freed
 
92
 */
 
93
NCBI_XBLAST_EXPORT
76
94
void BlastCompo_AlignmentsFree(BlastCompo_Alignment ** palign,
77
95
                               void (*free_context)(void*));
78
96
 
 
97
 
79
98
/** Parameters used to compute gapped alignments */
80
 
struct BlastCompo_GappingParams {
 
99
typedef struct BlastCompo_GappingParams {
81
100
    int gap_open;        /**< penalty for opening a gap */
82
101
    int gap_extend;      /**< penalty for extending a gapped alignment by
83
102
                              one residue */
87
106
                              path is no longer searched */
88
107
    void * context;      /**< a pointer to any additional gapping parameters
89
108
                              that may be needed by the calling routine. */
90
 
};
91
 
typedef struct BlastCompo_GappingParams BlastCompo_GappingParams;
 
109
} BlastCompo_GappingParams;
92
110
 
93
111
 
94
112
/**
135
153
typedef struct BlastCompo_MatchingSequence {
136
154
  Int4          length;         /**< length of this matching sequence */
137
155
  Int4          index;          /**< index of this sequence in the database */
138
 
  void * local_data;
 
156
  void * local_data;            /**< holds any sort of data that is
 
157
                                     necessary for callbacks to access
 
158
                                     the sequence */
139
159
} BlastCompo_MatchingSequence;
140
160
 
141
161
 
142
162
/** Collected information about a query */
143
 
struct BlastCompo_QueryInfo {
 
163
typedef struct BlastCompo_QueryInfo {
144
164
    int origin;               /**< origin of the query in a
145
165
                                   concatenated query */
146
166
    BlastCompo_SequenceData seq;   /**< sequence data for the query */
148
168
                                                   the query */
149
169
    double eff_search_space;  /**< effective search space of searches
150
170
                                   involving this query */
151
 
};
152
 
typedef struct BlastCompo_QueryInfo BlastCompo_QueryInfo;
 
171
} BlastCompo_QueryInfo;
153
172
 
154
173
 
155
174
/** Callbacks **/
184
203
 * performing an x-drop alignment in both directions
185
204
 *
186
205
 * @param in_align         the existing alignment, without traceback
 
206
 * @param matrix_adjust_rule   rule used to compute the scoring matrix
187
207
 * @param whichMode        which mode of composition adjustment has
188
208
 *                         been used to adjust the scoring matrix
189
209
 * @param query_data       query sequence data
199
219
 */
200
220
typedef BlastCompo_Alignment *
201
221
redo_one_alignment_type(BlastCompo_Alignment * in_align,
202
 
                        ECompoAdjustModes whichMode,
 
222
                        EMatrixAdjustRule matrix_adjust_rule,
203
223
                        BlastCompo_SequenceData * query_data,
204
224
                        BlastCompo_SequenceRange * query_range,
205
225
                        int ccat_query_length,
238
258
 * @param full_subject_length   length of the full subject sequence
239
259
 * @param gapping_params        parameters used to compute gapped
240
260
 *                              alignments
241
 
 * @param whichMode        which mode of composition adjustment has
242
 
 *                         been used to adjust the scoring matrix
 
261
 * @param matrix_adjust_rule   rule used to compute the scoring matrix
243
262
 * @return   0 on success, -1 for out-of-memory error
244
263
 */
245
264
typedef int
253
272
                     BlastCompo_SequenceRange * subject_range,
254
273
                     Int4 full_subject_length,
255
274
                     BlastCompo_GappingParams * gapping_params,
256
 
                     ECompoAdjustModes whichMode);
 
275
                     EMatrixAdjustRule matrix_adjust_rule);
 
276
 
 
277
/** Function type: free traceback data in a BlastCompo_Alignment.
 
278
 *
 
279
 *  @param traceback_data   data (of unknown type) to be freed
 
280
 */
 
281
typedef void free_align_traceback_type(void * traceback_data);
 
282
 
257
283
 
258
284
/** Callbacks used by Blast_RedoOneMatch and
259
285
 * Blast_RedoOneMatchSmithWaterman routines */
260
 
struct Blast_RedoAlignCallbacks {
 
286
typedef struct Blast_RedoAlignCallbacks {
 
287
    /** @sa calc_lambda_type */
261
288
    calc_lambda_type * calc_lambda;
 
289
    /** @sa get_range_type */
262
290
    get_range_type * get_range;
 
291
    /** @sa redo_one_alignment_type */
263
292
    redo_one_alignment_type * redo_one_alignment;
 
293
    /** @sa new_xdrop_align_type */
264
294
    new_xdrop_align_type * new_xdrop_align;
265
 
    void (*free_align_traceback)(void*);
266
 
};
267
 
typedef struct Blast_RedoAlignCallbacks Blast_RedoAlignCallbacks;
 
295
    /** @sa free_align_traceback_type */
 
296
    free_align_traceback_type * free_align_traceback;
 
297
} Blast_RedoAlignCallbacks;
 
298
 
268
299
 
269
300
/** A parameter block for the Blast_RedoOneMatch and
270
301
 * Blast_RedoOneMatchSmithWaterman routines */
271
 
struct Blast_RedoAlignParams {
272
 
    Blast_MatrixInfo * matrix_info;
273
 
    BlastCompo_GappingParams * gapping_params;
274
 
    int adjustParameters;
275
 
    int positionBased;
276
 
    int RE_pseudocounts;
277
 
    int subject_is_translated;
278
 
    int ccat_query_length;
279
 
    int cutoff_s;
280
 
    double cutoff_e;
281
 
    int do_link_hsps;
282
 
    double Lambda;
283
 
    double logK;
284
 
    const Blast_RedoAlignCallbacks * callbacks;
285
 
};
286
 
typedef struct Blast_RedoAlignParams Blast_RedoAlignParams;
287
 
 
288
 
 
 
302
typedef struct Blast_RedoAlignParams {
 
303
    Blast_MatrixInfo * matrix_info;  /**< information about the scoring
 
304
                                          matrix used */
 
305
    BlastCompo_GappingParams *
 
306
        gapping_params;              /**< parameters for performing a
 
307
                                          gapped alignment */
 
308
    ECompoAdjustModes compo_adjust_mode;   /**< composition adjustment mode */
 
309
    int positionBased;      /**< true if the search is position-based */
 
310
    int RE_pseudocounts;    /**< number of pseudocounts to use in
 
311
                                 relative-entropy based composition
 
312
                                 adjustment. */
 
313
    int subject_is_translated; /**< true if the subject is translated */
 
314
    int ccat_query_length;  /**< length of the concatenated query, or
 
315
                                just the length of the query if not
 
316
                                concatenated */
 
317
    int cutoff_s;           /**< cutoff score for saving alignments when
 
318
                                 HSP linking is used */
 
319
    double cutoff_e;        /**< cutoff e-value for saving alignments */
 
320
    int do_link_hsps;       /**< if true, then HSP linking and sum
 
321
                               statistics are used to computed e-values */
 
322
    const Blast_RedoAlignCallbacks *
 
323
        callbacks;                     /**< callback functions used by
 
324
                                            the Blast_RedoAlign* functions */
 
325
} Blast_RedoAlignParams;
 
326
 
 
327
 
 
328
/** Create new Blast_RedoAlignParams object.  The parameters of this
 
329
 * function correspond directly to the fields of
 
330
 * Blast_RedoAlignParams.  The new Blast_RedoAlignParams object takes
 
331
 * possession of *pmatrix_info and *pgapping_params, so these values
 
332
 * are set to NULL on exit. */
289
333
NCBI_XBLAST_EXPORT
290
334
Blast_RedoAlignParams *
291
335
Blast_RedoAlignParamsNew(Blast_MatrixInfo ** pmatrix_info,
292
336
                         BlastCompo_GappingParams **pgapping_params,
293
 
                         int adjustParameters, int positionBased,
 
337
                         ECompoAdjustModes compo_adjust_mode,
 
338
                         int positionBased,
294
339
                         int subject_is_translated,
295
340
                         int ccat_query_length, int cutoff_s,
296
 
                         double cutoff_e, int do_link_hsps, double Lambda,
297
 
                         double logK,
 
341
                         double cutoff_e, int do_link_hsps,
298
342
                         const Blast_RedoAlignCallbacks * callbacks);
299
343
 
 
344
 
 
345
/** Free a set of Blast_RedoAlignParams */
300
346
NCBI_XBLAST_EXPORT
301
347
void Blast_RedoAlignParamsFree(Blast_RedoAlignParams ** pparams);
302
348
 
 
349
 
 
350
/**
 
351
 * Recompute all alignments for one query/subject pair using the
 
352
 * Smith-Waterman algorithm and possibly also composition-based
 
353
 * statistics or composition-based matrix adjustment.
 
354
 *
 
355
 * @param alignments       an array of lists containing the newly
 
356
 *                         computed alignments.  There is one array
 
357
 *                         element for each query in the original
 
358
 *                         search
 
359
 * @param params           parameters used to redo the alignments
 
360
 * @param incoming_aligns  a list of existing alignments
 
361
 * @param hspcnt           length of incoming_aligns
 
362
 * @param Lambda           statistical parameter
 
363
 * @param logK             statistical parameter
 
364
 * @param matchingSeq      the database sequence
 
365
 * @param query_info       information about all queries
 
366
 * @param numQueries       the number of queries
 
367
 * @param matrix           the scoring matrix
 
368
 * @param NRrecord         a workspace used to adjust the composition.
 
369
 * @param forbidden        a workspace used to hold forbidden ranges
 
370
 *                         for the Smith-Waterman algorithm.
 
371
 * @param significantMatches   an array of heaps of alignments for
 
372
 *                             query-subject pairs that have already
 
373
 *                             been redone; used to terminate the
 
374
 *                             Smith-Waterman algorithm early if it is
 
375
 *                             clear that the current match is not
 
376
 *                             significant enough to be saved.
 
377
 * @param pvalueThisPair   the compositional p-value for this pair of sequences
 
378
 * @param compositionTestIndex   index of the test function used to decide
 
379
 *                               whether to use a compositional p-value
 
380
 * @param LambdaRatio      the ratio of the actual value of Lambda to the
 
381
 *                         ideal value.
 
382
 *
 
383
 * @return 0 on success, -1 on out-of-memory
 
384
 */
303
385
NCBI_XBLAST_EXPORT
304
386
int Blast_RedoOneMatchSmithWaterman(BlastCompo_Alignment ** alignments,
305
387
                                    Blast_RedoAlignParams * params,
306
 
                                    BlastCompo_Alignment * in_aligns,
 
388
                                    BlastCompo_Alignment * incoming_aligns,
307
389
                                    int hspcnt,
 
390
                                    double Lambda, double logK,
308
391
                                    BlastCompo_MatchingSequence * matchingSeq,
309
 
                                    BlastCompo_QueryInfo query[],
 
392
                                    BlastCompo_QueryInfo query_info[],
310
393
                                    int numQueries,
311
394
                                    int ** matrix,
312
395
                                    Blast_CompositionWorkspace * NRrecord,
313
396
                                    Blast_ForbiddenRanges * forbidden,
314
 
                                    BlastCompo_Heap * significantMatches);
315
 
 
 
397
                                    BlastCompo_Heap * significantMatches,
 
398
                                    double *pvalueThisPair,
 
399
                                    int compositionTestIndex,
 
400
                                    double *LambdaRatio);
 
401
 
 
402
 
 
403
/**
 
404
 * Recompute all alignments for one query/subject pair using
 
405
 * composition-based statistics or composition-based matrix adjustment.
 
406
 *
 
407
 * @param alignments       an array of lists containing the newly
 
408
 *                         computed alignments.  There is one array
 
409
 *                         element for each query in the original
 
410
 *                         search
 
411
 * @param params           parameters used to redo the alignments
 
412
 * @param incoming_aligns  a list of existing alignments
 
413
 * @param hspcnt           length of incoming_aligns
 
414
 * @param Lambda           statistical parameter
 
415
 * @param matchingSeq      the database sequence
 
416
 * @param ccat_query_length  the length of the concatenated query
 
417
 * @param query_info       information about all queries
 
418
 * @param numQueries       the number of queries
 
419
 * @param matrix           the scoring matrix
 
420
 * @param NRrecord         a workspace used to adjust the composition.
 
421
 * @param pvalueThisPair   the compositional p-value for this pair of sequences
 
422
 * @param compositionTestIndex   index of the test function used to decide
 
423
 *                               whether to use a compositional p-value
 
424
 * @param LambdaRatio      the ratio of the actual value of Lambda to the
 
425
 *                         ideal value.
 
426
 *
 
427
 * @return 0 on success, -1 on out-of-memory
 
428
 */
316
429
NCBI_XBLAST_EXPORT
317
430
int Blast_RedoOneMatch(BlastCompo_Alignment ** alignments,
318
431
                       Blast_RedoAlignParams * params,
319
432
                       BlastCompo_Alignment * incoming_aligns,
320
433
                       int hspcnt,
 
434
                       double Lambda,
321
435
                       BlastCompo_MatchingSequence * matchingSeq,
322
436
                       int ccat_query_length,
323
 
                       BlastCompo_QueryInfo query[],
 
437
                       BlastCompo_QueryInfo query_info[],
324
438
                       int numQueries,
325
439
                       int ** matrix,
326
 
                       Blast_CompositionWorkspace * NRrecord);
327
 
 
 
440
                       Blast_CompositionWorkspace * NRrecord,
 
441
                       double *pvalueThisPair,
 
442
                       int compositionTestIndex,
 
443
                       double *LambdaRatio);
 
444
 
 
445
 
 
446
/** Return true if a heuristic determines that it is unlikely to be
 
447
 * worthwhile to redo a query-subject pair with the given e-value; used
 
448
 * to terminate the main loop for redoing all alignments early. */
328
449
NCBI_XBLAST_EXPORT
329
450
int BlastCompo_EarlyTermination(double evalue,
330
451
                                BlastCompo_Heap significantMatches[],