We also after playing this game have

constructed something that is called alignment of two strings.

Alignment of two strings is a two row matrix such that,

that first row consist of symbols of the first string in order,

possibly interspaced with the space symbol.

And the second row consists of the symbols of the second string once again,

possibly interspersed with the space symbol.

After we constructed the alignment, we can classify

different columns in the alignment matrix as matches or

mismatches or insertions.

Insertions corresponds to the case when we selected the symbol

from the second string and

deletions that correspond to the case when we selected the symbol from the first string.

And more over we can score this alignment by giving premium for

every match, we'll give premium plus one and penalty for every mismatch and

every insertion and deletion that we denote as indel.

In our case we will use penalty minus mu for mismatches and

penalty minus sigma for insertions and deletions or indels.

For example in our case if mu equals zero and

sigma equal to one, then we get alignment score equal to one.

So we define the alignment score as number of matches minus mu

number of mismatches and minus sigma number of indels.

And the optimal alignment problem is given two strings mismatch penalty mu,

and indel penalty sigma find an alignment of two strings maximizing the score.

We will be particularly interested in one particular score of alignment.

We will define common subsequence

as simply matches in an alignment of two strands.

In this case, common subsequence is represented by ATGT,

and the longest common subsequence problems that we will be

interested in is the following.

Given two strings we want to find

the longest common subsequence of these strings.