Formal Definition of Sequence Alignment
Consider an alphabet \Sigma and two sequences s and t on \Sigma. Let \bar{\Sigma} = \Sigma\cup \{\diamond\} where \diamond is some symbol not in \Sigma, it's called the gap symbol. M:\bar{\Sigma}\times \bar{\Sigma}\to \Z. We have a gap penalties functions g_s,g_t:\N\to \Z. The functions are monotonic and are 0 at 0. The four boundary gap penalty coefficient b_s,b_t,e_s,e_t\in \{0,1\}. We want to find the alignment score between the two sequences.
A gap is the maximal substring consist of only \diamond's. The gap sequence of a string is a sequence of lengths of each gap. Define s_\diamond be the gap sequence of string s.
G(x,g,y,a) = xg(a_1) + \sum_{i=2}^{n-1} g(a_i) + yg(a_n), where a is a sequence of length n.
\displaystyle A(u,v) = \sum_{i=1}^{|u|} M(u_i,v_i) + G(b_s,g_s,e_s,u_\diamond) + G(b_t,g_t,e_t,v_\diamond)
Define S and T be the set of all strings that can be formed by inserting \diamond into s and t respectively.
The alignment score is defined as \displaystyle \max \{A(u,v) : |u|=|v|, u\in S, v\in T\}
Now, once one write an algorithm for this problem, it can be used for many sequence alignment problems on Rosalind.
- Hamming Distance: M(a,a)=-1, and 0 otherwise. All other function are -\infty.
- Finding a Shared Spliced Motif, longest common subsequence. M(a,a)=1 for a\in \Sigma, 0 otherwise. Everything else are 0.
- Edit distance: Levenshtein distance, M(a,a)=-1 for a\in \bar{\Sigma}, 0 otherwise. All other are -\infty.
- Global alignment: b_s=e_s=g_s, b_t=e_t=g_t.
- Overlap alignment: b_s=e_t=0, b_t=g_t, e_s=g_s.
- Fitting alignment: b_s=e_s=0, b_t=e_t=g_t.
- Semiglobal alignment: b_s=e_s=b_t=e_t=0.
- Substring Matching: b_s=e_s=0, g_s,g_t,b_t,e_t=-\infty.