Mission 4

Les séquences d'ADN sont composées d'un suite de caractères A, T, C et G. Pour traiter de telles séquences en Python, le plus simple est de les manipuler comme des chaînes de caractères.

Votre objectif durant cette mission est de développer quelques fonctions permettant de traiter des séquences d'ADN stockées sous la forme de chaînes de caractères.

1. Chargez le fichier exemples.py dans la tâche sur INGInious (plus bas). Ecrivez toutes les fonctions demandées durant cette mission dans ce fichier. Vous trouverez dans ce fichier plusieurs chaînes de caractères représentants des séquences ADN que vous pouvez réutiliser pour tester vos fonctions.

2. La première fonction à écrire est la fonction is_adn(s). Elle prend comme argument une chaîne de caractères s et retourne True si la chaîne de caractères contient uniquement les caractères a, t, c ou g (à la fois en majuscules et en minuscules) et False sinon. Une chaîne de caractères vide ("") n'est pas considérée comme étant de l'ADN.

3. La deuxième fonction à écrire est la fonction positions(s, p). Elle prend comme arguments deux chaînes de caractères s et p. Elle retourne les positions des occurences de p dans s. Par exemple, pour ACGACCG (majuscules) et cg (minuscule) le résultat doit être [1,5]. Vous ne pouvez pas utiliser la fonction find de Python.

4. La troisième fonction à écrire est baptisée distance_h. Elle calcule la distance de Hamming (http://fr.wikipedia.org/wiki/Distance_de_Hamming) entre deux chaînes de caractères de longueurs égales. En théorie de l'information, cette distance est définie comme étant le nombre de positions où les deux chaînes de caractères diffèrent. Voici quelques exemples qui devraient vous aider à mieux comprendre cette distance :

   Chaîne 1	Chaîne 2	Distance
   A	A	0
   AG	GG	1
   AG	AT	1
   ATGAC	ATGAC	0
   ATGAC	AGGAG	2
   ATGAC	TGACG	5

   Si les chaînes n'ont pas la même longueur, la fonction doit retourner None.

5. La quatrième fonction à écrire est distances_matrice(l). Étant donné une liste de chaînes de caractères, la fonction doit calculer une matrice des distances de Hamming entre toutes ces chaînes de caractères. Par exemple, pour cette liste: ["AG", "AT", "GT", "ACG", "ACT" ] la fonction doit retourner:

   [ [     0,   1,    2, None, None ],
     [     1,   0,    1, None, None ],
     [     2,   1,    0, None, None ],
     [ None, None, None, 0,    1    ],
     [ None, None, None, 1,    0    ] ]
   

   Utilisez la fonction que vous avez écrit dans l'exercice précédente.

6. Dans les séquences d'ADN, on retrouve parfois des palindromes. Un palindrome est un mot dont l'ordre des caractères reste le même qu'on le lise de gauche à droite ou de droite à gauche, comme "radar" ou "kayak". Une séquence ADN telle que CTAGGATC est un exemple de palindrome. A titre d'exemple, le plus long palindrome de la séquence ACCTGTTAGGATTC est TTAGGATT. Certains palindromes ont un rôle particulier d'un point de vue biologique et il est intéressant de pouvoir trouver dans une séquence donnée le plus long palindrome.

   Votre dernier objectif dans cette mission est d'écrire la fonction plus_long_palindrome qui prend comme argument une chaîne de caractères et retourne une chaîne de caractères contenant le plus long palindrome de la chaîne passée en argument. Dans cette phase de réalisation, nous considérons qu'un caractère unique est lui-même un palindrome. Lorsque la fonction ne trouve aucun palindrome dans une chaîne de caractères, elle devra retourner "".

   En Python, il existe une construction pour extended slices, qui n'a pas été discuté pendant le cours et qui n'est pas discuté dans le syllabus. Il n'est pas permis d'utiliser cette construction.

   Détecter le plus long palindrome dans une chaîne de caractères est un problème compliqué. En informatique, lorsque l'on est face à un problème compliqué, la meilleure approche pour le résoudre est de le découper en petits problèmes plus simples. Il suffit ensuite d'écrire une fonction pour résoudre chaque petit problème et de combiner ces fonctions pour résoudre le problème compliqué.

   Pour rechercher le plus long palindrome, une piste est de d'abord écrire une fonction permettant d'extraire d'une chaîne de caractères de longueur n les sous-chaînes de longueur n-1, n-2, ...

is_adn(text)
positions(text,car)
distance_h(text1,text2)
distances_matrice(l)
plus_long_palindrome(text)

Please log in to see this exercise