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 \mathbb{Z}$. We have a gap penalties functions $g_s,g_t:\mathbb{N}\to \mathbb{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$.