← 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/smith_waterman.c

  • 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/smith_waterman.c
24
24
 
25
25
/**
26
26
 * @file smith_waterman.c
27
 
 *
28
27
 * Routines for computing rigorous, Smith-Waterman alignments.
 
28
 *
 
29
 * @author Alejandro Schaffer, E. Michael Gertz
29
30
 */
30
31
#ifndef SKIP_DOXYGEN_PROCESSING
31
32
static char const rcsid[] =
32
 
    "$Id: smith_waterman.c,v 1.1 2005/12/01 13:48:09 gertz Exp $";
 
33
    "$Id: smith_waterman.c,v 1.3 2005/12/19 15:37:33 gertz Exp $";
33
34
#endif /* SKIP_DOXYGEN_PROCESSING */
34
35
 
35
36
#include <algo/blast/core/ncbi_std.h>
46
47
 
47
48
/**
48
49
 * Compute the score and right-hand endpoints of the locally optimal
49
 
 * Smith-Waterman alignment.
50
 
 *
51
 
 * @param *score            the computed score
52
 
 * @param *matchSeqEnd      the right-hand end of the alignment in the
53
 
 *                          database sequence
54
 
 * @param *queryEnd         the right-hand end of the alignment in the
55
 
 *                          query sequence
56
 
 * @param matchSeq          the database sequence data
57
 
 * @param matchSeqLength    length of matchSeq
58
 
 * @param query             the query sequence data
59
 
 * @param queryLength       length of query
60
 
 * @param matrix            amino-acid scoring matrix
61
 
 * @param gapOpen           penalty for opening a gap
62
 
 * @param gapExtend         penalty for extending a gap by one amino acid
63
 
 * @param positionSpecific  determines whether matrix is position
64
 
 *                          specific or not
 
50
 * Smith-Waterman alignment. Called by Blast_SmithWatermanScoreOnly
 
51
 * when there are no forbidden ranges.  nonempty.  See
 
52
 * Blast_SmithWatermanScoreOnly for the meaning of the parameters to
 
53
 * this routine.
65
54
 */
66
55
static int
67
56
BLbasicSmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd,
152
141
 
153
142
/**
154
143
 * Find the left-hand endpoints of the locally optimal Smith-Waterman
155
 
 * alignment given the score and right-hand endpoints computed by
156
 
 * BLbasicSmithWatermanScoreOnly.
157
 
 *
158
 
 * @param *score_out        the score of the optimal alignment -- should
159
 
 *                          equal score_in.
160
 
 * @param *matchSeqStart    the left-hand endpoint of the alignment in
161
 
 *                          the database sequence
162
 
 * @param *queryStart       the right-hand endpoint of the alignment
163
 
 *                          in the query sequence
164
 
 * @param matchSeq          the database sequence data
165
 
 * @param matchSeqLength    length of matchSeq
166
 
 * @param query             the query sequence data
167
 
 * @param matrix            amino-acid scoring matrix
168
 
 * @param gapOpen           penalty for opening a gap
169
 
 * @param gapExtend         penalty for extending a gap by one amino acid
170
 
 * @param matchSeqEnd       right-hand endpoint of the alignment in
171
 
 *                          the database sequence
172
 
 * @param queryEnd          right-hand endpoint of the alignment in
173
 
 *                          the query
174
 
 * @param score_in          the score of the alignment
175
 
 * @param positionSpecific  determines whether matrix is position
176
 
 *                          specific or not
 
144
 * alignment. Called by Blast_SmithWatermanFindStart when there are no
 
145
 * forbidden ranges.  See Blast_SmithWatermanFindStartfor the meaning
 
146
 * of the parameters to this routine.
177
147
 */
178
148
static int
179
149
BLSmithWatermanFindStart(int *score_out,
270
240
/**
271
241
 * Compute the score and right-hand endpoints of the locally optimal
272
242
 * Smith-Waterman alignment, subject to the restriction that some
273
 
 * ranges are forbidden.
274
 
 *
275
 
 * @param *score            the computed score
276
 
 * @param *matchSeqEnd      the right-hand end of the alignment in the
277
 
 *                          database sequence
278
 
 * @param *queryEnd         the right-hand end of the alignment in the
279
 
 *                          query sequence
280
 
 * @param matchSeq          the database sequence data
281
 
 * @param matchSeqLength    length of matchSeq
282
 
 * @param query             the query sequence data
283
 
 * @param queryLength       length of query
284
 
 * @param matrix            amino-acid scoring matrix
285
 
 * @param gapOpen           penalty for opening a gap
286
 
 * @param gapExtend         penalty for extending a gap by one amino acid
287
 
 * @param numForbidden      number of forbidden ranges [in]
288
 
 * @param forbiddenRanges   lists areas that should not be aligned [in]
289
 
 * @param positionSpecific  determines whether matrix is position
290
 
 *                          specific or not
 
243
 * ranges are forbidden.  Called by Blast_SmithWatermanScoreOnly when
 
244
 * forbiddenRanges is nonempty.  See Blast_SmithWatermanScoreOnly for
 
245
 * the meaning of the parameters to this routine.
291
246
 */
292
247
static int
293
248
BLspecialSmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd,
393
348
/**
394
349
 * Find the left-hand endpoints of the locally optimal Smith-Waterman
395
350
 * alignment, subject to the restriction that certain ranges may not
396
 
 * be aligned, given the score and right-hand endpoints computed by
397
 
 * BLspecialSmithWatermanScoreOnly.
398
 
 *
399
 
 * @param *score_out        the score of the optimal alignment -- should
400
 
 *                          equal score_in.
401
 
 * @param *matchSeqStart    the left-hand endpoint of the alignment in
402
 
 *                          the database sequence
403
 
 * @param *queryStart       the right-hand endpoint of the alignment
404
 
 *                          in the query sequence
405
 
 * @param matchSeq          the database sequence data
406
 
 * @param matchSeqLength    length of matchSeq
407
 
 * @param query             the query sequence data
408
 
 * @param matrix            amino-acid scoring matrix
409
 
 * @param gapOpen           penalty for opening a gap
410
 
 * @param gapExtend         penalty for extending a gap by one amino acid
411
 
 * @param matchSeqEnd       right-hand endpoint of the alignment in
412
 
 *                          the database sequence
413
 
 * @param queryEnd          right-hand endpoint of the alignment in
414
 
 *                          the query
415
 
 * @param score_in          the score of the alignment
416
 
 * @param numForbidden      number of forbidden ranges
417
 
 * @param forbiddenRanges   lists areas that should not be aligned
418
 
 * @param positionSpecific  determines whether matrix is position
419
 
 *                          specific or not
 
351
 * be aligned. Called by Blast_SmithWatermanFindStart if
 
352
 * forbiddenRanges is nonempty.  See Blast_SmithWatermanFindStartfor
 
353
 * the meaning of the parameters to this routine.
420
354
 */
421
355
static int
422
356
BLspecialSmithWatermanFindStart(int * score_out,
526
460
}
527
461
 
528
462
 
529
 
/**
530
 
 * Release the storage associated with the fields of self, but do not
531
 
 * delete self
532
 
 *
533
 
 * @param self          an instance of Blast_ForbiddenRanges [in][out]
534
 
 */
 
463
/* Documented in smith_waterman.h. */
535
464
void
536
465
Blast_ForbiddenRangesRelease(Blast_ForbiddenRanges * self)
537
466
{
544
473
}
545
474
 
546
475
 
547
 
/**
548
 
 * Initialize a new, empty Blast_ForbiddenRanges
549
 
 *
550
 
 * @param self              object to be initialized
551
 
 * @param capacity          the number of ranges that may be stored
552
 
 *                          (must be at least as long as the length
553
 
 *                           of the query)
554
 
 */
 
476
/* Documented in smith_waterman.h. */
555
477
int
556
478
Blast_ForbiddenRangesInitialize(Blast_ForbiddenRanges * self,
557
479
                                int capacity)
583
505
}
584
506
 
585
507
 
586
 
/** Reset self to be empty */
587
 
void
588
 
Blast_ForbiddenRangesClear(Blast_ForbiddenRanges * self)
 
508
/* Documented in smith_waterman.h. */
 
509
void Blast_ForbiddenRangesClear(Blast_ForbiddenRanges * self)
589
510
{
590
511
    int f;
591
512
    for (f = 0;  f < self->capacity;  f++) {
595
516
}
596
517
 
597
518
 
598
 
/** Add some ranges to self
599
 
 * @param self          an instance of Blast_ForbiddenRanges [in][out]
600
 
 * @param queryStart    start of the alignment in the query sequence
601
 
 * @param queryAlignmentExtent  length of the alignment in the query sequence
602
 
 * @param matchStart    start of the alignment in the subject sequence
603
 
 * @param matchAlignmentExtent  length of the alignment in the
604
 
 *                              subject sequence
605
 
 */
 
519
/* Documented in smith_waterman.h. */
606
520
int
607
521
Blast_ForbiddenRangesPush(Blast_ForbiddenRanges * self,
608
522
                          int queryStart,
631
545
}
632
546
 
633
547
 
634
 
/**
635
 
 * Calls BLbasicSmithWatermanScoreOnly if forbiddenRanges is empty and
636
 
 * calls BLspecialSmithWatermanScoreOnly otherwise.  See
637
 
 * BLspecialSmithWatermanScoreOnly for the meaning of the parameters
638
 
 * to this routine.
639
 
 */
 
548
/* Documented in smith_waterman.h. */
640
549
int
641
550
Blast_SmithWatermanScoreOnly(int *score,
642
551
                             int *matchSeqEnd, int *queryEnd,
670
579
}
671
580
 
672
581
 
673
 
/**
674
 
 * Calls BLSmithWatermanFindStart if forbiddenRanges is empty and
675
 
 * calls BLspecialSmithWatermanFindStart otherwise. See
676
 
 * BLspecialSmithWatermanFindStart for the meaning of the parameters
677
 
 * to this routine.
678
 
 */
 
582
/* Documented in smith_waterman.h. */
679
583
int
680
584
Blast_SmithWatermanFindStart(int * score_out,
681
585
                             int *matchSeqStart,