CSC277 - Project 3
Protein Alignment

Algorithm

Write a program to calculate the best global alignment between two sequences.

pwalign <sequence1> <sequence2> <score-matrix> <gap-penalty>

Your input sequences will be in FASTA format, and your scoring matricies will be either PAM250 or BLOSUM62.

Helpful Data Structures

The internal structure of your program could be organized in the following way:

score-matrix
A 2-D matrix to keep the scores for the individual amino acid match scores.
amino-acids
A list of the amino acids as organized in the score matrix.
sequence1
The first sequence read by the program, stored as a string.
sequence2
The second sequence read by the program, stored as a string.
gap
The gap penalty.
align-scores
The 2-D matrix of alignment scores, used for the dynammic programming.
align-arrows
The 2-D matrix of arrows to track the direction of the winning score.

These can be used by the following methods:

main
Read in the sequences and scoring matrix, then compute the alignment.
readMatrix
Load the text file into the 2-D score-matrix.
readSequence
Load the FASTA file into the sequence string
align
Progressively compute the alignment scores using the maximum of previously aligned pieces, and store the direction of this maximum alignment score. Once completed, walk from the sink to the source and calculate the resulting alignment.

Output

The output of your program should be the resulting alignment, in a format similar to the output seen at the EMBOSS Align website. In general the markup line uses a space for a mismatch or a gap, '.' for any small positive score, ':' for a similarity which scores more than 1.0, and '|' for an identity where both sequences have the same residue regardless of its score.

GFP_AEQVI          1     MSKGEELFTGVVPILVELDGDVNGHKFSVSGEGEGDATYGKLTLKF     46
                         :.|       .:|....::|.||||.|..:|:|||:...|...:|.
NFCP_ANESU         1 MASFLKK-------TMPFKTTIEGTVNGHYFKCTGKGEGNPFEGTQEMKI     43

GFP_AEQVI         47 -ICTTGKLPVPWPTLVTTFSYGVQCFSRYPDHMKQHDFFKSAMPEGYVQE     95
                      :...|.||..:..|.|:..||.:.|.:|...:.  |:||.:.|||:..|
NFCP_ANESU        44 EVIEGGPLPFAFHILSTSCMYGSKTFIKYVSGIP--DYFKQSFPEGFTWE     91

GFP_AEQVI         96 RTIFFKDDGNYKTRAEVKFEGDTLVNRIELKGIDFKEDGNILGHK-----    140
                     ||..::|.|......:...:||.||.::::.|.:|..||.::.:|     
NFCP_ANESU        92 RTTTYEDGGFLTAHQDTSLDGDCLVYKVKILGNNFPADGPVMQNKAGRWE    141

GFP_AEQVI        141 --LEYNYNSHNVY----IMADKQKNGIKVNFKIRHNIEDGSVQLADHYQQ    184
                       .|..|....|.    :||.|...|       ||.    :..|...|:.
NFCP_ANESU       142 PATEIVYEVDGVLRGQSLMALKCPGG-------RHL----TCHLHTTYRS    180

GFP_AEQVI        185 NTPIGDGPVLLPDNHYLSTQSALSKDPNEKRDHMVLLEFVTAAGITHGMD    234
                     ..|.  ..:.:|..|:              .||.:.:           |:
NFCP_ANESU       181 KKPA--SALKMPGFHF--------------EDHRIEI-----------ME    203

GFP_AEQVI        235 ELYK                             238
                     |:.|                         
NFCP_ANESU       204 EVEKGKCYKQYEAAVGRYCDAAPSKLGHN    232

Extra Credit

Implement the extensions we discussed in class, local alignment to find the best sub-match, and affine gap penalties.

Testing

Test you above algorithm on the two sequences found in the P42212.fasta and Q9GZ28.fasta files provided.