<string>

Table des matières

Mission 4 - Strings et listes

Mission 4 : Strings et listes

Mission 4 : Strings et listes

Introduction

Une étudiante en biologie que vous venez de rencontrer vous demande de l'aide pour un problème de bioinformatique. Grâce aux progrès des techniques de séquençage automatiques de l'ADN, il est maintenant facile d'obtenir l'ADN d'un être vivant. L'ADN est composé de quatre types de bases : Adénine, Cytosine, Guanine et Thymine. Pour manipuler ces séquences ADN, les biologistes ont pris l'habitude de les représenter sous la forme d'une (longue) suite de caractères représentants les 4 bases qui forment l'ADN. A titre d'exemple, voici un extrait de séquence ADN provenant de la base de données GenBank:

LOCUS       SCU49845     5028 bp    DNA             PLN       21-JUN-1999
DEFINITION  Saccharomyces cerevisiae TCP1-beta gene, partial cds, and Axl2p
            (AXL2) and Rev7p (REV7) genes, complete cds.
...

ORIGIN
        1 gatcctccat atacaacggt atctccacct caggtttaga tctcaacaac ggaaccattg
       61 ccgacatgag acagttaggt atcgtcgaga gttacaagct Aaaacgagca gtagtcagct
      121 ctgcatctga agccgctgaa gttctactaa gggtggataa catcatccgt gcaagaccaa
      181 gaaccgccaa tagacaacat atgtaacata tttaggatat acctcgaaaa taataaaccg
      241 ccacactgtc attattataa ttagaaacag aacgcaaaaa ttatccacta tataattcaa
      301 agacgcgaaa aaaaaagaac aacgcgtcat agaacttttg gcaattcgcg tcacaaataa
...
     4861 ttctccactt cactgtcgag ttgctcgttt ttagcggaca aagatttaat ctcgttttct
     4921 ttttcagtgt tagattgctc taattctttg agctgttctc tcagctcctc atatttttct
     4981 tgccatgact cagattctaa ttttaagcta ttcaatttct ctttgatc

Une séquence d'ADN d'un gène peut être très longue. A titre d'exemple, on estime que l'ADN humain contient de l'ordre de 3 × 109 bases découpées en environ 20.000 gènes. L'ADN d'une bactérie contient de l'ordre de 4 millions de bases. Les biologistes ont séquencé l'ADN d'un grand nombre d'espèces qu'ils stockent dans des bases de données spécialisées comme GenBank. Le traitement de toutes ces données a mené à la création de la bio-informatique, discipline qui rassemble des biologistes et des informaticiens.

Afin d'aider cette étudiante en biologie, vous allez écrire durant cette mission vos premiers algorithmes de bio-informatique.

Objectifs

Objectifs individuels

A l'issue de ce problème, chacun d'entre vous :

  • sera en mesure d'être de plus en plus précis sur certains concepts sous-jacents à un programme Python simple (après une quatrième prise de connaissance) :
    • chaînes de caractères
    • listes
    • fonctions qu'on peut appliquer sur chaînes et listes
    • création de listes imbriquées
  • aura montré une capacité à écrire des méthodes permettant de manipuler des chaînes de caractères et des listes.

Préparation, étude et apprentissage

La matière relative à cette mission est décrite dans les sections suivantes du syllabus :

Il est cependant important que vous puissiez facilement vous y retrouver dans la documentation de Python pour y trouver les renseignements dont vous avez besoin pour écrire des programmes efficaces. Pour des fonctions qui peuvent être exécutées sur des chaînes de caractères, regardez ici.

Questionnaire de démarrage

Questions à choix multiple

Les questions à choix multiples de cette mission sont également accessibles en ligne depuis https://inginious.info.ucl.ac.be/course/LSINF1101-PYTHON/Session4_QCM


        
        

Question 1

Vous voulez dire bonjour à l'utilisateur de votre programme. Le nom de l'utilisateur est enregistré dans une variable appelée name et vous voulez enregistrer vos salutations dans une variable nommée hello. Cette chaine de caractères aura la forme suivante : "Hello, name!"

Par exemple, si "Charles" est assigné à name, votre code écrirait "Hello, Charles!" dans la variable hello.


        
        

Question 2

Dans le programme ci-dessous, quelle ligne faut-il écrire pour afficher la longueur de la chaîne de caractères s ?

s = "Informatique1"

Question 3

Dans le programme ci-dessous, quelle ligne faut-il écrire pour afficher la chaîne en majuscules ?

s = "Informatique1"
.

Question 4

Etant donnée une chaîne de caractères stockée dans un variable l, par exemple, l = "louvain-la-neuve" ou l = "braine-le-compte", comment feriez-vous pour :

  • Afficher le premier caractère de l
 
 

  • Afficher le premier caractère de l en majuscule
 
 

  • Afficher toute la chaîne sauf le premier caractère
 
 

  • Afficher la chaîne avec le premier caractère en majuscule (sur les exemples, "Louvain-la-neuve" et "Braine-le-compte")
 
 

  • Afficher une liste des positions des traits d'union (sur les exemples, [7,10], [6,9])
 
 
 
 

  • Afficher le mot avant le premier trait d'union. (Sur les exemples, "Louvain", "Braine")
 
 
 
 

Question 4

La fonction max_index(lst) doit retourner l'index de l'élément avec la plus grande valeur dans une liste. La valeur None doit être retournée quand la liste est vide. Définissez cette fonction.


        
        

 
 
 
 

Question 5

Écrivez une fonction triangle(n) qui pour un nombre entier donné n, retourne la liste de listes imbriquées

[ [ 0 ],
  [ 0, 1 ],
  [ 0, 1, 2 ],
  ...,
  [ 0, 1, 2, ..., n ] ]


        
        

Question 6

Écrivez une fonction carre(n) qui pour un nombre entier donné n, retourne la matrice

[ [         0,             1, ...,     n - 1 ],
  [         n,         n + 1, ..., 2 * n - 1 ],
  [     2 * n,     2 * n + 1, ..., 3 * n - 1 ],
  ...,
  [ (n-1) * n, (n-1) * n + 1, ..., n * n - 1 ] ]

Par exemple, pour n=4, la fonction retourne

[ [  0,  1,  2,  3 ],
  [  4,  5,  6,  7 ],
  [  8,  9, 10, 11 ],
  [ 12, 13, 14, 15 ] ]


        
        

Question 7

Écrivez une fonction recherche ( m, v ) qui pour un nombre entier donné v, retourne True si ce nombre apparaît dans la matrice, et False si non. Par exemple, pour la matrice suivante et la valeur v=4, le résultat doit être False. Pour la valeur v=3 le résultat doit être True.

[ [  0,  3,  2,  8 ],
  [  6,  5,  2,  1 ],
  [  7,  0,  3,  2 ] ]


        
        

Question 8

Écrivez une fonction ajoute ( l, v ) qui pour une liste donnée l, ajoute le nombre v à la fin de la liste, si ce nombre n'est pas encore présent dans la liste. Si le nombre apparaît déjà, la liste doit rester non modifiée. Pour ce code:

l = [ 3, 1, 5, 4 ]
ajoute ( l, 4 )
ajoute ( l, 6 )
ajoute ( l, 7 )
ajoute ( l, 6 )
print ( l )

Le programme doit imprimer [ 3, 1, 5, 4, 6, 7 ]. La fonction ajoute ne retourne rien.


        
        

Question 9

Les nombres premiers (https://en.wikipedia.org/wiki/Prime_number) sont des nombres avec les caractéristiques suivantes:

  • ce sont des nombres plus grands que 1
  • ils n'ont pas des diviseurs autres que 1 et eux-mêmes.

Des nombres premiers sont 2, 3, 5, 7, 11, 13, ...

Pour calculer les nombres premiers on peut utiliser le crible d'Eratosthène : pour chaque nombre successif, on vérifie si on peut le diviser par un des nombres premiers déjà trouvés. Si non, on peut ajouter le nombre à la liste. Ecrivez la fonction primes(max) qui retourne une liste de tous les nombres premiers jusque max (max inclus si max est un nombre premier). Si max est négatif ou zéro, la liste vide doit être retournée.

Pour limiter la complexité de la solution, decomposez votre solution en sous-problèmes comme nécessaire; utilisez des boucles for.


        
        

Mission 4

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, ...

Remise de votre solution

Pour cette mission, vous devez soumettre votre fichiers bioinfo.py au serveur de soumissions de programmes du cours. Votre fichier bioinfo.py doit au moins contenir les fonctions :

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

        
        
Questions complémentaires

Questions complémentaires

La méthode sum(list) retourne la somme des éléments contenus dans list.

Exemple: la somme de [1,2,3] est 6

Notez que votre algorithme devrait être capable de calculer la somme même si la liste list contient des éléments malicieux (pas des nombres).


        
        

La méthode average(list) retourne la moyenne arithmétique des éléments contenu dans list, sauf si list est vide auquel cas, elle devrait retourner None.


        
        

La méthode diff_count(lst) retourne le nombre d'éléments différents contenus dans la liste lst.

Par exemple:

  • Si lst est égal à [3, 5, 3] alors la méthode devrait retourner 2.
  • Si tous les éléments sont les mêmes, la méthode devrait retourner 1.
  • Si la liste lst est vide, elle devrait retourner 0.


        
        

Les équations du second degré sont des équations de la forme suivante:

$$ax^2 + bx + c = 0$$

avec a ≠ 0

Pour déterminer si l'équation dispose d'une solution, on calcule le nombre ρ = b2 − 4ac. Si ρ est strictement positif, l'équation a exactement deux solutions. La première solution s'obtient via la formule suivante :

( − b + (ρ))/(2a)

Et la seconde racine s'obtient via la formule suivante :

( − b − (ρ))/(2a)

Si ρ est nul, l'équation a exactement une solution, dont la valeur est égale à  − b ⁄ (2a). Si ρ est négatif, l'équation n'a aucune solution.

Un étudiant vous demande de l'aider à résoudre des équations à tour de bras. Vous disposez de la fonction suivante, qui est une variante de la fonction implémentée dans un exercice complémentaire de la Session 3:

def solution(a, b, c):
"""
pre:  a, b et c sont 3 nombres réels
post: la valeur de retour de cette fonction dépend du nombre
      de solutions de l'équation ax^2 + bx + c = 0.
- 0 solution: retourne la liste vide
- 1 solution: retourne une liste contenant la solution de l'équation
- 2 solutions: retourne une liste contenant les deux solutions,
              la plus petite solution en première place
"""

Écrivez la signature et le corps de la fonction solveur, dont le but est de résoudre une liste d'équations du second degré. Une équation est représentée par la liste [a, b, c]. La fonction solveur doit retourner une liste. L'élément à l'indice i de la valeur de retour contient le résultat de la fonction solution appliquée sur l'équation située à l'indice i de l'input.

Pour réussir cette exercice, vous devez utiliser une list comprehension.

Voici un exemple de la valeur de retour de la fonction solveur :

>>> solveur([])
[]

>>> solveur([[1, 1, -1], [4, 4, 1], [1, 2, 3], [-1, 2, 3]])
[[-1.618033988749895, 0.6180339887498949], [-0.5], [], [-1.0, 3.0]]


        
        

Une fois de plus, la Grosse Dame a bu tout le vin de la peinture des moines ivres et le Chevalier du Catogan n'est pas disponible pour la remplacer. L'accès à la salle commune des Gryffondor n'est pas gardée et les intentions des Serpentards sont mauvaises.

Nous avons besoin que vous conceviez un vérificateur de mot de passe pour combler le vide laisser par le départ de la Grosse Dame.

Créez une fonction portrait(right_password, entered_password) qui retourne True si les deux mots de passe sont identiques et False sinon.


        
        

Anonymous vient de vous engager sur le dark web pour une tâche dangereuse. Ils essayent de craquer un code depuis quelques jours mais ne sont arrivés à rien... pour le moment!

Ils veulent que vous construisiez une fonction qui analysera chaque caractère dans un code donné et que vous déterminiez sa nature. Le but est simple : ils ont l'intention d'utiliser les informations que vous leur fournirez pour trouver un pattern dans le code.

Créez une fonction extract(code) pour fournir des infos concernant la nature de chaque élément du code :

Par exemple, si le code 'AeB7' est donné en entrée, la fonction devrait produire 'vowel-up vowel-low consonant-up number' comme sortie. En général :

  • Ajoutez un number à la réponse si l'élément du code est un chiffre.
  • Ajoutez un vowel à la réponse si l'élément du code est une voyelle.
  • Ajoutez un consonant à la réponse si l'élément du code est une consonne.
  • Suivez cela par -up si la voyelle/consonne est en majuscule.
  • Suivez cela par -low si la voyelle/consonne est en minuscule.

Exemple :

Avec le code '65AeBc7' la fonction devrait sortir 'number number vowel-upvowel-low consonant-up consonant-up number'.


        
        

Etant donné que votre travail était remarquable, Anonymous vous a à nouveau contacté avec une autre tâches risquée. Ils manquent de main d'oeuvre et aimeraient que traitiez les données que vous leur avez donné.

Ils veulent que vous construisiez une fonction qui transformera votre précédente sortie en quelque chose de plus simple et plus rapide à traiter. C'est à vous de voir comment transformer l'information en un pattern utilisable!

Créez une fonction treatment(data) pour transformer l'information que vous avez précédemment retourné en un pattern :

Chaque suite d'éléments communs devrait être indiqué par la nature de l'élément suivi de '*' et le nombre d’occurrence sans autre éléments entre.

Exemple:

Avec le code '66AeB7' votre précédente fonction sortirait 'number number vowel-up vowel-low consonant-up number'.

Avec cette sortie en entrée votre nouvelle fonction treatment sortirait la string suivante 'number*2 vowel-up*1 vowel-low*1 consonant-up*1 number*1'.

N'hésitez pas à utiliser autant de sous-méthodes que vous jugez nécessaires.