Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
Macros | Functions | Variables
SWpar_ref.c File Reference
#include "SWcommon.h"
#include "SWcommon_ref.h"
#include <mpi.h>
Include dependency graph for SWpar_ref.c:

Go to the source code of this file.

Macros

#define BEGIN(coord, dims, size)   (coord * size / dims)
 
#define END(coord, dims, size)   ((( coord + 1 ) * size / dims)-1)
 
#define SIZE(coord, dims, size)   (END(coord,dims,size)-BEGIN(coord,dims,size)+1)
 
#define h(i, j)   (H[((i)*(lsize[1]+1))+(j)])
 
#define xback(i, j)   (xTraceback[((i)*(lsize[1]+1))+(j)])
 
#define yback(i, j)   (yTraceback[((i)*(lsize[1]+1))+(j)])
 
#define T_LOCAL   0
 
#define T_MIN   1
 
#define T_AVG   2
 
#define T_MAX   3
 
#define T_READ   0
 
#define T_HMAT   1
 
#define T_BACK   2
 
#define T_DIST   3
 
#define T_SYNH   4
 
#define T_SYNB   5
 
#define T_COMP   6
 
#define allTimers(timer)   timers[T_MIN][timer],timers[T_AVG][timer],timers[T_MAX][timer]
 
#define MIN(a, b)   (((a)<(b))?(a):(b))
 
#define MAX(a, b)   (((a)>(b))?(a):(b))
 

Functions

void distributeProtein (aa_t *protein, aa_t *lprotein, int dim)
 
void recv_Back (int dir, int *pos)
 
void send_Back (int dir, int pos)
 
void composeOutput (aa_t *out, int *outpos, int *outsize, aa_t *lout, int loutsize, int *gBegin, int *gEnd)
 
void phase_read_sequences ()
 
void phase_distribute_sequences ()
 
void phase_recv_hmatrix ()
 
void phase_comp_hmatrix ()
 
void phase_send_hmatrix ()
 
void phase_recv_back ()
 
void phase_comp_back ()
 
void phase_send_back ()
 
void phase_compose_sequence ()
 
void debug_show_matrices ()
 
void debug_show_backtracking ()
 
int main (int argc, char *argv[])
 

Variables

int rank
 
int nProcs
 
int lsize [2]
 
int dims [2] = {0,0}
 
int lcoords [2]
 
int lbegin [2]
 
MPI_Comm comm
 
MPI_Op opHMaxLoc
 
aa_tp1
 
aa_tp2
 
aa_tout1
 
aa_tout2
 
int xMax
 
int yMax
 
int xBegin
 
int yBegin
 
int match_length
 
int match_length1
 
int match_length2
 
int match_pos
 
aa_tlp1
 
aa_tlp2
 
aa_tlout1
 
aa_tlout2
 
h_tH
 
trace_txTraceback
 
trace_tyTraceback
 
h_t lMax
 
int lxMax
 
int lyMax
 
int lxBegin
 
int lyBegin
 
int lmatch_length
 
int lmatch_length1
 
int lmatch_length2
 
int lmatch_pos
 

Detailed Description

Parallel version for the Smith-Waterman algorihtm. The Smith–Waterman algorithm performs local sequence alignment of protein sequences.

This version assumes a linear gap penalty. This algorithm creates the matrix H as follows:

              | H(i-1,j-1) + PAM(a_i,b_j)    (diagonal)

H(i,j) = MAX of | H(i-1,j) + gappenalty (up) | H(i,j-1) + gappenalty (left) | 0

The PAM matrix is the amino acid substitution matrix that encode the expected evolutionary change at the amino acid level.

To obtain the optimum local alignment, we start with the highest value in the matrix (i,j). Then, we go backwards to one of positions (i − 1,j), (i, j − 1), and (i − 1, j − 1) depending on the direction of movement used to construct the matrix.

Author
Javier Fresno
Date
Jun 2013

Definition in file SWpar_ref.c.

Macro Definition Documentation

#define allTimers (   timer)    timers[T_MIN][timer],timers[T_AVG][timer],timers[T_MAX][timer]
#define BEGIN (   coord,
  dims,
  size 
)    (coord * size / dims)

Macro to get the protein (or H matrix) Begin index of the current processor.

Definition at line 72 of file SWpar_ref.c.

#define END (   coord,
  dims,
  size 
)    ((( coord + 1 ) * size / dims)-1)

Macro to get the protein (or H matrix) End index of the current processor.

Definition at line 77 of file SWpar_ref.c.

#define h (   i,
 
)    (H[((i)*(lsize[1]+1))+(j)])

Definition at line 243 of file SWpar_ref.c.

#define MAX (   a,
 
)    (((a)>(b))?(a):(b))

Definition at line 1224 of file SWpar_ref.c.

#define MIN (   a,
 
)    (((a)<(b))?(a):(b))

Definition at line 1223 of file SWpar_ref.c.

#define SIZE (   coord,
  dims,
  size 
)    (END(coord,dims,size)-BEGIN(coord,dims,size)+1)

Macro to get the local protein (or H matrix) size of the current processor.

Definition at line 82 of file SWpar_ref.c.

#define T_AVG   2
#define T_BACK   2
#define T_COMP   6
#define T_DIST   3
#define T_HMAT   1
#define T_LOCAL   0
#define T_MAX   3
#define T_MIN   1
#define T_READ   0
#define T_SYNB   5
#define T_SYNH   4
#define xback (   i,
 
)    (xTraceback[((i)*(lsize[1]+1))+(j)])

Definition at line 248 of file SWpar_ref.c.

#define yback (   i,
 
)    (yTraceback[((i)*(lsize[1]+1))+(j)])

Definition at line 249 of file SWpar_ref.c.

Function Documentation

void composeOutput ( aa_t out,
int *  outpos,
int *  outsize,
aa_t lout,
int  loutsize,
int *  gBegin,
int *  gEnd 
)

Function to compose the final output in the root processor.

Definition at line 1228 of file SWpar_ref.c.

void debug_show_backtracking ( )

Debug to show the backtracking info

void debug_show_matrices ( )

Debug function to show the H and backtraking matrices

void distributeProtein ( aa_t protein,
aa_t lprotein,
int  dim 
)

Function that distributes the protein from the root processor to the remain procs.

Definition at line 1116 of file SWpar_ref.c.

int main ( int  argc,
char *  argv[] 
)

Main function.

< Time init start

< Time init end

< Time computation start

< Time computation end

< Aux start timer for phases

< Aux end timer for phases

< Accumulate time in read

< Accumulate time in H matrix computation

< Accumulate time in backtracking

< Accumulate time in protein sequence distribution

< Accumulate time in H matrix sync

< Accumulate time in backtracking sync

< Accumulate time in final protein composition

Definition at line 275 of file SWpar_ref.c.

Here is the call graph for this function:

void phase_comp_back ( )

Compute the traceback

void phase_comp_hmatrix ( )

Calculate the similarity matrix (H)

void phase_compose_sequence ( )

Compose the final sequence

void phase_distribute_sequences ( )

Distribute the protein sequences

void phase_read_sequences ( )

Read the protein sequences

void phase_recv_back ( )

Receive the traceback neighbor values

void phase_recv_hmatrix ( )

Receive the similarity matrix (H) values from the neighbors.

void phase_send_back ( )

Receive the traceback values to the appropriate neighbor

void phase_send_hmatrix ( )

Send the similarity matrix (H) values to the neighbors.

void recv_Back ( int  dir,
int *  pos 
)

Function to receive the result from the sucessors at the backtracking stage. They will pass the coordinate of the next point of the path or -1 if the alignement do not cross through our portion of H.

void send_Back ( int  dir,
int  pos 
)

Function to inform the predecessor processors if they have to rebuild the path using the backtracking algorithm.

Variable Documentation

MPI_Comm comm

Communicator

Definition at line 193 of file SWpar_ref.c.

int dims[2] = {0,0}

Partition dimensions.

Definition at line 187 of file SWpar_ref.c.

h_t* H

Definition at line 242 of file SWpar_ref.c.

int lbegin[2]

Begin index for the current processor

Definition at line 191 of file SWpar_ref.c.

int lcoords[2]

x and y coordinates of the processor in the topology.

Definition at line 189 of file SWpar_ref.c.

int lmatch_length

Definition at line 263 of file SWpar_ref.c.

int lmatch_length1

Definition at line 264 of file SWpar_ref.c.

int lmatch_length2

Definition at line 265 of file SWpar_ref.c.

int lmatch_pos

Definition at line 268 of file SWpar_ref.c.

h_t lMax

Definition at line 252 of file SWpar_ref.c.

aa_t* lout1

Definition at line 238 of file SWpar_ref.c.

aa_t* lout2

Definition at line 239 of file SWpar_ref.c.

aa_t* lp1

Definition at line 234 of file SWpar_ref.c.

aa_t* lp2

Definition at line 235 of file SWpar_ref.c.

int lsize[2]

Size of the local part of the proteins.

Definition at line 185 of file SWpar_ref.c.

int lxBegin

Definition at line 259 of file SWpar_ref.c.

int lxMax

Definition at line 255 of file SWpar_ref.c.

int lyBegin

Definition at line 260 of file SWpar_ref.c.

int lyMax

Definition at line 256 of file SWpar_ref.c.

int match_length

Definition at line 221 of file SWpar_ref.c.

int match_length1

Definition at line 222 of file SWpar_ref.c.

int match_length2

Definition at line 223 of file SWpar_ref.c.

int match_pos

Definition at line 226 of file SWpar_ref.c.

int nProcs

Number of processors in the communicator.

Definition at line 183 of file SWpar_ref.c.

MPI_Op opHMaxLoc

MPI reduce function for double_3int

Definition at line 196 of file SWpar_ref.c.

aa_t* out1

Definition at line 209 of file SWpar_ref.c.

aa_t* out2

Definition at line 210 of file SWpar_ref.c.

aa_t* p1

Definition at line 205 of file SWpar_ref.c.

aa_t* p2

Definition at line 206 of file SWpar_ref.c.

int rank

MPI Rank of the current processor.

Definition at line 181 of file SWpar_ref.c.

int xBegin

Definition at line 217 of file SWpar_ref.c.

int xMax

Definition at line 213 of file SWpar_ref.c.

trace_t* xTraceback

Definition at line 246 of file SWpar_ref.c.

int yBegin

Definition at line 218 of file SWpar_ref.c.

int yMax

Definition at line 214 of file SWpar_ref.c.

trace_t* yTraceback

Definition at line 247 of file SWpar_ref.c.