De Levenshteinafstand tussen twee DNA sequenties is de minimale hoeveelheid bewerkingen die nodig zijn om de ene sequentie om te zetten in de andere. Deze afstandsmaat is genoemd naar Vladimir Levenshtein, die hem in 1965 uitvond. Naast zijn toepassing in de spellingscontrole, wordt de Levenshteinafstand ook gebruikt om schattingen te maken van de evolutionaire afstand tussen twee DNA sequenties (waarbij dan meestal gebruik wordt gemaakt van de varianten van Needleman-Wunsch of Smith-Waterman). Hierbij kan een DNA sequentie worden voorgesteld door een tekenreeks die enkel bestaat uit de lettertekens A, C, G en T. De verzameling geldige bewerkingen is dan insertie (letter invoegen), deletie (letter verwijderen) en substitutie (letter veranderen door een andere letter).
Voor de berekening van de Levenshteinafstand
tussen twee gegeven DNA sequenties wordt gebruikgemaakt van een
tweedimensionale matrix $$d(0,\ldots,m;0,\ldots,n)$$, waarbij $$m$$ de lengte
van de eerste DNA sequentie voorstelt en $$n$$ de lengte van de tweede DNA
sequentie. Initieel vul je de eerste kolom van de matrix $$d$$ met de
getallen $$0,1,\ldots,m$$ en de eerste rij met de getallen $$0,1,\ldots,n$$.
De andere getallen worden van links naar rechts en van boven naar onder
berekend, waarbij de waarde op rij $$i$$ en kolom $$j$$ wordt gegeven door
\[
d_{i,j} = \textrm{minimum}
\left\{
\begin{array}{ll}
d_{i-1,j}+1&\textrm{deletie}\\
d_{i,j-1}+1&\textrm{insertie}\\
d_{i-1,j-1}+\textrm{kost}\quad\quad&\textrm{substitutie}\\
\end{array}
\right.
\]
Hierbij is de kost gelijk aan 0 als de $$i$$-de letter van de eerste DNA
sequentie gelijk is aan de $$j$$-de letter van de tweede DNA sequentie.
Anders is de kost gelijk aan 1. Op het einde van deze procedure kan de
Levenshteinafstand worden uitgelezen als de waarde rechtsonderaan in de
matrix.
Een voorbeeld, de Levenshteinafstand tussen ACTCA en AGTCCG is 3 en kan als volgt weergegeven worden:
ACTCA $$\longrightarrow$$ AGTCA (eerste C vervangen door G)
AGTCA $$\longrightarrow$$ AGTCC (A achteraan vervangen door C)
AGTCC $$\longrightarrow$$ AGTCCG (achteraan G toevoegen)
Het eindresultaat na berekening van de tweedimensionale matrix $$d$$ ziet er dan als volgt uit:
Opgave
Definieer een klasse Sequentie waarmee instanties van geldige DNA sequenties kunnen aangemaakt worden. De objecten van de klasse Sequentie moeten ondersteuning bieden aan de volgende methoden:
De initialisatiemethode __init__ laat toe om DNA sequentieobjecten aan te maken op basis van een gegeven string (die als argument wordt meegegeven). Dergelijke objecten hebben een attribuut seq dat verwijst naar een string die enkel bestaat uit de letters A, C, G en T. De meegeleverde string moet door de methode __init__ omgezet worden naar hoofdletters, en de geldigheid ervan moet gecontroleerd worden door in de initialisatiemethode de methode valideer aan te roepen. Bestudeer onderstaand voorbeeld om te achterhalen wat er moet gebeuren indien de doorgegeven string geen geldige DNA sequentie voorstelt.
De methode valideer geeft de waarde True terug indien de waarde van het attribuut seq enkel bestaat uit de letters A, C, G en T. Anders wordt de waarde False teruggegeven. Aan deze methode moeten geen argumenten doorgegeven worden.
De methode afstand geeft de Levenshteinafstand terug tussen het huidige Sequentie object en een ander Sequentie object dat als argument aan de methode moet doorgegeven worden.
Voorbeeld
>>> seq1 = Sequentie('ACTCA')
>>> seq2 = Sequentie('AGTCCG')
>>> seq1.afstand(seq2)
3
>>> seq3 = Sequentie('GTCNAAC')
Traceback (most recent call last):
AssertionError: ongeldige sequentie