Un des enjeux de la bio-informatique est de repérer des points communs et des différences entre des séquences d'acides aminés (représentés ici par les lettres A, G, T et C).
Pour cela, il est nécessaire de calculer la «distance» entre 2 séquences, comme AGTATCT et AGATGC. Cette distance est le coût de la transformation la moins coûteuse, qui permet de transformer la première séquence en la deuxième.
Pour transformer une séquence en une autre, on peut :
- insérer ou supprimer une lettre (coût a)
- transformer une lettre en une autre (coût b)
A G . T A T C T A G A T . G C .Pour transformer AGTATCT en AGATGC, on a donc fait un ajout (lettre A, coût 2), deux suppression (lettre A, puis T, coût 2x2) et une transformation (T en G, coût 1). Le coût total est donc : 7
Mais on peut aussi procéder autrement !
A G T A T C T A G . A T G CCette fois, nous avons réalisé une seule suppression (lettre T, coût 2), et deux transformations (C en G puis T en C, coût 2x1). Le coût total est 4.
Ces deux transformations peuvent être visualisées sur ce schéma :
Le coût de la première transformation est 7 et celui de la deuxième est 4, ce qui est le minimum entre ces deux séquences si a=2 et b=1. On dira donc, si a=2 et b=1, que la distance entre AGTATCT et AGATGC est 4.
Dans votre cas, vous utiliserez les valeurs numériques suivantes : a=8 et b=5. Vous devez calculez la distance entre les deux séquences données en entrée du problème.
À titre d'exemple, pour les valeurs a=8 et b=5, la distance entre ATGCGTAGCG et AATGCGTGCAA est 28.