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\).
\[ 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 \[ \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\).
