Question
Une chaîne d’ADN peut être représentée comme une chaîne de caractères contenant uniquement les caractères A,T,G,C.
Exercice 1
On peut aussi représenter une chaîne d’ADN par un nombre en considérant que chaque lettre représente un chiffre et que le nombre représentant la chaîne d’ADN est écrit en base 4. Par exemple en admettant que A représente le chiffre 0, T, le chiffre 1, G, le chiffre 2 et C le chiffre 3, la chaîne d’ADN ATG serait représentée par le nombre :
|
Par quel nombre serait représentée la chaîne GTG ? la chaîne TAA ?
Réponse :
GTG → 2 × 16 + 1 × 4 + 2 × 1 = 38
TAA → 1 × 16 + 0 × 4 + 0 × 1 = 16
Exercice 2
Si une chaîne d’ADN a une longueur de 2 nucléotides (deux lettres), quelle est la chaîne représentée par le nombre 15 ? par le nombre 0 ?
Réponse :
15 = 3 × 4 + 3 × 1 = CC
00 = 0 × 4 + 0 × 1 = AA
Exercice 3
Quelle est le plus grand nombre qui représente une chaîne d’ADN de longueur 10 ? Quelle chaîne représente-t-il?
Réponse :
Dans notre système à base 4, le « chiffre » qui a la plus grande valeur est C, qui vaut 4−1=3. Le plus grand nombre représenté par dix chiffres en base 4 sera constitué de dix « chiffres » C, et vaudra :
(4−1) × 49 + (4−1) × 48 + ... + (4−1) × 42 + (4−1) × 41 + (4−1) × 40
soit en développant :
410 − 49 + 49 − 48 + 48 − ... + 43 − 42 + 42 − 41 + 41 −1
et grâce à ces combinaisons d’additions et de soustractions :
CCCCCCCCCC → 410−1 = 1048575
Exercice 4
Le nombre représentant une chaîne d’ADN dépend de l’association que nous définissons entre les lettres A,T,G et C et les chiffre 0, 1, 2, 3. Si nous décidons d’associer T à 0, G à 1, C à 2 et A à 3, par quel nombre serait représentée la chaîne ATG ? la chaîne GTG ? Quelle serait la chaîne d’ADN représentée par le nombre 15 ?
Exercice 5
Combien y a-t-il de façon d’associer les lettres A, T, G et C chacune avec un chiffre différent pris entre 0 et 3 ?
Réponse :
S’il y a 4 choix possibles pour A, il en reste 3 pour T, 2 pour G et 1 pour C : donc 4!=24 solutions possibles, qui sont appelées les permutations de l’ensemble { A,T,G,C } (cf. http://fr.wikipedia.org/wiki/Permutation).
Exercice 6
Une chaîne de protéine est une chaîne d’acides aminés, elle peut être représentée comme une chaîne de caractères ne contenant que les caractères suivants : A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y. En effet il y a 20 acides aminés. On peut représenter une chaîne de protéine par un nombre en considérant que chacun des caractères pouvant apparaître dans une chaîne de protéine est associé à un nombre pris entre 0 et 19. Le calcul pour une protéine se fera donc en base 20.
On peut prendre comme correspondance entre acide aminé et chiffre la correspondance suivante par exemple :
A: 0; C: 1; D: 2; E: 3; F: 4; G: 5; H: 6; I: 7; K: 8; L: 9; M:10; N:11; P:12; Q:13; R:14; S:15; T:16; V:17; W:18; Y:19;
Dans ce cas quelle est la valeur du nombre représentant le tripeptide CAY ?
Réponse :
CAY → 1 × 202 + 0 × 201 + 19 × 200
soit : 1 × 400 + 0 × 20 + 19 × 1 = 419
Exercice 7
Quel est le plus grand nombre représentant un tripeptide (une protéine formée de trois acides aminés) ? Quel est le plus grand nombre représentant une protéine de 300 acides aminés ?
Réponse :
Le raisonnement est le même qu’à la question ?? :
YYY → 203−1 = 7999
YYYYYYYYYYYYYYYYYYYY... → 20300−1
Exercice 8
Soit la fonction Scheme:
1 (define (adn->number DNA-CHAINE) 2 (let ((valeur 0)) 3 (do ((i 0 (+ i 1))) 4 ((>= i (string-length DNA-CHAINE))valeur) 5 (set! valeur 6 (+ (* valeur 4) 7 (if (char=? (string-ref DNA-CHAINE i) #\T) 8 0 9 (if (char=? (string-ref DNA-CHAINE i) #\G) 10 1 11 (if (char=? (string-ref DNA-CHAINE i) #\C) 12 2 3)))))))) |
Cette fonction rend la valeur d’un nombre associé à une chaîne d’ADN. Quelle correspondance a-t-on choisi entre les nucléotides (lettres) de la chaîne d’ADN et les chiffres 0,1,2,3 ?
Réponse :
T → 0
G → 1
C → 2
A → 3
Exercice 9
Donner le pseudocode de l’algorithme décrit par la fonction adn->number.
Réponse :
1 Algo : ADN->number 2 Entrée : A une séquence d'ADN representée par une 3 chaîne de caractères 4 Résultat : la valeur numérique qui représente la séquence 5 valeur <- 0 6 L <- longueur de A 7 pour i allant de 0 a L-1 faire 8 si A[i] = T alors valeur <- 4*valeur + 0 9 sinon si A[i] = G alors valeur <- 4*valeur + 1 10 sinon si A[i] = C alors valeur <- 4*valeur + 2 11 sinon si A[i] = A alors valeur <- 4*valeur + 3 12 finsi 13 fait 14 retourner valeur |
Exercice 10
On peut se demander si deux chaînes sont identiques de la façon suivante : ont-elle la même longueur et dans ce cas sont-elles représentées par le même nombre ? Ecrire la fonction Scheme qui réalise une comparaison de deux chaînes d’ADN sur ce principe.
Réponse :
1 (define (adn=? seq1 seq2) 2 (and (= (string-length seq1) (string-length seq1)) 3 (= (adn->number seq1) (adn->number seq2)))) |
Question
Nous nous proposons de trier des listes selon un algorithme de tri par fusion de listes déjà triées. Nous allons dans un premier temps attaquer le problème de la fusion.
Exercice 1
Si nous avons deux ensembles de valeurs triées, rangées dans deux listes, pour construire la liste triée de l’union de ces deux ensembles de valeurs :
- si la première liste est vide : la solution est la seconde liste ;
- si la seconde liste est vide : la solution est la première liste ;
- si aucune des deux listes n’est vide, nous prendrons la plus petite des têtes des deux listes, que nous placerons en tête de la liste solution, dont la suite sera construite par la fusion du reste de la liste dont nous avons déjà gardé la tête avec l’autre liste.
En Scheme :
1 (define (fusion L1 L2) 2 (if (null? L1) L2 3 (if (null? L2) L1 4 (if (< (car L1) (car L2)) 5 (cons (car L1) 6 (fusion (cdr L1) L2)) 7 (cons (car L2) 8 (fusion L1 (cdr L2))))))) |
Il vous est demandé d’écrire le pseudo-code de cet algorithme de fusion.
Exercice 2
Ainsi on voit que pour trier une liste il suffit de la séparer en deux sous listes, de trier chacune de ces listes et de les fusionner. Sauf si la liste est vide au départ, dans ce cas elle est déjà triée !
Séparer une liste en deux sous-listes et appliquer une fonction de tri à chacun de ces sous-listes et enfin appliquer une fonction de fusion à ces deux sous-listes peut s’écrire :
1 (define (separe-et-applique L f g L1 L2) 2 (if (null? L) 3 (g (f L1) (f L2)) 4 (separe-et-applique 5 (cdr L) f g L2 (cons (car L) L1)))) |
Il vous est demandé d’écrire le pseudo-code de cet algorithme « séparer et appliquer ».
Exercice 3
Finalement, pour trier une liste avec ces programmes il faut faire :
1 Algo : tri-fusion 2 Donnée : une liste L 3 Résultat : L est triée 4 si L est la liste vide ou (cdr L) est la liste vide 5 alors retourner L 6 sinon 7 separer-et-appliquer(L, tri-fusion, fusion, '(), '()) |
Il vous est demandé d’écrire le programme Scheme qui correspond à cet algorithme.
1 (define (tri-fusion L) 2 (if (or (null? L) (null? (cdr L))) 3 L 4 (separe-et-applique 5 L tri-fusion fusion '() '()))) |
Ce document a été traduit de LATEX par HEVEA