* matchSeq,
intmatchSeqLength,
55 int**matrix,
intgapOpen,
intgapExtend,
60 intbestMatchSeqPos, bestQueryPos;
67 intprevScoreNoGapMatchSeq;
69 intprevScoreGapMatchSeq;
72 intmatchSeqPos, queryPos;
75 if(scoreVector ==
NULL) {
81newGapCost = gapOpen + gapExtend;
82 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
83scoreVector[matchSeqPos].
noGap= 0;
84scoreVector[matchSeqPos].
gapExists= -gapOpen;
86 for(queryPos = 0; queryPos < queryLength; queryPos++) {
88matrixRow = matrix[queryPos];
90matrixRow = matrix[
query[queryPos]];
92prevScoreNoGapMatchSeq = 0;
93prevScoreGapMatchSeq = -(gapOpen);
94 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
97 if((newScore = newScore - newGapCost) >
98(prevScoreGapMatchSeq = prevScoreGapMatchSeq - gapExtend))
99prevScoreGapMatchSeq = newScore;
102 if((newScore = scoreVector[matchSeqPos].noGap - newGapCost) >
104scoreVector[matchSeqPos].
gapExists- gapExtend))
105continueGapScore = newScore;
109prevScoreNoGapMatchSeq + matrixRow[matchSeq[matchSeqPos]];
113 if(newScore < prevScoreGapMatchSeq)
114newScore = prevScoreGapMatchSeq;
115 if(newScore < continueGapScore)
116newScore = continueGapScore;
117prevScoreNoGapMatchSeq = scoreVector[matchSeqPos].
noGap;
118scoreVector[matchSeqPos].
noGap= newScore;
119scoreVector[matchSeqPos].
gapExists= continueGapScore;
120 if(newScore > bestScore) {
121bestScore = newScore;
122bestQueryPos = queryPos;
123bestMatchSeqPos = matchSeqPos;
130*matchSeqEnd = bestMatchSeqPos;
131*queryEnd = bestQueryPos;
146 int*matchSeqStart,
int*queryStart,
147 const Uint1* matchSeq,
intmatchSeqLength,
149 int**matrix,
intgapOpen,
intgapExtend,
150 intmatchSeqEnd,
intqueryEnd,
intscore_in,
151 intpositionSpecific)
155 intbestMatchSeqPos, bestQueryPos;
161 intprevScoreNoGapMatchSeq;
163 intprevScoreGapMatchSeq;
165 intcontinueGapScore;
166 intmatchSeqPos, queryPos;
169 if(scoreVector ==
NULL) {
175newGapCost = gapOpen + gapExtend;
176 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
177scoreVector[matchSeqPos].
noGap= 0;
178scoreVector[matchSeqPos].
gapExists= -(gapOpen);
180 for(queryPos = queryEnd; queryPos >= 0; queryPos--) {
181 if(positionSpecific)
182matrixRow = matrix[queryPos];
184matrixRow = matrix[
query[queryPos]];
186prevScoreNoGapMatchSeq = 0;
187prevScoreGapMatchSeq = -(gapOpen);
188 for(matchSeqPos = matchSeqEnd; matchSeqPos >= 0; matchSeqPos--) {
191 if((newScore = newScore - newGapCost) >
192(prevScoreGapMatchSeq = prevScoreGapMatchSeq - gapExtend))
193prevScoreGapMatchSeq = newScore;
196 if((newScore = scoreVector[matchSeqPos].noGap - newGapCost) >
198scoreVector[matchSeqPos].
gapExists- gapExtend))
199continueGapScore = newScore;
203prevScoreNoGapMatchSeq + matrixRow[matchSeq[matchSeqPos]];
207 if(newScore < prevScoreGapMatchSeq)
208newScore = prevScoreGapMatchSeq;
209 if(newScore < continueGapScore)
210newScore = continueGapScore;
211prevScoreNoGapMatchSeq = scoreVector[matchSeqPos].
noGap;
212scoreVector[matchSeqPos].
noGap= newScore;
213scoreVector[matchSeqPos].
gapExists= continueGapScore;
214 if(newScore > bestScore) {
215bestScore = newScore;
216bestQueryPos = queryPos;
217bestMatchSeqPos = matchSeqPos;
219 if(bestScore >= score_in)
222 if(bestScore >= score_in)
228*matchSeqStart = bestMatchSeqPos;
229*queryStart = bestQueryPos;
230*score_out = bestScore;
245 const Uint1* matchSeq,
intmatchSeqLength,
247 int**matrix,
intgapOpen,
intgapExtend,
248 const int*numForbidden,
249 int** forbiddenRanges,
250 intpositionSpecific)
254 intbestMatchSeqPos, bestQueryPos;
260 intprevScoreNoGapMatchSeq;
262 intprevScoreGapMatchSeq;
264 intcontinueGapScore;
265 intmatchSeqPos, queryPos;
270 if(scoreVector ==
NULL) {
276newGapCost = gapOpen + gapExtend;
277 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
278scoreVector[matchSeqPos].
noGap= 0;
279scoreVector[matchSeqPos].
gapExists= -(gapOpen);
281 for(queryPos = 0; queryPos < queryLength; queryPos++) {
282 if(positionSpecific)
283matrixRow = matrix[queryPos];
285matrixRow = matrix[
query[queryPos]];
287prevScoreNoGapMatchSeq = 0;
288prevScoreGapMatchSeq = -(gapOpen);
289 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
292 if((newScore = newScore - newGapCost) >
293(prevScoreGapMatchSeq = prevScoreGapMatchSeq - gapExtend))
294prevScoreGapMatchSeq = newScore;
297 if((newScore = scoreVector[matchSeqPos].noGap - newGapCost) >
299scoreVector[matchSeqPos].
gapExists- gapExtend))
300continueGapScore = newScore;
304 for(
f= 0;
f< numForbidden[queryPos];
f++) {
305 if((matchSeqPos >= forbiddenRanges[queryPos][2 *
f]) &&
306(matchSeqPos <= forbiddenRanges[queryPos][2*
f+ 1])) {
315prevScoreNoGapMatchSeq + matrixRow[matchSeq[matchSeqPos]];
319 if(newScore < prevScoreGapMatchSeq)
320newScore = prevScoreGapMatchSeq;
321 if(newScore < continueGapScore)
322newScore = continueGapScore;
323prevScoreNoGapMatchSeq = scoreVector[matchSeqPos].
noGap;
324scoreVector[matchSeqPos].
noGap= newScore;
325scoreVector[matchSeqPos].
gapExists= continueGapScore;
326 if(newScore > bestScore) {
327bestScore = newScore;
328bestQueryPos = queryPos;
329bestMatchSeqPos = matchSeqPos;
336*matchSeqEnd = bestMatchSeqPos;
337*queryEnd = bestQueryPos;
353 int*matchSeqStart,
int*queryStart,
354 const Uint1* matchSeq,
intmatchSeqLength,
356 intgapOpen,
intgapExtend,
intmatchSeqEnd,
357 intqueryEnd,
intscore_in,
358 const int*numForbidden,
359 int** forbiddenRanges,
360 intpositionSpecific)
364 intbestMatchSeqPos, bestQueryPos;
371 intprevScoreNoGapMatchSeq;
373 intprevScoreGapMatchSeq;
375 intcontinueGapScore;
376 intmatchSeqPos, queryPos;
381 if(scoreVector ==
NULL) {
387newGapCost = gapOpen + gapExtend;
388 for(matchSeqPos = 0; matchSeqPos < matchSeqLength; matchSeqPos++) {
389scoreVector[matchSeqPos].
noGap= 0;
390scoreVector[matchSeqPos].
gapExists= -(gapOpen);
392 for(queryPos = queryEnd; queryPos >= 0; queryPos--) {
393 if(positionSpecific)
394matrixRow = matrix[queryPos];
396matrixRow = matrix[
query[queryPos]];
398prevScoreNoGapMatchSeq = 0;
399prevScoreGapMatchSeq = -(gapOpen);
400 for(matchSeqPos = matchSeqEnd; matchSeqPos >= 0; matchSeqPos--) {
403 if((newScore = newScore - newGapCost) >
404(prevScoreGapMatchSeq = prevScoreGapMatchSeq - gapExtend))
405prevScoreGapMatchSeq = newScore;
408 if((newScore = scoreVector[matchSeqPos].noGap - newGapCost) >
410scoreVector[matchSeqPos].
gapExists- gapExtend))
411continueGapScore = newScore;
415 for(
f= 0;
f< numForbidden[queryPos];
f++) {
416 if((matchSeqPos >= forbiddenRanges[queryPos][2 *
f]) &&
417(matchSeqPos <= forbiddenRanges[queryPos][2*
f+ 1])) {
426prevScoreNoGapMatchSeq + matrixRow[matchSeq[matchSeqPos]];
430 if(newScore < prevScoreGapMatchSeq)
431newScore = prevScoreGapMatchSeq;
432 if(newScore < continueGapScore)
433newScore = continueGapScore;
434prevScoreNoGapMatchSeq = scoreVector[matchSeqPos].
noGap;
435scoreVector[matchSeqPos].
noGap= newScore;
436scoreVector[matchSeqPos].
gapExists= continueGapScore;
437 if(newScore > bestScore) {
438bestScore = newScore;
439bestQueryPos = queryPos;
440bestMatchSeqPos = matchSeqPos;
442 if(bestScore >= score_in)
445 if(bestScore >= score_in)
451*matchSeqStart = bestMatchSeqPos;
452*queryStart = bestQueryPos;
453*score_out = bestScore;
465 for(
f= 0;
f<
self->capacity;
f++)
free(self->ranges[
f]);
467 free(self->ranges);
self->ranges =
NULL;
468 free(self->numForbidden);
self->numForbidden =
NULL;
478 self->capacity = capacity;
479 self->numForbidden =
NULL;
480 self->ranges =
NULL;
481 self->isEmpty =
TRUE;
483 self->numForbidden = (
int*)
calloc(capacity,
sizeof(
int));
484 if(self->numForbidden ==
NULL)
486 self->ranges = (
int**)
calloc(capacity,
sizeof(
int*));
487 if(self->ranges ==
NULL)
489 for(
f= 0;
f< capacity;
f++) {
490 self->numForbidden[
f] = 0;
491 self->ranges[
f] = (
int*)
malloc(2 *
sizeof(
int));
492 if(self->ranges[
f] ==
NULL)
494 self->ranges[
f][0] = 0;
495 self->ranges[
f][1] = 0;
508 for(
f= 0;
f<
self->capacity;
f++) {
509 self->numForbidden[
f] = 0;
511 self->isEmpty =
TRUE;
524 for(
f= queryStart;
f< queryEnd;
f++) {
525 int last= 2 *
self->numForbidden[
f];
528realloc(self->ranges[
f], (
last+ 2) *
sizeof(
int));
529 if(new_ranges ==
NULL)
531 self->ranges[
f] = new_ranges;
533 self->ranges[
f][
last] = matchStart;
534 self->ranges[
f][
last+ 1] = matchEnd;
536 self->numForbidden[
f]++;
538 self->isEmpty =
FALSE;
547 int*matchSeqEnd,
int*queryEnd,
548 const Uint1* subject_data,
intsubject_length,
549 const Uint1* query_data,
intquery_length,
553 intpositionSpecific,
556 if(forbiddenRanges->
isEmpty) {
558queryEnd, subject_data,
560query_data, query_length,
566queryEnd, subject_data,
569query_length, matrix,
572forbiddenRanges->
ranges,
583 const Uint1* subject_data,
intsubject_length,
584 const Uint1* query_data,
591 intpositionSpecific,
594 if(forbiddenRanges->
isEmpty) {
596queryStart, subject_data,
597subject_length, query_data,
598matrix, gapOpen, gapExtend,
599matchSeqEnd, queryEnd,
600score_in, positionSpecific);
609matchSeqEnd, queryEnd,
612forbiddenRanges->
ranges,
Constants used in compositional score matrix adjustment.
#define COMPO_SCORE_MIN
Minimum score in a matrix.
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
uint8_t Uint1
1-byte (8-bit) unsigned integer
Type and macro definitions from C toolkit that are not defined in C++ toolkit.
#define TRUE
bool replacment for C indicating true.
#define FALSE
bool replacment for C indicating false.
void Blast_ForbiddenRangesRelease(Blast_ForbiddenRanges *self)
Release the storage associated with the fields of self, but do not delete self.
static int BLspecialSmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd, const Uint1 *matchSeq, int matchSeqLength, const Uint1 *query, int queryLength, int **matrix, int gapOpen, int gapExtend, const int *numForbidden, int **forbiddenRanges, int positionSpecific)
Compute the score and right-hand endpoints of the locally optimal Smith-Waterman alignment,...
int Blast_ForbiddenRangesPush(Blast_ForbiddenRanges *self, int queryStart, int queryEnd, int matchStart, int matchEnd)
Add some ranges to self.
int Blast_ForbiddenRangesInitialize(Blast_ForbiddenRanges *self, int capacity)
Initialize a new, empty Blast_ForbiddenRanges.
void Blast_ForbiddenRangesClear(Blast_ForbiddenRanges *self)
Reset self to be empty.
int Blast_SmithWatermanFindStart(int *score_out, int *matchSeqStart, int *queryStart, const Uint1 *subject_data, int subject_length, const Uint1 *query_data, int **matrix, int gapOpen, int gapExtend, int matchSeqEnd, int queryEnd, int score_in, int positionSpecific, const Blast_ForbiddenRanges *forbiddenRanges)
Find the left-hand endpoints of the locally optimal Smith-Waterman alignment given the score and righ...
int Blast_SmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd, const Uint1 *subject_data, int subject_length, const Uint1 *query_data, int query_length, int **matrix, int gapOpen, int gapExtend, int positionSpecific, const Blast_ForbiddenRanges *forbiddenRanges)
Compute the score and right-hand endpoints of the locally optimal Smith-Waterman alignment,...
static int BLspecialSmithWatermanFindStart(int *score_out, int *matchSeqStart, int *queryStart, const Uint1 *matchSeq, int matchSeqLength, const Uint1 *query, int **matrix, int gapOpen, int gapExtend, int matchSeqEnd, int queryEnd, int score_in, const int *numForbidden, int **forbiddenRanges, int positionSpecific)
Find the left-hand endpoints of the locally optimal Smith-Waterman alignment, subject to the restrict...
static int BLSmithWatermanFindStart(int *score_out, int *matchSeqStart, int *queryStart, const Uint1 *matchSeq, int matchSeqLength, const Uint1 *query, int **matrix, int gapOpen, int gapExtend, int matchSeqEnd, int queryEnd, int score_in, int positionSpecific)
Find the left-hand endpoints of the locally optimal Smith-Waterman alignment.
struct SwGapInfo SwGapInfo
A structure used internally by the Smith-Waterman algorithm to represent gaps.
static int BLbasicSmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd, const Uint1 *matchSeq, int matchSeqLength, const Uint1 *query, int queryLength, int **matrix, int gapOpen, int gapExtend, int positionSpecific)
Compute the score and right-hand endpoints of the locally optimal Smith-Waterman alignment.
Definitions for computing Smith-Waterman alignments.
An instance of Blast_ForbiddenRanges is used by the Smith-Waterman algorithm to represent ranges in t...
int * numForbidden
how many forbidden ranges at each database position
int ** ranges
forbidden ranges for each database position
int isEmpty
True if there are no forbidden ranges.
A structure used internally by the Smith-Waterman algorithm to represent gaps.
int noGap
score if opening a gap
int gapExists
score if continuing a gap
voidp calloc(uInt items, uInt size)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4