Exercise 1 - Levenshtein Distance

Compute the minimal Levenshtein edit distance for the following pairs of sequences.

1a)

\[\begin{align} S_{1} = A\\ S_{2} = T \end{align}\]

Hide
Hint

A → T

Solution

A → T = 1

1b)

\[\begin{align} S_{1} &= AGATATA\\ S_{2} &= TATATATA \end{align}\]

Hide
Hint

AGATATA → ATATATA → …

Solution

AGATATA → ATATATA → TATATATA = 2

1c)

\[\begin{align} S_{1} = AGTCCT\\ S_{2} = CGCTCA \end{align}\]

Hide
Hint

AGTCCT → AGCTCA → …

Solution

AGTCCT → CGTCCT → CGCCCT → CGCTCT → CGCTCA = 4

1d)

\[\begin{align} S_{1} = TGCATAT\\ S_{2} = ATCCGAT \end{align}\]

Hide
Hint

TGCATAT → AGCATAT → …

Solution

TGCATAT → AGCATAT → ATCATAT → ATCAGAT → ATCCGAT = 4

1e)

\[\begin{align} S_{1} = ACGTATATAGCCCCGCG\\ S_{2} = ACGTTATATAGCCGCGC \end{align}\]

Hide
Hint

You need to use all the possible operations

ACGTATATAGCCCCGCG → ACGTTATATAGCCCCGCG → …

Solution

ACGTATATAGCCCCGCG → ACGTTATATAGCCCCGCG → ACGTTATATAGCCGCGCG → ACGTTATATAGCCGCGC = 3

Exercise 2 - Metric function

Check if the corresponding functions are metric.

Hide
Formulae

Note

Definition Metric:

\[\begin{align} w(x,y) &= 0 \leftrightarrow x = y\ &\text{(identity)}\\ w(x, y) &= w(y, x)\ &\text{(symmetric)}\\ w (x, z) &\leq w (x, y ) + w (y , z) &\text{(triangle inequality)} \end{align}\]

2a)

\[\begin{align} w(x,y) = x-y \end{align}\]

Hide
Hint

What if \(x = 1\) and \(y = 2\)?

Solution

Not a metric, violates symmetry constraint.

\[ x = 1\\ y = 2\\ x - y = 1 - 2 = -1 \neq 1 = 2 - 1 = y - x \]

2b)

\[\begin{align} w(x,y) = |x-y| \end{align}\]

Hide
Hint

You need to check all the properties.

Solution

Metric

2c)

\[\begin{align} w(x,y) = x+y \end{align}\]

Hide
Hint

What if \(x = 1\) and \(y = 1\)?

Solution

Not metric, violates identity constraint:

\[ x = y = 1\\ x + y = x + x = 2 \neq 0 \]

2d)

\[\begin{align} w(x,y) = \begin{cases} 1 \ \text{if}\ x \neq y \\0\ \text{else} \end{cases} \end{align}\]

Hide
Hint

You need to check all the properties.

Solution

Metric

Exercise 3 - Programming assignment

Programming assignments are available via Github Classroom and contain automatic tests.

We recommend doing these assignments since they will help you to further understand this topic.

Access the Github Classroom link: Programming Assignment: Sheet 02.