Description
Many problems in bioinformatics amount to approximate string matching. For example, whenever a new gene is sequenced, searching known genes for close matches allows us to attempt to infer the new gene’s functions.
-
Sequence Alignment
Specifically, a gene is a string over the alphabet Σ = {A, C, G, T}, and the closeness of two genes is measured by the extent to which they are aligned. An alignment of two strings, x and y, is an arrangement of their characters in columns, in the same order as they originally appeared, potentially interspersed by spaces.
For example, given x = ACGAT and y = TACGCA, one possible alignment is:
A – – – C G A T
T A C G C – – A
Where the ‘–’ character is used to indicate a space. Note that a typical further requirement (and will be a requirement for this assignment) is that no column may contain two spaces.
Another possible alignment is:
– A C G – A T
T A C G C A –
Of these two alignments, the second appears to be “better”, but how can we quantify “better”? The score of an alignment is specified by a (|Σ| + 1) × (|Σ| + 1) scoring matrix, δ. For example, the latter of the above alignments has a score of δ(–, T) + δ(A, A) + δ(C, C) + δ(G, G) + δ(–, C) + δ(A, A) + δ(T, –).
In your programming language of choice, implement a dynamic programming algorithm to find the highest scoring alignment of two strings.
You may assume that both of the given strings will be non-empty and will contain only the characters ‘A’, ‘C’, ‘G’, or ‘T’. You may also assume that the scoring matrix will always contain exactly 5 rows and 5 columns, each in the order ‘A’, ‘C’, ‘G’, ‘T’, ‘–’, will always be symmetric about the major diagonal, and will always provide integer scores.
For example, the above strings, along with a simple scoring matrix, would be represented as:
ACGAT
TACGCA
x A C G T –
A10000
C01000
G00100
T00010
-00000
Since this scoring matrix only rewards exact matches, in this situation, the second of the above alignments, with a score of 4, would indeed be better than the first, with a score of 1 (and, in fact, is the highest scoring alignment overall).
Your program must accept as a command line argument the name of a file containing two strings and a scoring matrix as described above, then print to stdout the highest scoring alignment as follows.
-
The first given string, named x, must be printed above the second given string, named y
-
The columns of the alignment must be space-separated, and ‘–’ characters must be used to represent spaces within the aligned strings.
-
After printed the alignment, print the score.
For example:
CSC 349 Assignment 4 — Dynamic Programming Page 2 of 2
$ ./compile.sh
-
./run.sh test_files/in1.txt x: – A C G – A T
y: T A C G C A –
Score: 4
You may first assume that the highest scoring alignment will be unique. Your program will be tested using diff, as its printed output must match exactly.
-
Submission
The following items must be demonstrated/presented to me in lab on the day of the deadline.
-
Definition, base cases, formula, and solution for a dynamic programming algorithm to find the highest scoring alignment of two strings.
The following files are required and must be pushed to your GitHub Classroom repository by the deadline:
-
compile.sh — A bash script to compile your submission (even if it does nothing).
-
run.sh — A bash script to run your submission.
-
*.py or *.java — Your source code in Python or Java of a working program.
