Introduction à la bioinformatique
feuille Exercices de TD
Exercice - 1 Biologie moléculaire
1- Définissez ce qu’est un génome.
2- Expliquer les différences entre les molécules d’ADN et d’ARN.
3- Expliquer le processus de réplication de l’ADN.
4- Expliquer le processus de transcription de l’ADN.
5- Expliquer le mécanisme de production des protéines.
6- Quels sont les différents types d’ARN ? Expliquer leurs rôles.
7- Sur un brin d’une molécule d’ADN, la séquence des nucléotides est CCGTAC. Quelle est la séquence
des nucléotides qui s’associent à ce brin lors de la réplication ? Lors de la transcription ?
Exercice - 2 Les gènes et leurs fonctions
1- Qu’est-ce que l’annotation de gènes ?
2- Quelles sont les différences entre les gènes procaryotes et eucaryotes ?
3- Quels sont les problèmes rencontrés par les outils d’annotation de gènes dans les génomes
procaryotes ? Dans les génomes eucaryotes ?
4- Voici un fragment d’ADN contenant le début de la séquence codante d’un gène :
AATGAAACGCATTAGCACC...
TTACTTTGCGTAAGCGTGG...
a- Identifiez le début de la phase codante du gène.
b- Ecrivez la séquence nucléotidique du fragment d’ARNm codant pour le début de la protéine.
c- Déduisez-en la séquence de la protéine correspondante. Utilisez le code génétique en annexe.
d- On a isolé une protéine mutante dans laquelle la première sérine est remplacée par une
arginine.
Quelles mutations nucléotidiques pourraient expliquer ce changement d’acide aminé ?
e- Dans une pathologie, on trouve une forme écourtée de la protéine : seuls les trois premiers
acides aminés sont présents. Quelle mutation nucléotidique a eu lieu ?
5- Calculer le modèle de “background” (composition en nucléotides) pour la séquence d’ADN
acctgcactg
6- Etant donné un dictionnaire contenant la probabilité d’apparition de chaque codon, par exemple :
codons = {TTT : 0.001, TTC :0.002, . . . } et une séquence de codons sous forme de liste S=(TTT,
TCA, TGA, . . . ), donnez le code python qui calcule la probabilité p de S étant donné le modèle de
codons (p = P (S = c0 c1 . . . cN | codons)
7- Les promoteurs sont des séquences d’ADN, généralement en amont du début du gène et res-
ponsable de sa régulation. Il y a habituellement des variations dans la composition de la séquence
du site promoteur (en général des substitutions).
Des expériences biologiques ont permis de déterminer les séquences de promoteurs suivantes :
acgact
acgtga
agcccc
1
feuille Exercices de TD 3I019 2017-2018
acgtca
tcgtct
acgtca
acgtca
accgca
tggtca
acctct
a- Calculez la matrice des fréquences de nucléotides par position Fij (i : indice de nucléotide,
j : indice de position). Rajoutez des pseudo-comptages.
F
b- Calculez la matrice de score par position, wij = log2 ( piji ), où pi est la probabilité du
nucléotide i avec le modèle de background.
8- Supposons qu’une bactérie est atteinte par un virus qui affecte la machinerie de la réplication
aléatoirement en changeant la manière dont chaque nucléotide est recopié :
chaque A peut être répliqué comme 3 A, chaque C peut être répliqué comme 4 C, chaque G peut être
répliqué comme 4 G, et chaque T peut être répliqué comme 3 T.
a- Donnez un algorithme (python ou pseudo-code) qui, pour deux séquences u et v détermine
si u peut être une version infectée de v.
b- Donnez un algorithme (python ou pseudo-code) qui étant donné une séquence S de la bac-
térie et un dictionnaire donnant la probabilité de réplication de chaque nucléotides, produira
aléatoirement une séquence infectée.
Par exemple, si S=ACCTG et P={‘A’:0.2,‘C’: 0.5,‘G’: 0.3,‘T’: 0.1}, la première lettre
(un A) a 20% de chance d’être répliqué comme 3 A, la seconde (un C), 50% de chances de
devenir 4 C, etc.
c- Le virus a muté, et en plus de rajouter des copies multiples d’une position pendant la répli-
cation, il est également possible que le nucléotide ne soit pas recopié, provoquant une délétion.
Modifiez l’algorithme de question “a” pour prendre en compte ce nouveau phénomène. On
dira par exemple que chaque nucléotide a 2% de chances de ne pas être recopié.
Exercice - 3 Alignement par paire
1- Aligner globalement les deux séquences suivantes : U=ACGCCAT et V=GCCCTA, en appliquant le
système de scores suivant : Match=2, Mismatch=-1, GAP=-3. A partir de la matrice construite,
en déduire le score de l’alignement global optimal, extraire un alignement optimal, et calculer le
nombre d’alignements qui ont ce score optimal.
2- On a partiellement rempli la matrice de programmation dynamique correspondant à un algo-
rithme d’alignement de séquences d’ADN ; la voici :
a- Quel type d’alignement 2 à 2 est-on en train de réaliser ?
b- Pour remplir cette matrice, quel coût a été utilisé pour les « Gaps » ? pour les « Match » ?
pour les « Mismatch » (le coût des « Mismatch » est indépendant du couple de nucléotides
considérés) ?
c- Terminez le remplissage de la grille.
d- Proposez un alignement optimal possible.
UPMC - Licence d’informatique 2
feuille Exercices de TD 3I019 2017-2018
3- L’algorithme d’alignement global des deux séquences CACGT et AGT donne la table de program-
mation dynamique suivante :
a- Pour remplir cette matrice, quel coût a été utilisé pour les « Gaps » ? pour les « Match » ?
pour les « Mismatch » (le coût des « Mismatch » est indépendant du couple de nucléotides
considérés) ?
b- Proposez un alignement optimal possible.
4- Voici l’alignement obtenu pour deux séquences :
CGTTAACG---ACTGTCT
CG-TATCGGCCACTATCT
Calculez le score de cet alignement dans les cas suivants :
a- Match= 2, Mismatch=-1, Gap=-2
b- Comme pour a), mais avec un score de gap affine (ouverture=-3, extension=-1)
c- Comme pour b) mais avec la matrice de similarité suivante :
Exercice - 4 BLAST
1- La figure 1 représente les résultats d’une recherche de similarité effectuée au moyen de l’outil
BLAST, pour identifier dans le génome humain les régions codant pour l’enzyme acylphosphatase.
a- Quelle est la longueur de la séquence requête (précisez l’unité) ?
b- Quelle modalité de BLAST a été utilisée et pourquoi ?
c- Comment interpréter les E-valeurs respectives des deux hits de la figure 1b ? Quel est le
meilleur hit ?
d- Dans quelle phase les hits sont-t-ils trouvés ?
e- Expliquer pourquoi dans le deuxième hit la valeur de positivité est supérieure à la valeur
d’identité.
UPMC - Licence d’informatique 3
feuille Exercices de TD 3I019 2017-2018
2- On considère les deux séquences d’ADN :
- seq1 : ATTCATTCATTCATTCATTCATTCATTCATTC
- seq2 : ATTGATTGATTGATTGATTGATTGATTGATTG
Quel est, à première vue, leur pourcentage d’identité ? Quand on fait un alignement avec l’algo-
rithme de BLAST (avec une taille de mot de 4), aucune similarité n’est trouvée. Pourquoi ?
3- Donner le code python ou le pseudocode pour générer la base de données de BLAST. Votre
fonction aura la signature db(sequences, w), où sequences est un dictionnaire de séquences et w
est la taille de mot.
Par exemple avec sequence = {‘s1’: ‘acgta’, ‘s2’: ‘aacgta’, ‘s3’: ‘acggta’} et w=3,
votre fonction doit alors renvoyer le dictionnaire des indices d’apparition de tout les mots de taille
3 dans les séquences s1, s2 et s3 :
{acg : [(s1,1), (s2,2), (s3,1)],
cgt : [(s1,2), (s2,3)],
gta : [(s1,3), (s2,4), (s3,4)],
aac : [(s2,1)],
cgg : [(s3,2)],
ggt : [(s3,3)]}
4- Montrez comment la séquence cgtca sera alignée par BLAST en utilisant les séquences et la
base de donnée indexée de la question précédente.
Exercice - 5 Alignements Multiples
1- Score d’un alignement multiple.
UPMC - Licence d’informatique 4
feuille Exercices de TD 3I019 2017-2018
a- Donnez le score de l’alignement multiple global ci dessous selon la méthode de la somme
des paires en considérant le système de scores suivant :
σ(x, x) = +1, σ(x, y) = −1, σ(x, −) = σ(−, x) = −2, σ(−, −) = 0
ACTATGTG
A-T--GTG
A-TT-GTG
b- Est-ce le meilleur alignement global que l’on pouvait obtenir ? Justifiez votre réponse.
2- Donnez le score de l’alignement multiple global ci dessous calculé selon la méthode de la somme
des paires en utilisant la matrice de substitution BLOSUM 62 (donnée en annexe).
NNNIV
NNNIV
NNN-V
NNCIV
NCCIV
3- Soit les alignements par paires :
VEDLIRY
VEDLRRY
PNELRRY
VEDLIRY
BNKAALIRF
VED--LIRY
AEDL-RF
VEDLIRY
Nous voudrions utiliser l’algorithme star pour obtenir l’alignement multiple :
a- Quelle est la séquence guide à utiliser ?
b- Donner l’alignement multiple obtenu par star
4- Soit un alignement multiple de séquences protéiques représenté en Python par une liste de
chaines de caractères. Par exemple :
almult = [’AHS--LKATL’,
’L-SW-AA--L’,
’AHI--LKATL’,
’LHS--FT--L’]
Dans un alignement multiple, une sous-partie de l’alignement ou “bloc”, est considérée comme
conservée si plus de 70% des séquences présentent le même acide aminé à chacune des positions du
bloc (un bloc peut être une colonne unique). Dans l’exemple précédent, la leucine (L) en dernière
position est conservée dans toutes les séquences, tandis que l’histidine (H) et la sérine (S), respec-
tivement en 2de et 3ème positions sont conservées à 75%. Il y a donc 2 blocs conservés, dont les
positions dans l’alignement sont : 2-3 et 10-10 (les gaps sont donc considérés comme un caractère).
a- Si on représente un alignement multiple par une liste nommée lseq de n chaînes de carac-
tères, donner l’algorithme (en Python ou en pseudocode) qui permet d’imprimer les positions
de début et de fin des blocs conservés dans l’alignement.
b- Quelle(s) modification(s) faut-il apporter à l’algorithme si on ne souhaite imprimer que les
positions des blocs ayant une taille minimale de k colonnes contiguës ?
c- Comment modifier l’algorithme pour imprimer les positions des blocs non pas conser-
vés, mais dont les colonnes présentent au moins m acides aminés différents (y compris gaps,
1 < m ≤ 20
5- A partir du schéma suivant expliquer les étapes des algorithmes dit d’alignement progressif.
UPMC - Licence d’informatique 5
feuille Exercices de TD 3I019 2017-2018
Exercice - 6 Recherche de motifs
1- Soit les séquences :
ACTGACCCTG
ACCCGGATTC
TCTGACCCTG
a- Donner les motifs de taille 4 possédant plus de trois occurrence. Construire la table de
hachage correspondante.
b- Est-ce que vous observez des motifs avec 1 seul mismatch ?
2- Proposer un algorithme (en python ou en pseudo-code) qui trouve d’abord les motifs de taille k
identiques à l’aide d’une table de hachage, et qui ensuite analyse la table pour grouper les motifs
en permettant jusqu’à v substitutions. Quel est la complexité de cet algorithme ?
3- Soit les séquences :
ACTGAAACTT
AACAGTGGCT
CAGTACTGAC
a- Certains motifs sont reverse complémentaires, par exemple ACAG et CTGT. Retrouver
tous les motifs de taille 4 possédant plus de trois occurrences inclut les reverse complémen-
taires.
4- Soit la séquence S="ACGTGGCATCCGCATCG"
a- Tracer son skew plot
b- Pourquoi le skew plot peut-il être utilisé pour trouver l’origine de réplication de certaines
bactéries ?
c- Parmi les plots représentés ci dessous, lequel ou lesquels peuvent aider à trouver l’origine
de réplication ? Justifiez votre réponse.
UPMC - Licence d’informatique 6
feuille Exercices de TD 3I019 2017-2018
5- Soit les séquences :
tcctttaatt
gcaggtcctg
tctccaagag
UPMC - Licence d’informatique 7
feuille Exercices de TD 3I019 2017-2018
a- Appliquez l’algorithme "Brute Force Motif Search” pour trouver le meilleur motif
b- Quelle est la complexité de l’algorithme "Brute Force Motif Search” ?
c- Si 10000 opérations de l’algorithme "Brute Force Motif Search” prennent 1 seconde, combien de
temps serait nécessaire pour analyser un génome de 5 millions de bp ?
d- Appliquez l’algorithme "Median String Search" pour trouver le meilleur motif.
e- Si 10000 opérations de l’algorithme "Median String Search” prennent 1 seconde, combien de
temps serait nécessaire pour analyser un genome de 5 millions de bp ?
f- Discuter et comparer les complexités des deux algorithmes.
Exercice - 7 Phylogénies
1- Remplissez la Table ci-dessous en indiquant, pour chaque paire de séquences, le type d’homologie
(O=Orthologie ; P=Paralogie ; I=Identité)
2- Déroulez l’algorithme UPGMA sur la matrice de distances suivante :
3- Lequel de ces deux arbres provient d’une méthode UPGMA ? Expliquez.
4- Quel est le nombre possible d’arbres enracinés avec 3 espèces ? avec 4 espèces ?
a- Montrer que, si Cn est le nombre d’arbres enracinés possible avec n espèces, on a C1 = 1
et Cn = (2n − 3)Cn−1 .
b- Déduisez en la formule générale pour Cn :
(2n − 3)!
Cn =
2n−2 (n − 2)!
UPMC - Licence d’informatique 8
feuille Exercices de TD 3I019 2017-2018
c- Supposons que l’on puisse calculer le score d’un millions d’arbres en une seconde. Combien
de temps cela prendrait-il d’évaluer le score de tous les arbres avec 10 espèces ? avec 15
espèces ?
5- Reconstruction des caractères ancestraux. Soit l’arbre suivant :
a- Reconstruisez les séquences ancestrales par parcimonie en utilisant l’algorithme de Sankoff,
avec un coût de 1 pour toutes les substitutions. b- Refaites maintenant l’algorithme en prenant
cette fois un coût de 1 pour les transitions et un coût de 2 pour les transversions (voir ci
dessous).
Annexes
Exercice - 8 Examen du 22 juin 2017, extraits
1- Quizz
UPMC - Licence d’informatique 9
feuille Exercices de TD 3I019 2017-2018
Questions Réponses
1. Le processus de fabrication des protéines dans les ribosomes transcription
en utilisant l’ARNm est appelé
dérivation de protéine
traduction
aucune de ces réponses
2. La molécule simple brin qui est transcrite d’une trame de ARNt
l’ADN (c’est-à-dire une photocopie d’une section spécifique de la
molécule d’ADN) et qui est ensuite utilisée pour la fabrication ARNm
des protéines est
ARNr
3. La molécule d’ADN est un polymère. Ses unités monomères acides nucléiques
sont des
acides aminés
nucléosides
nucléotides
4. La séquence transcrite sur le brin complémentaire de la UGCCAAGCA
séquence d’ADN TCGGAACAT est AUGUUCCGA
TGCCAAGCA
ATGTTCCGA
5. Quel est le nombre maximum de codons qui peuvent coder 2
pour un acide aminé ? 4
6
8
UPMC - Licence d’informatique 10
