<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

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

  • Afficher la longueur de la chaîne de caractères l
 
 

  • Afficher la chaîne l en majuscules
 
 

  • 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")
 
 

Question 3

La fonction maximum_index(lst) doit retourner l'index de l'élément avec la plus grande valeur dans une liste non vide. Par exemple: maximum_index([0,2,5,3]) doit retourner 2, puisque 5 est la plus grande valeur et apparaît en position 2. Définissez cette fonction.


        
        

Question 4

Nous voulons écrire une fonction positions(s,p) qui pour une chaîne de caractères s et un caractère p retourne la liste des positions où le caractère p apparaît dans s. Par exemple, pour positions("gtagaac","a") le résultat doit être [2,4,5].

  • Décrivez en mots la structure d'un programme Python qui peut résoudre ce problème.
 
 
 
 
 

  • Écrivez du code Python pour ce problème.
 
 
 
 
 

  • Écrivez une spécification de la fonction suivante:
def q(c1,c2):
  return c1.upper () == c2.upper ()
 
 
 
  • On veut modifier la fonction positions(c,p) de telle façon que la fonction ignore si un caractère est en majuscule ou en minuscule. Par exemple, dans ce cas positions("gtagaAc","A") donne aussi [2,4,5] comme résultat, puisque le cas n'est pas important. Modifiez la fonction positions(c,p), en utilisant la fonction q de la question précédente.
 
 
 
 
 

Question 5

É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 6

  • Étudiez la fonction ci-dessous et écrivez une spécification pour la fonction, en utilisant des conditions pré and post!
def mysterieux(n):
  l = []
  for i in range(n):
    l2 = []
    for j in range(n):
      l2.append ( n )
    l.append ( l2 )
  return l
 
 
 
 
 

  • Écrivez une fonction carre(n).

Pour un nombre entier donné n, la fonction doit retourner 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 ] ]


        
        

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.

Toutes les fonctions doivent être écrites dans un fichier avec le nom bioinfo.py. Vérifiez pour chaque fonction que la fonction est correcte en utilisant des exemples!

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

    De bons exemples à utiliser pour les tests sont ici: "acgac", "AcaA", aAaza, "".

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

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

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

Remise de votre solution

Pour cette mission, vous devez soumettre votre fichier 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)

        
        
Questions complémentaires

Questions complémentaires

É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 ] ]


        
        

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.


        
        

Nombres premiers

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.