Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast__gapalign_8c_source.html below:

NCBI C++ ToolKit: src/algo/blast/core/blast_gapalign.c Source File

retval->

= chunksize;

}

(var->

== 0) {

retval->

= chunksize;

->next = retval;

state_struct->

= 0;

state_struct = state_struct->

;

max_d_1, d_diff, max_cost, gd,

;

reward, penalty, gap_open, gap_extend;

Mis_cost, GE_cost;

(score_params ==

|| (!ext_params && !Xdrop))

(score_params->

% 2 == 1) {

reward = 2*score_params->

;

penalty = -2*score_params->

;

gap_open = 2*score_params->

;

reward = score_params->

;

penalty = -score_params->

;

gap_open = score_params->

;

(gap_open == 0 && gap_extend == 0)

gap_extend = reward / 2 + penalty;

gamp->

= Xdrop;

d_diff = (Xdrop+reward/2)/(penalty+reward)+1;

,

(max_d + max_d + 6) *

(

) * 2);

Mis_cost = reward + penalty;

GE_cost = gap_extend+reward/2;

max_cost =

(Mis_cost, gap_open+GE_cost);

gd =

(&Mis_cost, &gap_open, &GE_cost);

d_diff = (Xdrop+reward/2)/gd+1;

(

= 1;

<= max_cost;

++)

max_subject_length,

(!gap_align_ptr || !sbp || !score_params || !ext_params)

*gap_align_ptr = gap_align;

gap_align->

= sbp;

max_subject_length, 0);

b_index, b_size, first_b_index, last_b_index, b_increment;

gap_open_extend;

* edit_script_row;

** edit_script;

*edit_start_offset;

edit_script_num_rows;

script, next_script, script_row, script_col;

num_extra_cells;

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

edit_script_num_rows = 100;

edit_script = (

**)

(

(

*) * edit_script_num_rows);

edit_start_offset = (

*)

(

(

) * edit_script_num_rows);

num_extra_cells = x_dropoff / gap_extend + 3;

num_extra_cells =

+ 3;

edit_start_offset[0] = 0;

score = -gap_open_extend;

score_array = gap_align->

;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 1;

<=

;

++) {

(score < -x_dropoff)

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

state_struct->

=

+ 1;

(reverse_sequence)

(a_index = 1; a_index <=

; a_index++) {

b_size - first_b_index + num_extra_cells);

+ 3 - first_b_index);

(a_index == edit_script_num_rows) {

edit_script_num_rows = edit_script_num_rows * 2;

edit_script = (

**)realloc(edit_script,

edit_script_num_rows *

edit_start_offset = (

*)realloc(edit_start_offset,

edit_script_num_rows *

edit_script[a_index] = state_struct->

+

state_struct->

+ 1;

edit_start_offset[a_index] = first_b_index;

edit_script_row = edit_script[a_index] - first_b_index;

orig_b_index = first_b_index;

(reverse_sequence)

matrix_row = matrix[

[

- a_index ] ];

matrix_row = matrix[

[ a_index ] ];

(reversed || reverse_sequence)

matrix_row = pssm[

- a_index];

matrix_row = pssm[a_index + query_offset];

(reverse_sequence)

b_ptr = &

[

- first_b_index];

b_ptr = &

[first_b_index];

last_b_index = first_b_index;

(b_index = first_b_index; b_index < b_size; b_index++) {

matrix_index = 0;

b_ptr += b_increment;

score_gap_col = score_array[b_index].

;

matrix_index = *b_ptr;

next_score = score_array[b_index].

+ matrix_row[ *b_ptr ];

(score < score_gap_col) {

score = score_gap_col;

(score < score_gap_row) {

score = score_gap_row;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

last_b_index = b_index;

(score > best_score) {

score_gap_row -= gap_extend;

score_gap_col -= gap_extend;

(score_gap_col < (score - gap_open_extend)) {

score_array[b_index].

= score - gap_open_extend;

score_array[b_index].

= score_gap_col;

script += script_col;

(score_gap_row < (score - gap_open_extend))

score_gap_row = score - gap_open_extend;

script += script_row;

score_array[b_index].

= score;

edit_script_row[b_index] = script;

(first_b_index == b_size || (fence_hit && *fence_hit))

(last_b_index + num_extra_cells + 3 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

(score_gap_row >= (best_score - x_dropoff) && b_size <=

) {

score_array[b_size].

= score_gap_row;

score_array[b_size].

= score_gap_row - gap_open_extend;

score_gap_row -= gap_extend;

state_struct->

+=

(b_index, b_size) - orig_b_index + 1;

(fence_hit && *fence_hit)

(a_index > 0 || b_index > 0) {

edit_script[a_index][b_index - edit_start_offset[a_index]];

(edit_start_offset);

b_index, b_size, first_b_index, last_b_index, b_increment;

gap_open_extend;

num_extra_cells;

(

,

,

,

, a_offset, b_offset, edit_block, gap_align,

score_params, query_offset, reversed, reverse_sequence,

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

num_extra_cells = x_dropoff / gap_extend + 3;

num_extra_cells =

+ 3;

score_array = gap_align->

;

score = -gap_open_extend;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 1;

<=

;

++) {

(score < -x_dropoff)

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

(reverse_sequence)

(a_index = 1; a_index <=

; a_index++) {

(reverse_sequence)

matrix_row = matrix[

[

- a_index ] ];

matrix_row = matrix[

[ a_index ] ];

(reversed || reverse_sequence)

matrix_row = pssm[

- a_index];

matrix_row = pssm[a_index + query_offset];

(reverse_sequence)

b_ptr = &

[

- first_b_index];

b_ptr = &

[first_b_index];

last_b_index = first_b_index;

(b_index = first_b_index; b_index < b_size; b_index++) {

b_ptr += b_increment;

score_gap_col = score_array[b_index].

;

next_score = score_array[b_index].

+ matrix_row[ *b_ptr ];

(score < score_gap_col)

score = score_gap_col;

(score < score_gap_row)

score = score_gap_row;

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

score_gap_row -= gap_extend;

score_gap_col -= gap_extend;

score_array[b_index].

=

(score - gap_open_extend,

score_gap_row =

(score - gap_open_extend, score_gap_row);

score_array[b_index].

= score;

(first_b_index == b_size)

(last_b_index + num_extra_cells + 3 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

(score_gap_row >= (best_score - x_dropoff) && b_size <=

) {

score_array[b_size].

= score_gap_row;

score_array[b_size].

= score_gap_row - gap_open_extend;

score_gap_row -= gap_extend;

b_index, b_size, first_b_index, last_b_index, b_increment;

* b_ptr;

gap_open_extend;

num_extra_cells;

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

num_extra_cells = x_dropoff / gap_extend + 3;

num_extra_cells =

+ 3;

score_array = gap_align->

;

score = -gap_open_extend;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 1;

<=

;

++) {

(score < -x_dropoff)

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

score -= gap_extend;

(reverse_sequence)

(a_index = 1; a_index <=

; a_index++) {

(reverse_sequence)

matrix_row = matrix[

[

- a_index ] ];

matrix_row = matrix[

[ a_index ] ];

(reverse_sequence)

matrix_row = pssm[

- a_index];

matrix_row = pssm[a_index + query_offset];

(reverse_sequence)

b_ptr = &

[

- first_b_index];

b_ptr = &

[first_b_index];

last_b_index = first_b_index;

(b_index = first_b_index; b_index < b_size; b_index++) {

b_ptr += b_increment;

next_score = score_array[b_index].

+ matrix_row[ *b_ptr ];

(b_index != b_gap) {

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score_array[b_index].

= score;

score_gap_col = score_array[b_index].

;

(score < score_gap_col)

score = score_gap_col;

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score_gap_col -= gap_extend;

(score - gap_open_extend, score_gap_col);

score_array[b_index].

= score;

score_gap_row = score;

(b_index = first_b_index; b_index < b_size; b_index++) {

b_ptr += b_increment;

next_score = score_array[b_index].

+ matrix_row[ *b_ptr ];

(b_index != b_gap) {

(score < score_gap_row)

score = score_gap_row;

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score_gap_row -= gap_extend;

score_gap_row =

(score - gap_open_extend,

score_array[b_index].

= score;

score_gap_col = score_array[b_index].

;

(score < score_gap_col)

score = score_gap_col;

(score < score_gap_row)

score = score_gap_row;

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score_gap_row -= gap_extend;

score_gap_col -= gap_extend;

(score - gap_open_extend, score_gap_col);

score_gap_row =

(score - gap_open_extend,

score_array[b_index].

= score;

(first_b_index == b_size)

b_gap = first_b_index;

(last_b_index + num_extra_cells + 3 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

(score_gap_row >= (best_score - x_dropoff) && b_size <=

) {

score_array[b_size].

= score_gap_row;

score_array[b_size].

= score_gap_row - gap_open_extend;

score_gap_row -= gap_extend;

b_index, b_size, first_b_index, last_b_index;

gap_open_extend;

score_other_frame1;

score_other_frame2;

** edit_script;

* edit_script_row;

*edit_start_offset;

edit_script_num_rows;

script, next_script;

num_extra_cells;

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

shift_penalty = score_params->

;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

edit_script_num_rows = 100;

edit_script = (

**)

(

(

*) * edit_script_num_rows);

edit_start_offset = (

*)

(

(

) * edit_script_num_rows);

num_extra_cells =

* (x_dropoff / gap_extend + 5);

num_extra_cells =

+ 5;

edit_start_offset[0] = 0;

score_array = gap_align->

;

score = -gap_open_extend;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 3;

<=

+ 2;

+= 3) {

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

(score < -x_dropoff)

score -= gap_extend;

state_struct->

= b_size + 1;

(a_index = 1; a_index <=

; a_index++) {

b_size - first_b_index + num_extra_cells);

+ 5 - first_b_index);

(a_index == edit_script_num_rows) {

edit_script_num_rows = edit_script_num_rows * 2;

edit_script = (

**)realloc(edit_script,

edit_script_num_rows *

edit_start_offset = (

*)realloc(edit_start_offset,

edit_script_num_rows *

edit_script[a_index] = state_struct->

+

state_struct->

+ 1;

edit_start_offset[a_index] = first_b_index;

edit_script_row = edit_script[a_index] - first_b_index;

orig_b_index = first_b_index;

matrix_row = matrix[

[ a_index * increment ] ];

matrix_row = pssm[

- a_index];

matrix_row = pssm[a_index + query_offset];

score_other_frame1 =

;

score_other_frame2 =

;

last_b_index = first_b_index;

b_index = first_b_index;

(b_index < b_size) {

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col1);

(score == score_col1) {

(score + shift_penalty == score_other_frame1) {

(score_other_frame1 == score_col2)

(score_other_frame2 == score_col3)

score += matrix_row[

[ b_index * increment ] ];

score_other_frame1 =

(score_col1, score_array[b_index].best);

score_col1 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row1)) {

(score_gap_col > score_row1) {

score = score_gap_col;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row1 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row1 -= gap_extend;

(score > score_row1)

score_gap_col -= gap_extend;

(score < score_gap_col) {

score_array[b_index].

= score_gap_col;

score_array[b_index].

= score;

edit_script_row[b_index++] = script;

(b_index >= b_size) {

score_row1 = score_row2;

score_row2 = score_row3;

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col2);

(score == score_col2) {

(score + shift_penalty == score_other_frame1) {

(score_other_frame1 == score_col1)

(score_other_frame2 == score_col3)

score += matrix_row[

[ b_index * increment ] ];

score_other_frame2 =

(score_col2, score_array[b_index].best);

score_col2 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row2)) {

score =

(score_gap_col, score_row2);

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

(score == score_gap_col)

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row2 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row2 -= gap_extend;

(score > score_row2)

score_gap_col -= gap_extend;

(score < score_gap_col) {

score_array[b_index].

= score_gap_col;

score_array[b_index].

= score;

edit_script_row[b_index++] = script;

(b_index >= b_size) {

score_row2 = score_row1;

score_row1 = score_row3;

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col3);

(score == score_col3) {

(score + shift_penalty == score_other_frame1) {

(score_other_frame1 == score_col1)

(score_other_frame2 == score_col2)

score += matrix_row[

[ b_index * increment ] ];

score_other_frame1 = score_other_frame2;

score_other_frame2 =

(score_col3, score_array[b_index].best);

score_col3 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row3)) {

score =

(score_gap_col, score_row3);

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

(score == score_gap_col)

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row3 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row3 -= gap_extend;

(score > score_row3)

score_gap_col -= gap_extend;

(score < score_gap_col) {

score_array[b_index].

= score_gap_col;

score_array[b_index].

= score;

edit_script_row[b_index++] = script;

(first_b_index == b_size)

(last_b_index + num_extra_cells + 5 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

score =

(score_row1, score_row2);

score =

(score, score_row3);

(score >= (best_score - x_dropoff) && b_size <

+ 1) {

score_array[b_size].

= score_row1;

score_array[b_size].

= score_row1 - gap_open_extend;

score_row1 -= gap_extend;

score_array[b_size+1].

= score_row2;

score_array[b_size+1].

= score_row2 - gap_open_extend;

score_row2 -= gap_extend;

score_array[b_size+2].

= score_row3;

score_array[b_size+2].

= score_row3 - gap_open_extend;

score_row3 -= gap_extend;

score -= gap_extend;

b_size =

(b_size,

+ 1);

state_struct->

+=

(b_index, b_size) - orig_b_index + 1;

last_b_index =

(b_size + 4,

+ 3);

(b_size < last_b_index) {

a_index = *a_offset;

b_index = *b_offset;

(a_index > 0 || b_index > 0) {

edit_script[a_index][b_index - edit_start_offset[a_index]];

(edit_start_offset);

(edit_script);

b_index, b_size, first_b_index, last_b_index;

gap_open_extend;

num_extra_cells;

score_other_frame1;

score_other_frame2;

edit_block, gap_align,

score_params, query_offset,

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

shift_penalty = score_params->

;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

num_extra_cells =

* (x_dropoff / gap_extend + 5);

num_extra_cells =

+ 5;

score_array = gap_align->

;

score = -gap_open_extend;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 3;

<=

+ 2;

+= 3) {

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

(score < -x_dropoff)

score -= gap_extend;

(a_index = 1; a_index <=

; a_index++) {

matrix_row = matrix[

[ a_index * increment ] ];

matrix_row = pssm[

- a_index];

matrix_row = pssm[a_index + query_offset];

score_other_frame1 =

;

score_other_frame2 =

;

last_b_index = first_b_index;

b_index = first_b_index;

(b_index < b_size) {

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col1) +

matrix_row[

[ b_index * increment ] ];

score_other_frame1 =

(score_col1, score_array[b_index].best);

score_col1 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row1)) {

score =

(score_gap_col, score_row1);

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row1 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row1 -= gap_extend;

score_row1 =

(score, score_row1);

score_gap_col - gap_extend);

(++b_index >= b_size) {

score_row1 = score_row2;

score_row2 = score_row3;

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col2) +

matrix_row[

[ b_index * increment ] ];

score_other_frame2 =

(score_col2, score_array[b_index].best);

score_col2 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row2)) {

score =

(score_gap_col, score_row2);

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row2 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row2 -= gap_extend;

score_row2 =

(score, score_row2);

score_gap_col - gap_extend);

(++b_index >= b_size) {

score_row2 = score_row1;

score_row1 = score_row3;

score =

(score_other_frame1, score_other_frame2) - shift_penalty;

score =

(score, score_col3) +

matrix_row[

[ b_index * increment ] ];

score_other_frame1 = score_other_frame2;

score_other_frame2 =

(score_col3, score_array[b_index].best);

score_col3 = score_array[b_index].

;

score_gap_col = score_array[b_index].

;

(score <

(score_gap_col, score_row3)) {

score =

(score_gap_col, score_row3);

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

score_array[b_index].

= score_gap_col - gap_extend;

score_row3 -= gap_extend;

(best_score - score > x_dropoff) {

(first_b_index == b_index)

first_b_index = b_index + 1;

last_b_index = b_index;

score_array[b_index].

= score;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score -= gap_open_extend;

score_row3 -= gap_extend;

score_row3 =

(score, score_row3);

score_gap_col - gap_extend);

(first_b_index == b_size)

(b_size + num_extra_cells + 5 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

score =

(score_row1, score_row2);

score =

(score, score_row3);

(score >= (best_score - x_dropoff) && b_size <

+ 1) {

score_array[b_size].

= score_row1;

score_array[b_size].

= score_row1 - gap_open_extend;

score_row1 -= gap_extend;

score_array[b_size+1].

= score_row2;

score_array[b_size+1].

= score_row2 - gap_open_extend;

score_row2 -= gap_extend;

score_array[b_size+2].

= score_row3;

score_array[b_size+2].

= score_row3 - gap_open_extend;

score_row3 -= gap_extend;

score -= gap_extend;

b_size =

(b_size,

+ 1);

last_b_index =

(b_size + 4,

+ 3);

(b_size < last_b_index) {

query_length = 0;

query_end_pt = 0;

query_length = query_end_pt - *query_start;

single_query->

= query_length;

query_start = 0;

query_out, &query_start);

(rev_prelim_tback ==

|| fwd_prelim_tback ==

)

(fwd_prelim_tback->

> 0 && rev_prelim_tback->

> 0 &&

(

=0;

< rev_prelim_tback->

;

++) {

esp->

[index] = op->

;

(fwd_prelim_tback->

== 0)

esp->

[index-1] += fwd_prelim_tback->

[(fwd_prelim_tback->

)-1].num;

= fwd_prelim_tback->

- 2;

= fwd_prelim_tback->

- 1;

(;

>= 0;

--) {

esp->

[index] = op->

;

q_seed_start,

s_seed_start,

gap_align->

= score;

(--op < 0)

;

qd -= esp->

[op];

sd -= esp->

[op];

qd -= esp->

[op];

sd -= esp->

[op];

}

(qd > 0 || sd > 0);

esp->

[op] = -

(qd, sd);

(; op < pos-1; op++) esp->

[op] = 0;

esp->

[pos] += bf;

esp->

[pos-1] = (qd>0) ? qd : -qd;

(++op >= esp->

)

;

qd -= esp->

[op];

sd -= esp->

[op];

qd -= esp->

[op];

sd -= esp->

[op];

}

(qd > 0 || sd > 0);

esp->

[op] = -

(qd, sd);

(; op > pos+1; op--) esp->

[op] = 0;

esp->

[pos] += af;

esp->

[pos+1] = (qd>0) ? qd : -qd;

(

=0, j=-1;

<esp->

;

++) {

(esp->

[

] == 0)

;

esp->

[j] += esp->

[

];

esp->

[j] = esp->

[

];

d = esp->

[j] - esp->

[

];

esp->

[j-1] += esp->

[

];

(j == 0 &&

- j > 0) {

esp->

[j-1] += esp->

[j];

esp->

[j-1] += esp->

[j];

, j, nm1, nm2, d;

*q1, *s1;

(q1=q, s1=s,

=0;

<esp->

;

++) {

(esp->

[

] == 0)

;

(esp->

[

] >= 12) {

(q1-nm1>=q && (*(q1-nm1) == *(s1-nm1))) ++nm1;

q1 += esp->

[

];

s1 += esp->

[

];

(i < esp->

-1) {

((q1+1<qf) && (s1+1<sf) && (*(q1++) == *(s1++))) ++nm2;

q1 += esp->

[

];

s1 += esp->

[

];

q1 += esp->

[

];

s1 += esp->

[

];

(

=0;

<esp->

;

++) {

q += esp->

[

];

s += esp->

[

];

&& esp->

[

-2] > 0) {

d = esp->

[

] + esp->

[

-1] + esp->

[

-2];

(esp->

[

-2]) = 0;

(esp->

[

-1]) = 2;

(esp->

[

]) = 0;

}

(d < 12) {

q -= esp->

[

-1];

s -= esp->

[

-1];

(j=0; j<esp->

[

-1]; ++j, ++q1, ++s1, ++q, ++s) {

(*q1 == *s1) nm1++;

(*q == *s) nm2++;

(j=0; j<d; ++j, ++q, ++s) {

(*q == *s) nm2++;

(nm2 >= nm1 - d) {

(esp->

[

-2]) -= d;

(esp->

[

-1]) += d;

(esp->

[

]) -= d;

q += esp->

[

];

s += esp->

[

];

q_avail, s_avail;

q_ext_l, q_ext_r, s_ext_l, s_ext_r;

q_seed_start = q_off;

s_seed_start = s_off;

q_avail = query_length - q_off;

s_avail = subject_length - s_off;

(!compressed_subject) {

new_dist, xdrop;

fwd_prelim_tback, rem, fence_hit, &fwd_start_point);

(fence_hit && *fence_hit) {

(score >=0)

;

(compressed_subject)

new_dist, xdrop, score1;

rev_prelim_tback, rem, fence_hit, &rev_start_point);

(fence_hit && *fence_hit) {

(q_ext_r + s_ext_r + q_ext_l + s_ext_l)*score_params->

/2 -

}

(score_params->

% 2 == 1) {

(!compressed_subject);

q_box_l = q_off - q_ext_l;

s_box_l = s_off - s_ext_l;

q_box_r = q_off + q_ext_r;

s_box_r = s_off + s_ext_r;

q_seed_start_l = q_off - rev_start_point.

;

s_seed_start_l = s_off - rev_start_point.

;

q_seed_start_r = q_off + fwd_start_point.

;

s_seed_start_r = s_off + fwd_start_point.

;

valid_seed_len_l = 0;

valid_seed_len_r = 0;

(q_seed_start_r < q_box_r && s_seed_start_r < s_box_r) {

valid_seed_len_r =

(q_box_r - q_seed_start_r,

s_box_r - s_seed_start_r);

valid_seed_len_r =

(valid_seed_len_r,

q_seed_start_r = q_off;

s_seed_start_r = s_off;

(q_seed_start_l > q_box_l && s_seed_start_l > s_box_l) {

valid_seed_len_l =

(q_seed_start_l - q_box_l,

s_seed_start_l - s_box_l);

valid_seed_len_l =

(valid_seed_len_l,

q_seed_start_l = q_off;

s_seed_start_l = s_off;

(valid_seed_len_r > valid_seed_len_l) {

q_seed_start = q_seed_start_r + valid_seed_len_r;

s_seed_start = s_seed_start_r + valid_seed_len_r;

q_seed_start = q_seed_start_l - valid_seed_len_l;

s_seed_start = s_seed_start_l - valid_seed_len_l;

q_off-q_ext_l, s_off-s_ext_l,

q_off+q_ext_r, s_off+s_ext_r,

q_seed_start, s_seed_start,

q_length, s_length;

private_q_start, private_s_start;

score_right = 0, score_left = 0;

offset_adjustment;

(q_length > query_blk->

|| s_length > subject_blk->

)

&private_q_start, &private_s_start, gap_align,

score_params,

, x_dropoff);

gap_align->

= q_length - private_q_start;

(q_length < query_blk->length &&

s_length < subject_blk->length)

query_blk->

-q_length,

(score_right < 0)

gap_align->

= score_right+score_left;

a_index, a_base_pair;

b_index, b_size, first_b_index, last_b_index, b_increment;

num_extra_cells;

gap_open_extend;

gap_open = score_params->

;

gap_open_extend = gap_open + gap_extend;

(x_dropoff < gap_open_extend)

x_dropoff = gap_open_extend;

(

<= 0 ||

<= 0)

num_extra_cells = x_dropoff / gap_extend + 3;

num_extra_cells =

+ 3;

score_array = gap_align->

;

score = -gap_open_extend;

score_array[0].

= 0;

score_array[0].

= -gap_open_extend;

(

= 1;

<=

;

++) {

(score < -x_dropoff)

score_array[

].

= score;

score_array[

].

= score - gap_open_extend;

score -= gap_extend;

(reverse_sequence)

(a_index = 1; a_index <=

; a_index++) {

(reverse_sequence) {

matrix_row = matrix[a_base_pair];

(3-((a_index-1)%4)));

matrix_row = matrix[a_base_pair];

(reverse_sequence)

b_ptr = &

[

- first_b_index];

b_ptr = &

[first_b_index];

last_b_index = first_b_index;

(b_index = first_b_index; b_index < b_size; b_index++) {

b_ptr += b_increment;

score_gap_col = score_array[b_index].

;

next_score = score_array[b_index].

+ matrix_row[ *b_ptr ];

(score < score_gap_col)

score = score_gap_col;

(score < score_gap_row)

score = score_gap_row;

(best_score - score > x_dropoff) {

(b_index == first_b_index)

last_b_index = b_index;

(score > best_score) {

*a_offset = a_index;

*b_offset = b_index;

score_gap_row -= gap_extend;

score_gap_col -= gap_extend;

score_array[b_index].

=

(score - gap_open_extend,

score_gap_row =

(score - gap_open_extend, score_gap_row);

score_array[b_index].

= score;

(first_b_index == b_size)

(last_b_index + num_extra_cells + 3 >= gap_align->

) {

score_array = (

*)realloc(score_array,

gap_align->

= score_array;

(last_b_index < b_size - 1) {

b_size = last_b_index + 1;

(score_gap_row >= (best_score - x_dropoff) && b_size <=

) {

score_array[b_size].

= score_gap_row;

score_array[b_size].

= score_gap_row - gap_open_extend;

score_gap_row -= gap_extend;

index1, max_offset, score, max_score, hsp_end;

* query_var,* subject_var;

*q_retval = q_start + q_length/2;

*s_retval = s_start + q_length/2;

query_var =

+ q_start;

subject_var =

+ s_start;

(index1=q_start; index1<hsp_end; index1++) {

(!(positionBased))

score += sbp->

->

[*query_var][*subject_var];

query_var++; subject_var++;

max_offset = hsp_end - 1;

hsp_end = q_start +

(q_length, s_length);

(index1=q_start +

; index1<hsp_end; index1++) {

(!(positionBased)) {

score += sbp->

->

[*query_var][*subject_var];

(score > max_score) {

max_offset = index1;

query_var++; subject_var++;

*q_retval = max_offset;

*s_retval = (max_offset - q_start) + s_start;

(!(positionBased))

score += sbp->

->

[*query_var][*subject_var];

query_var++; subject_var++;

hspMaxIdentRun = 10;

index, max_offset, score, max_score, q_start, s_start, q_len;

q =

+ q_start;

((q-

< q_len) && (*q++ == *s++)) {

(score > hspMaxIdentRun)

;

q =

+ q_start;

((q-

>= 0) && (*q-- == *s--)) {

(score > hspMaxIdentRun)

;

hspMaxIdentRun *= 1.5;

q =

+ q_start;

max_offset = q_start;

prev_match =

;

(index = q_start; index < q_start + q_len; index++) {

= (*q++ == *s++);

(

!= prev_match) {

prev_match =

;

}

(score > max_score) {

max_offset = index - score/2;

}

(

) {

(score > hspMaxIdentRun) {

max_offset = index - hspMaxIdentRun/2;

(

&& score > max_score) {

max_offset = index - score/2;

(max_score > 0) {

index1, max_offset, score, max_score, hsp_end;

* query_var,* subject_var;

max_offset = q_start + q_length/2;

query_var =

+ q_start;

subject_var =

+ s_start;

(index1=q_start; index1<hsp_end; index1++) {

(!(positionBased))

score += sbp->

->

[*query_var][*subject_var];

query_var++; subject_var++;

max_offset = hsp_end - 1;

hsp_end = q_start +

(q_length, s_length);

(index1=q_start +

; index1<hsp_end; index1++) {

(!(positionBased)) {

score += sbp->

->

[*query_var][*subject_var];

(score > max_score) {

max_offset = index1;

query_var++; subject_var++;

max_offset = q_start;

(!retval->

) {

(i < init_hitlist->total) {

context <= query_info->last_context) {

(context <= query_info->last_context);

nodes[num_nodes].

= &init_array[

];

((i < init_hitlist->total) &&

nodes[num_nodes].

= &init_array[

];

(k = num_nodes - 1;k >= 0;k--) {

(j = k + 1;j < num_nodes;j++) {

new_score = self_score + nodes[j].

;

new_score +=

(

(q_diff, s_diff) * 3,

new_score -=

(

(q_diff - s_diff), 1) + score_params->

;

(new_score > nodes[k].best_score) {

nodes[k].

= &nodes[j];

(k = 0;k < num_nodes;k++) {

(nodes[k].init_hsp->ungapped_data) {

(nodes[k].init_hsp->ungapped_data);

(init_hitlist->

> 0 &&

init_hitlist->

--;

(k = 0;k < init_hitlist->

- 1;k++) {

init_hitlist->

--;

(init_hitlist->

- 1 > k &&

init_hitlist->

--;

q_start, s_start, q_end, s_end;

rps_cutoff_index = 0;

kRestrictedMult = 0.68;

redo_index = -1;

redo_query = -1;

(!

|| !

|| !gap_align || !score_params || !ext_params ||

!hit_params || !init_hitlist || !hsp_list_ptr)

(init_hitlist->

== 0)

hit_params, word_params, init_hitlist);

restricted_align_array =

program_number) + 1,

(

= 0;

< init_hitlist->

;

++) {

query_index = -1;

contxt <= query_info->last_context; contxt++) {

q_off < query_info->contexts[contxt].query_offset +

(query_index >= 0);

(found[query_index]) {

found[query_index] =

;

(

)(kRestrictedMult *

restricted_align_array[query_index] =

;

restricted_align_array[query_index] =

;

rps_cutoff_index =

->oid;

(*hsp_list_ptr ==

)

hsp_list = *hsp_list_ptr;

(index=0; index<init_hitlist->

; index++)

(init_hsp_array[index].ungapped_data->score > hit_params->

[query_index])

found_high_score[query_index] = 1;

(index=0; index<init_hitlist->

; index++)

tmp_init_hsp = init_hsp_array[index];

tmp_ungapped_data = *(init_hsp_array[index].

);

init_hsp = &tmp_init_hsp;

(index < redo_index && query_index != redo_query) {

(restricted_align_array && restricted_align_array[query_index]) {

restricted_alignment =

;

(!found_high_score[query_index])

tmp_hsp.

= score;

cutoff, restricted_cutoff = 0;

(restricted_alignment)

restricted_cutoff = (

)(kRestrictedMult * cutoff);

score_params, init_hsp,

restricted_alignment,

(restricted_alignment &&

gap_align->

< cutoff &&

gap_align->

>= restricted_cutoff) {

(restricted_align_array);

restricted_align_array[query_index] =

;

(index2 = 0; index2 < hsp_list->

; index2++) {

(q_index2 != query_index) {

hsp_list = new_hsp_list;

redo_query = query_index;

}

(is_greedy) {

gap_align, score_params,

gap_align, score_params, init_hsp);

(rpsblast_pssms) {

(found_high_score);

(gap_align->

>= cutoff) {

query_frame = 0;

query_frame = -query_frame;

(found_high_score);

(found_high_score);

(restricted_align_array) {

(restricted_align_array);

(rpsblast_pssms) {

*hsp_list_ptr = hsp_list;

s_off,

* private_q_start,

* private_s_start,

private_s_start, private_q_start, score_only, edit_block,

gap_align, score_params, psi_offset, reversed);

private_q_start, private_s_start, score_only, edit_block,

gap_align, score_params, psi_offset, reversed);

query_offset,

query_length,

* start_shift)

subject_length = *subject_length_ptr;

max_extension_left, max_extension_right;

s_offset = *subject_offset_ptr;

max_extension_right = query_length - query_offset +

;

(s_offset <= max_extension_left) {

*start_shift = s_offset - max_extension_left;

*subject_offset_ptr = max_extension_left;

*subject_length_ptr =

(subject_length, s_offset + max_extension_right) - *start_shift;

found_start, found_end;

q_length=0, s_length=0, score_right, score_left;

private_q_start, private_s_start;

subject_shift = 0;

(gap_align ==

)

found_start =

;

(q_length != 0 && s_length != 0) {

found_start =

;

&private_q_start, &private_s_start,

,

,

gap_align, score_params, q_length,

, switch_seq);

(restricted_alignment) {

&private_q_start, &private_s_start,

gap_align, score_params,

&private_q_start, &private_s_start,

,

, gap_align, score_params,

gap_align->

= q_length - private_q_start;

gap_align->

= s_length - private_s_start + subject_shift;

(q_length < query_length && s_length < subject_length) {

query_length-q_length+1, subject_length-s_length+1,

(restricted_alignment) {

query_length-q_length,

subject_length-s_length,

gap_align, score_params,

query_length-q_length,

subject_length-s_length,

,

, gap_align, score_params,

(found_start ==

) {

(found_end ==

) {

gap_align->

= score_right+score_left;

nucl_align_length,

(

= 0;

< rev_prelim_tback->

;

++) {

(next_op == last_op) {

last_num += next_num;

last_num = next_num;

(

= fwd_prelim_tback->

- 1;

>= 0;

--) {

new_script->

--;

(new_script->

== 0)

fwd_prelim_tback->

=

+ 1;

(

=0;

<e_script->

;

++)

total_actions=0;

last_op = e_script->

[

];

total_actions = last_op * e_script->

[

];

(num_nuc + total_actions >= nucl_align_length) {

e_script->

[

] = (nucl_align_length - num_nuc +

last_op - 1) / last_op;

num_nuc += total_actions;;

(

=0;

<e_script->

;

++)

(e_script->

[

] % 3 != 0 && e_script->

[

] > 1) {

extra_needed += e_script->

[

] - 1;

(

=0;

<e_script->

;

++)

new_esp->

[new_esp_i] = e_script->

[

];

last_op = e_script->

[

];

(last_op % 3 != 0 && e_script->

[

] > 1) {

num_ops = e_script->

[

];

new_esp->

[new_esp_i-1] = 1;

(esp_index = 1; esp_index < num_ops; esp_index++) {

new_esp->

[new_esp_i] = 1;

new_esp->

[new_esp_i] = last_op;

*edit_script_ptr = e_script;

last_op = e_script->

[0];

(

=1;

<e_script->

;

++)

(e_script->

[

])++;

last_op = e_script->

[

];

score_right, score_left, private_q_length, private_s_length;

q_length, s_length;

(gap_align ==

)

q_length = query_length;

s_length = subject_length;

q_start, s_start, &private_q_length, &private_s_length,

, rev_prelim_tback, gap_align, score_params, q_start,

gap_align->

= q_start - private_q_length;

score_left =

(

,

, q_start+1, s_start+1, &private_q_length, &private_s_length, rev_prelim_tback,

gap_align->

= q_start - private_q_length + 1;

((! (fence_hit && *fence_hit)) &&

(q_start < q_length) &&

(s_start < s_length)) {

q_length-q_start, s_length-s_start,

&private_q_length, &private_s_length,

, fwd_prelim_tback,

gap_align, score_params, q_start,

, switch_seq);

q_length-q_start-1, s_length-s_start-1, &private_q_length,

&private_s_length, fwd_prelim_tback, gap_align,

gap_align->

= q_start + private_q_length + 1;

gap_align->

= s_start + private_s_length + 1;

(found_end ==

) {

nucl_align_length;

fwd_prelim_tback, nucl_align_length,

score_left += score_params->

+

(

= 1;

< esp->

;

++) {

esp->

[

-1] = esp->

[

];

score_right += score_params->

+

gap_align->

= score_right + score_left;

(*hsp_list_ptr !=

)

hsp_list = *hsp_list_ptr;

(!init_hitlist) {

*hsp_list_ptr =

;

(index = 0; index < init_hitlist->

; ++index) {

*hsp_list_ptr = hsp_list;

#define COMPRESSION_RATIO

Compression ratio of nucleotide bases (4 bases in 1 byte)

#define sfree(x)

Safe free a pointer: belongs to a higher level header.

#define CODON_LENGTH

Codons are always of length 3.

#define NUM_FRAMES

Number of frames to which we translate in translating searches.

void Blast_InitHitListSortByScore(BlastInitHitList *init_hitlist)

Sort array of initial HSPs by score.

Boolean Blast_InitHitListIsSortedByScore(BlastInitHitList *init_hitlist)

Check if array of initial HSPs is sorted by score.

Boolean BlastGetOffsetsForGappedAlignment(const Uint1 *query, const Uint1 *subject, const BlastScoreBlk *sbp, BlastHSP *hsp, Int4 *q_retval, Int4 *s_retval)

Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the mid...

Int2 BLAST_GappedAlignmentWithTraceback(EBlastProgramType program, const Uint1 *query, const Uint1 *subject, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 q_start, Int4 s_start, Int4 query_length, Int4 subject_length, Boolean *fence_hit)

Perform a gapped alignment with traceback.

static void s_SetUpLocalBlastSequenceBlk(const BLAST_SequenceBlk *concatenated_query, const BlastQueryInfo *query_info, Int4 context, BLAST_SequenceBlk *single_query, Int4 *query_start)

Set up a BLAST_SequenceBlk structure for a single query sequence.

static Int2 s_BlastOOFTracebackToGapEditScript(GapPrelimEditBlock *rev_prelim_tback, GapPrelimEditBlock *fwd_prelim_tback, Int4 nucl_align_length, GapEditScript **edit_script_ptr)

Converts OOF traceback from a gapped alignment to a GapEditScript.

Int4 BlastGetStartForGappedAlignment(const Uint1 *query, const Uint1 *subject, const BlastScoreBlk *sbp, Uint4 q_start, Uint4 q_length, Uint4 s_start, Uint4 s_length)

Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the mid...

#define RESTRICT_SIZE

For restricted gapped alignment, gaps may only start once in this many sequence offsets.

static NCBI_INLINE void s_AdjustInitialHSPOffsets(BlastInitHSP *init_hsp, Int4 query_start)

Adjust the HSP offsets in the initial ungapped HSP structure given the query start.

#define MININT

Lower bound for scores.

static Boolean s_GapPurgeState(GapStateArrayStruct *state_struct)

Remove a state from a state structure.

Int4 Blast_SemiGappedAlign(const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed, Boolean reverse_sequence, Boolean *fence_hit)

Low level function to perform gapped extension in one direction with or without traceback.

Int2 BLAST_GetGappedScore(EBlastProgramType program_number, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, BLAST_SequenceBlk *subject, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, const BlastHitSavingParameters *hit_params, const BlastInitialWordParameters *word_params, BlastInitHitList *init_hitlist, BlastHSPList **hsp_list_ptr, BlastGappedStats *gapped_stats, Boolean *fence_hit)

Performs gapped extension for all non-Mega BLAST programs, given that ungapped extension has been don...

#define CHUNKSIZE

Minimal size of a chunk for state array allocation.

static void s_UpdateEditScript(GapEditScript *esp, int pos, int bf, int af)

static SGreedyAlignMem * s_BlastGreedyAlignsFree(SGreedyAlignMem *gamp)

Deallocate the memory for greedy gapped alignment.

static Int2 s_BlastGreedyGapAlignStructFill(BlastGapAlignStruct *gap_align, Int4 q_start, Int4 s_start, Int4 q_end, Int4 s_end, Int4 q_seed_start, Int4 s_seed_start, Int4 score, GapEditScript *esp)

Fills the BlastGapAlignStruct structure with the results of a greedy gapped extension.

static int s_CompareInitHSPsByQueryOffsetScore(const void *v1, const void *v2)

Int2 BLAST_GetUngappedHSPList(BlastInitHitList *init_hitlist, BlastQueryInfo *query_info, BLAST_SequenceBlk *subject, const BlastHitSavingOptions *hit_options, BlastHSPList **hsp_list_ptr)

Convert initial HSP list to an HSP list: to be used in ungapped search.

static void s_ReduceGaps(GapEditScript *esp, const Uint1 *q, const Uint1 *s, const Uint1 *qf, const Uint1 *sf)

static Int2 s_BlastProtGappedAlignment(EBlastProgramType program, BLAST_SequenceBlk *query_in, BLAST_SequenceBlk *subject_in, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, BlastInitHSP *init_hsp, Boolean restricted_alignment, Boolean *fence_hit)

Performs gapped extension for protein sequences, given two sequence blocks, scoring and extension opt...

Int4 ALIGN_EX(const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed, Boolean reverse_sequence, Boolean *fence_hit)

Low level function to perform dynamic programming gapped extension with traceback.

#define MAX_SUBJECT_OFFSET

Maximal subject length after which the offsets are adjusted to a subsequence.

static Int4 s_OutOfFrameGappedAlign(const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed)

Low level function to perform gapped extension with out-of-frame gapping with or without traceback.

static NCBI_INLINE Int4 s_GetUngappedHSPContext(const BlastQueryInfo *query_info, const BlastInitHSP *init_hsp)

Simple wrapper around binary search function for BlastQueryInfo structure to obtain the context in wh...

GapEditScript * Blast_PrelimEditBlockToGapEditScript(GapPrelimEditBlock *rev_prelim_tback, GapPrelimEditBlock *fwd_prelim_tback)

Convert the initial list of traceback actions from a non-OOF gapped alignment into a blast edit scrip...

static Int4 s_BlastAlignPackedNucl(Uint1 *B, Uint1 *A, Int4 N, Int4 M, Int4 *pej, Int4 *pei, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Boolean reverse_sequence, Int4 x_dropoff)

Aligns two nucleotide sequences, one (A) should be packed in the same way as the BLAST databases,...

static Int4 s_OutOfFrameSemiGappedAlignWrap(const Uint1 *query, const Uint1 *subject, Int4 q_off, Int4 s_off, Int4 *private_q_start, Int4 *private_s_start, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 psi_offset, Boolean reversed, Boolean switch_seq)

Out-of-frame gapped alignment wrapper function.

ChainingStruct * ChainingStructFree(ChainingStruct *ch)

@ SCRIPT_SUB

Substitution.

@ SCRIPT_GAP_IN_A

Deletion.

@ SCRIPT_GAP_IN_B

Insertion.

@ SCRIPT_EXTEND_GAP_B

continue a gap in B

@ SCRIPT_EXTEND_GAP_A

continue a gap in A

@ SCRIPT_OP_MASK

Mask for edit script operations.

static SGreedyAlignMem * s_BlastGreedyAlignMemAlloc(const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, Int4 max_d, Int4 Xdrop)

Allocate memory for the greedy gapped alignment algorithm.

@ SCRIPT_AHEAD_ONE_FRAME

Shift 1 frame in sequence A (gap 2 nucleotides)

@ SCRIPT_NEXT_IN_FRAME

Shift to next base (substitution)

@ SCRIPT_OOF_OPEN_GAP

Opening a gap.

@ SCRIPT_AHEAD_TWO_FRAMES

Shift 2 frames in sequence A (gap 1 nucleotide)

@ SCRIPT_NEXT_PLUS_TWO_FRAMES

Shift to next base plus 2 frames (gap 2 nucleotides in sequence B)

@ SCRIPT_NEXT_PLUS_ONE_FRAME

Shift to next base plus 1 frame (gap 1 nucleotide in sequence B)

Int2 BLAST_GreedyGappedAlignment(const Uint1 *query, const Uint1 *subject, Int4 query_length, Int4 subject_length, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 q_off, Int4 s_off, Boolean compressed_subject, Boolean do_traceback, Boolean *fence_hit)

Greedy gapped alignment, with or without traceback.

void AdjustSubjectRange(Int4 *subject_offset_ptr, Int4 *subject_length_ptr, Int4 query_offset, Int4 query_length, Int4 *start_shift)

Adjusts range of subject sequence to be passed for gapped extension, taking into account the length a...

static Int2 s_BlastDynProgNtGappedAlignment(BLAST_SequenceBlk *query_blk, BLAST_SequenceBlk *subject_blk, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, BlastInitHSP *init_hsp)

Performs dynamic programming style gapped extension, given an initial HSP (offset pair),...

static Int2 s_ChainingAlignment(BlastQueryInfo *query_info, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, const BlastHitSavingParameters *hit_params, const BlastInitialWordParameters *word_params, BlastInitHitList *init_hitlist)

Approximate gapped alignment score by chaining co-linear ungapped alignments.

static void s_AdjustHspOffsetsAndGetQueryData(const BLAST_SequenceBlk *query, const BlastQueryInfo *query_info, BlastInitHSP *init_hsp, BLAST_SequenceBlk *query_out, Int4 *context)

Find the HSP offsets relative to the individual query sequence instead of the concatenated sequence a...

void BlastGetStartForGappedAlignmentNucl(const Uint1 *query, const Uint1 *subject, BlastHSP *hsp)

Function to look for the longest identity match run (up to size HSP_MAX_IDENT_RUN) in an HSP and retu...

static GapStateArrayStruct * s_GapGetState(GapStateArrayStruct **head, Int4 length)

Retrieve the state structure corresponding to a given length.

#define MAX_TOTAL_GAPS

Approximate upper bound on a number of gaps in an HSP, needed to determine the length of the subject ...

Int2 BLAST_GapAlignStructNew(const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, Uint4 max_subject_length, BlastScoreBlk *sbp, BlastGapAlignStruct **gap_align_ptr)

Initializes the BlastGapAlignStruct structure.

static void s_RebuildEditScript(GapEditScript *esp)

static Int4 s_OutOfFrameAlignWithTraceback(const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed)

Low level function to perform gapped extension with out-of-frame gapping with traceback.

BlastGapAlignStruct * BLAST_GapAlignStructFree(BlastGapAlignStruct *gap_align)

Deallocates memory in the BlastGapAlignStruct structure.

static Int4 s_RestrictedGappedAlign(const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reverse_sequence)

Low level function to perform score-only gapped extension in one direction.

ChainingStruct * ChainingStructNew(void)

Structures and functions prototypes used for BLAST gapped extension.

#define MAX_DBSEQ_LEN

Split subject sequences if longer than this.

Private interface for blast_gapalign.c.

#define HSP_MAX_WINDOW

Window size used to scan HSP for highest score region, where gapped extension starts.

Int2 Blast_HSPInit(Int4 query_start, Int4 query_end, Int4 subject_start, Int4 subject_end, Int4 query_gapped_start, Int4 subject_gapped_start, Int4 query_context, Int2 query_frame, Int2 subject_frame, Int4 score, GapEditScript **gap_edit, BlastHSP **ret_hsp)

Allocates BlastHSP and inits with information from input.

Int4 BlastHspNumMax(Boolean gapped_calculation, const BlastHitSavingOptions *options)

Calculated the number of HSPs that should be saved.

BlastHSPList * Blast_HSPListNew(Int4 hsp_max)

Creates HSP list structure with a default size HSP array.

BlastHSP * Blast_HSPFree(BlastHSP *hsp)

Deallocate memory for an HSP structure.

Int2 Blast_HSPListSaveHSP(BlastHSPList *hsp_list, BlastHSP *hsp)

Saves HSP information into a BlastHSPList structure.

BlastHSPList * Blast_HSPListFree(BlastHSPList *hsp_list)

Deallocate memory for an HSP list structure as well as all it's components.

void Blast_HSPListSortByScore(BlastHSPList *hsp_list)

Sort the HSPs in an HSP list by score.

Utilities for dealing with BLAST HSPs in the core of BLAST.

Boolean BlastIntervalTreeContainsHSP(const BlastIntervalTree *tree, const BlastHSP *hsp, const BlastQueryInfo *query_info, Int4 min_diag_separation)

Determine whether an interval tree contains an HSP that envelops an input HSP.

void Blast_IntervalTreeReset(BlastIntervalTree *tree)

Empty an interval tree structure but do not free it.

BlastIntervalTree * Blast_IntervalTreeInit(Int4 q_start, Int4 q_end, Int4 s_start, Int4 s_end)

Initialize an interval tree structure.

Int2 BlastIntervalTreeAddHSP(BlastHSP *hsp, BlastIntervalTree *tree, const BlastQueryInfo *query_info, EITreeIndexMethod index_method)

Add an HSP to an existing interval tree.

BlastIntervalTree * Blast_IntervalTreeFree(BlastIntervalTree *tree)

Deallocate an interval tree structure.

Interface for an interval tree, used for fast HSP containment tests.

@ eQueryAndSubject

Index by query and then by subject offset.

#define BLASTERR_MEMORY

System error: out of memory condition.

@ eJumperWithTraceback

Jumper extension (mapping)

@ eDynProgScoreOnly

standard affine gapping

@ eGreedyScoreOnly

Greedy extension (megaBlast)

Boolean Blast_ProgramIsRpsBlast(EBlastProgramType p)

Returns true if program is RPS-BLAST (i.e.

EBlastProgramType

Defines the engine's notion of the different applications of the BLAST algorithm.

Boolean Blast_SubjectIsTranslated(EBlastProgramType p)

Returns true if the subject is translated.

Int4 Blast_GetQueryIndexFromQueryOffset(Int4 query_offset, EBlastProgramType program, const BlastQueryInfo *query_info)

Return the query index (zero based), given the query offset in the initial HSP as the program.

Int4 Blast_GetQueryIndexFromContext(Int4 context, EBlastProgramType program)

Given a context from BLAST engine core, return the query index.

Int4 BSearchContextInfo(Int4 n, const BlastQueryInfo *A)

Search BlastContextInfo structures for the specified offset.

Various auxiliary BLAST utility functions.

Int4 BLAST_FrameToContext(Int2 frame, EBlastProgramType program)

Convert translation frame or strand into a context number suitable for indexing into the BlastQueryIn...

#define FENCE_SENTRY

This sentry value is used as a 'fence' around the valid portions of partially decoded sequences.

#define NCBI2NA_UNPACK_BASE(x, N)

Macro to extract base N from a byte x (N >= 0, N < 4)

static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)

void GapPrelimEditBlockAdd(GapPrelimEditBlock *edit_block, EGapAlignOpType op_type, Int4 num_ops)

Add a new operation to a preliminary edit block, possibly combining it with the last operation if the...

GapPrelimEditBlock * GapPrelimEditBlockFree(GapPrelimEditBlock *edit_block)

Frees a preliminary edit block structure.

GapStateArrayStruct * GapStateFree(GapStateArrayStruct *state_struct)

Free the gap state structure.

EGapAlignOpType

Operation types within the edit script.

@ eGapAlignIns

Insertion: a gap in subject.

@ eGapAlignSub

Substitution.

@ eGapAlignDel

Deletion: a gap in query.

GapEditScript * GapEditScriptNew(Int4 size)

Initialize the edit script structure.

GapEditScript * GapEditScriptDelete(GapEditScript *esp)

Free edit script structure.

GapPrelimEditBlock * GapPrelimEditBlockNew(void)

Allocates a preliminary edit block structure.

void GapPrelimEditBlockReset(GapPrelimEditBlock *edit_block)

Reset a preliminary edit block without freeing it.

Prototypes and structures for greedy gapped alignment.

struct SGreedyOffset SGreedyOffset

Bookkeeping structure for greedy alignment.

void MBSpaceFree(SMBSpace *sp)

Free the space structure.

Int4 BLAST_AffineGreedyAlign(const Uint1 *seq1, Int4 len1, const Uint1 *seq2, Int4 len2, Boolean reverse, Int4 xdrop_threshold, Int4 match_cost, Int4 mismatch_cost, Int4 in_gap_open, Int4 in_gap_extend, Int4 *seq1_align_len, Int4 *seq2_align_len, SGreedyAlignMem *aux_data, GapPrelimEditBlock *edit_block, Uint1 rem, Boolean *fence_hit, SGreedySeed *seed)

Perform the greedy extension algorithm with affine gap penalties.

SMBSpace * MBSpaceNew(int num_space_arrays)

Allocate a space structure for greedy alignment At least num_space_arrays will be allocated,...

#define GREEDY_MAX_COST_FRACTION

sequence_length / (this number) is a measure of how hard the alignment code will work to find the opt...

#define GREEDY_MAX_COST

The largest distance to be examined for an optimal alignment.

uint8_t Uint1

1-byte (8-bit) unsigned integer

int16_t Int2

2-byte (16-bit) signed integer

int32_t Int4

4-byte (32-bit) signed integer

uint32_t Uint4

4-byte (32-bit) unsigned integer

int8_t Int1

1-byte (8-bit) signed integer

JumperGapAlign * JumperGapAlignNew(Int4 size)

JumperGapAlign * JumperGapAlignFree(JumperGapAlign *jgap_align)

if(yy_accept[yy_current_state])

const struct ncbi::grid::netcache::search::fields::SIZE size

int strcmp(const char *str1, const char *str2)

Prototypes for portable math library (ported from C Toolkit)

Int4 BLAST_Gdb3(Int4 *a, Int4 *b, Int4 *c)

Divide 3 numbers by their greatest common divisor.

#define MIN(a, b)

returns smaller of a and b.

#define NCBI_INLINE

"inline" seems to work on our remaining in-house compilers (WorkShop, Compaq, ICC,...

Uint1 Boolean

bool replacment for C

#define TRUE

bool replacment for C indicating true.

#define FALSE

bool replacment for C indicating false.

#define ASSERT

macro for assert.

#define INT4_MIN

Smallest (most negative) number represented by signed int.

#define MAX(a, b)

returns larger of a and b.

static int match(PCRE2_SPTR start_eptr, PCRE2_SPTR start_ecode, uint16_t top_bracket, PCRE2_SIZE frame_size, pcre2_match_data *match_data, match_block *mb)

static PCRE2_SIZE * offsets

Structure to hold a sequence.

Int4 length

Length of sequence.

Int2 frame

Frame of the query, needed for translated searches.

Uint1 * sequence

Sequence used for search (could be translation).

Uint1 * oof_sequence

Mixed-frame protein representation of a nucleotide sequence for out-of-frame alignment.

The context related information.

Int4 query_length

Length of this query, strand or frame.

Int4 query_offset

Offset of this query, strand or frame in the concatenated super-query.

Int1 frame

Frame number (-1, -2, -3, 0, 1, 2, or 3)

Int4 max_mismatches

Maximum number of mismatches allowed for Jumper.

Boolean chaining

Use chaining for fast approximate gapped extension.

Int4 mismatch_window

Widnow for counting mismatches for Jumper.

EBlastPrelimGapExt ePrelimGapExt

type of preliminary gapped extension (normally) for calculating score.

Computed values used as parameters for gapped alignments.

BlastExtensionOptions * options

The original (unparsed) options.

Int4 gap_x_dropoff_final

X-dropoff value for the final gapped extension (raw)

Int4 gap_x_dropoff

X-dropoff value for gapped extension (raw)

Structure supporting the gapped alignment.

GapPrelimEditBlock * fwd_prelim_tback

traceback from right extensions

Int4 gap_x_dropoff

X-dropoff parameter to use.

GapPrelimEditBlock * rev_prelim_tback

traceback from left extensions

Boolean positionBased

Is this PSI-BLAST?

Int4 query_stop

query end offseet of current alignment

ChainingStruct * chaining

data for chaining

Int4 dp_mem_alloc

current number of structures allocated

Int4 subject_start

subject start offset current alignment

Int4 greedy_subject_seed_start

for greedy alignments, the subject offset of the gapped start point

BlastScoreBlk * sbp

Pointer to the scoring information block.

SGreedyAlignMem * greedy_align_mem

Preallocated memory for the greedy gapped extension.

GapStateArrayStruct * state_struct

Structure to keep extension state information.

Int4 query_start

query start offset of current alignment

Int4 subject_stop

subject end offset of current alignment

Int4 max_mismatches

Max number of mismatches for jumper.

Int4 greedy_query_seed_start

for greedy alignments, the query offset of the gapped start point

Int4 mismatch_window

Window sie for mismatches for jumper.

BlastGapDP * dp_mem

scratch structures for dynamic programming

JumperGapAlign * jumper

data for jumper alignment

Int4 score

Return value: alignment score.

GapEditScript * edit_script

The traceback (gap) information.

Auxiliary structure for dynamic programming gapped extension.

Int4 best_gap

score of best path that ends in a gap at this position

Int4 best

score of best path that ends in a match at this position

Int4 cutoff_score

Raw cutoff score corresponding to the e-value provided by the user if no sum stats,...

Structure containing hit counts from the gapped stage of a BLAST search.

Int4 extensions

Total number of gapped extensions performed.

The structure to hold all HSPs for a given sequence after the gapped alignment.

Int4 hspcnt

Number of HSPs saved.

BlastHSP ** hsp_array

Array of pointers to individual HSPs.

Structure holding all information about an HSP.

BlastSeg query

Query sequence info.

Int4 context

Context number of query.

BlastSeg subject

Subject sequence info.

Int4 score

This HSP's raw score.

Options used when evaluating and saving hits These include: a.

Int4 min_diag_separation

How many diagonals separate a hit from a substantial alignment before it's not blocked out.

Parameter block that contains a pointer to BlastHitSavingOptions and the values derived from it.

BlastGappedCutoffs * cutoffs

per-context gapped cutoff information

Boolean restricted_align

TRUE if approximate score-only gapped alignment is used.

Int4 * low_score

lowest ungapped score that can trigger a gapped alignment if the histlist is already full.

BlastHitSavingOptions * options

The original (unparsed) options.

A node in a path through blast unagpped alignments.

struct BlastInitHSPNode * next

Next node in the path.

BlastInitHSP * init_hsp

Ungapped alignment.

int best_score

Best score for paths that start at this node.

Structure to hold the initial HSP information.

BlastUngappedData * ungapped_data

Pointer to a structure holding ungapped alignment information.

BlastOffsetPair offsets

Offsets in query and subject, or, in PHI BLAST, start and end of pattern in subject.

Structure to hold all initial HSPs for a given subject sequence.

Int4 total

Total number of hits currently saved.

BlastInitHSP * init_hsp_array

Array of offset pairs, possibly with scores.

Parameter block that contains a pointer to BlastInitialWordOptions and the values derived from it.

BlastUngappedCutoffs * cutoffs

cutoff values (one per context)

Main structure describing an interval tree.

The query related information.

Int4 first_context

Index of the first element of the context array.

BlastContextInfo * contexts

Information per context.

int num_queries

Number of query sequences.

Int4 last_context

Index of the last element of the context array.

Structure used for scoring calculations.

SPsiBlastScoreMatrix * psi_matrix

PSSM and associated data.

SBlastScoreMatrix * matrix

scoring matrix data

Scoring options block Used to produce the BlastScoreBlk structure This structure may be needed for lo...

char * matrix

Name of the matrix containing all scores: needed for finding neighboring words.

Boolean is_ooframe

Should out-of-frame gapping be used in a translated search?

Scoring parameters block Contains scoring-related information that is actually used for the blast sea...

Int4 gap_extend

Penalty for each gap residue (scaled version)

Int2 penalty

Penalty for a mismatch.

Int4 shift_pen

Penalty for shifting a frame in out-of-frame gapping (scaled version)

Int4 gap_open

Extra penalty for starting a gap (scaled version)

BlastScoringOptions * options

User-provided values for these params.

Int2 reward

Reward for a match.

Int4 gapped_start

Where the gapped extension started.

Int2 frame

Translation frame.

Int4 offset

Start of hsp.

Int4 cutoff_score

Cutoff score for saving ungapped hits.

Structure to hold ungapped alignment information.

Int4 score

Score of the ungapped alignment.

Int4 length

Length of the ungapped alignment.

Int4 q_start

Start of the ungapped alignment in query.

Int4 s_start

Start of the ungapped alignment in subject.

Workspace used for chaining.

Edit script: linked list of correspondencies between two sequences.

Int4 * num

Array of number of operations.

Int4 size

Size of above arrays.

EGapAlignOpType * op_type

Array of type of operation.

Preliminary version of GapEditBlock, used directly by the low- level dynamic programming routines.

GapPrelimEditScript * edit_ops

array of edit operations

Int4 num_ops

number of edit ops presently in use

A version of GapEditScript used to store initial results from the gapped alignment routines.

Int4 num

Number of operations.

EGapAlignOpType op_type

Type of operation.

Structure to keep memory for state structure.

struct GapStateArrayStruct * next

Next link in the list.

Int4 used

how much of length is used.

Int4 length

length of the state_array.

Uint1 * state_array

array to be used.

int ** data

actual scoring matrix data, stored in row-major form

All auxiliary memory needed for the greedy extension algorithm.

SGreedyOffset ** last_seq2_off_affine

Like last_seq2_off but for affine searches.

Int4 * max_score

array of maximum scores

SMBSpace * space

local memory pool for SGreedyOffset structs

Int4 max_dist

max distance to search

Int4 * diag_bounds

bounds on ranges of diagonals

Int4 ** last_seq2_off

2-D array of distances

Bookkeeping structure for greedy alignment.

Structure for locating high-scoring seeds for greedy alignment.

Int4 start_q

query offset of start of run of matches

Int4 match_length

length of run of matches

Int4 start_s

subject offset of start of run of matches

SBlastScoreMatrix * pssm

position-specific score matrix

Uint4 q_off

Query offset.

Uint4 s_off

Subject offset.

struct BlastOffsetPair::@6 qs_offsets

Query/subject offset pair.

static CS_CONTEXT * context

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