By lliu | Fri, 04/23/2021 - 15:38

Suppose $a$ and $b$ are two nucleotides at a site of the alignment, the similarity score between $a$ and $b$ is defined as follows,

$$\begin{align} S(a,b)=\begin{cases} 1, &a=b \\ -1, &a \ne b \\ 0, &gap\end{cases} \end{align}$$

Given an alignment, the similarity score of the alignment is equal to the sum of the similarity scores across sites of the alignment, i.e.

$$\begin{equation}S=\sum_{i=1}^nS(a_i,b_i)\end{equation}$$

Next, we introduce three popular algorithms to find the alignment with the maximum similarity score.