Séquence génomique

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 couteuse, 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)
Par exemple pour transformer AGTATCT en AGATGC, avec a=2 et b=1 on peut opérer ainsi :
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 autremenent !

A G T A T C T
A G . A T G C
Cette fois, nous avons réalisé une seule suppression (lettre T, cout 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=6 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=6 et b=5, la distance entre ATGCGTAGCG et AATGCGTGCAA est 23.

Ce problème est tiré de c0d1ng UP 2014

Type de retour

Un nombre entier

Entrée du problème

('ATTTCAAGTATTTCCCCATAAAACCTTAGCGCAGCGTACACACGCAATTATGTAATTCTCGGATGTAGGATGGCAACTGGATCTGCATACATCCCGGCGCAAATACCAAGAT', 'GGAACCATTGGTCATAGCACTAAGACCTATTCTCTCTCTTGGCTGTGCAAAGTCGTGTCAGGCTTTCGTGGAGCTAGAGCTCTATATAGCCCGGTGCTTCGTACGCCATAAACTTTAC')

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup14 combinatoire récursivité