TD2 Chaines de caractères et tableaux

Les Chaînes de caractère

Notre fil rouge: le code ADN en tant que Chaîne

Les informations du génomes sont stockées à l’aide d’un alphabet de 4 lettres ATCG

  1. Adenine
  2. Thymine
  3. Cytosine
  4. Guanine

TGGGAATAGTACGGGGATTCAATGGTACCAGTATAGC

Le Génome est composé de paires de ces nucléotiques (environ 3.10ˆ9). Des algorithmes de recherche de gènes sont indispensable pour exploiter l’information contenue dans notre ADN.

Pourquoi travailler avec les Chaînes (String)

Les chaines de caractères ne sont pas un type primitif, mais elles restent un type Objet très important pour le language. Elle peuvent contenir n'importe quel type de caractère:

Extrait du gène MSH2 chez l'être humain

source: https://www.ncbi.nlm.nih.gov

Homo sapiens chromosome 2, GRCh38.p14 Primary Assembly AAGCTGATTGGGTGTGGTCGCCGTGGCCGGACGCCGCTCGGGGGACGTGGGAGGGGAGGCGGGAAACAGC TTAGTGGGTGTGGGGTCGCGCATTTTCTTCAACCAGGAGGTGAGGAGGTTTCGACATGGCGGTGCAGCCG AAGGAGACGCTGCAGTTGGAGAGCGCGGCCGAGGTCGGCTTCGTGCGCTTCTTTCAGGGCATGCCGGAGA AGCCGACCACCACAGTGCGCCTTTTCGACCGGGGCGACTTCTATACGGCGCACGGCGAGGACGCGCTGCT GGCCGCCCGGGAGGTGTTCAAGACCCAGGGGGTGATCAAGTACATGGGGCCGGCAGGTGAGGGCCGGGAC GGCGCGTGCTGGGGAGGGACCCGGGGCCTTGTGGCGCGGCTCCTTTCCCGCCTCAGAGAGTGGGCGGTGA GCAGCCTCTCCAGTGCGGAGGCACGGGGGCGGAACGTTGGTGCTTGTGCGGATTCCGCCGTCCCCAGGTT CTGCTTGGCTCCGGAGGGACGCCCCCCTCAGCCCTGAAACCCGTGCCTCTCCAGCCGCCCCGGATCTGAA CTTGTGATCACGGAGTGTTTACGTCGTGCCAGGCATTTTAATGCATTGTTCTAGTTCATTTTCCAGCAGT CGCATTCCTCGCCTTGGCCCTACATGTAGCGCTCATTACAAACACGGCCAGAATCTCTTATTAACAAACA GCAGCCAGGAGTGAGATTTAAAATAGACTGGGGGTTTAGGAGACCCTTTTATGACACGTAATTCTGCTCC

Une réponse à une requète HTTP

< HTTP/2 304 < date: Wed, 04 Oct 2023 23:17:42 GMT < via: 1.1 varnish < cache-control: max-age=600 < etag: W/"6464c0c3-271e" < expires: Wed, 04 Oct 2023 23:27:00 GMT < age: 2 < x-served-by: cache-par-lfpg1960062-PAR < x-cache: HIT < x-cache-hits: 1

Un document XML

<LinkedHashMap><price>39.0</price><productType>LUXURY</productType></LinkedHashMap>

Objectifs de cette phase du cours

Dans cette phase, nous allons tâcher de comprendre la classe String présente dans le JDK21.

La classe String présente de nombreuses méthodes utilisées pour manipuler des chaines de caractères et dispose de nombreuses méthodes très utiles. Nous allons étudier seulement une partie des méthodes de la classe String, mais vous pouvez vous référer à la documentation en ligne pour en savoir plus.

Nous en profiterons pour en apprendre plus sur les types Java, notemment les types numériques et les opérateurs.

Et finalement nous aborerons la création de programme pour programmes pour découvrir des patterns et de l'information dans des Strings (e.g. tous les liens sur une page web? quels sont tous les gènes dans un brin d'ADN?)

Les Strings avec l'ADN

Travailler avec des Strings représentant de l'ADN

Nous allons commencer par chercher des gènes dans des Strings. Ceci est un exemple réel (mais très simplifié) d'une recherche de pattern dans une chaine de caractère. Vous pourrez généraliser cette approche avec n'importe quelle application, telle que les pages web, les emails et tout contenu textuel.

Nous aurons également une belle occasion d'appliquer à nouveau la méthode en 7 étapes.

LEs 4 lettres ATGC sont appellés les nucléotides. Ils sont les briques composant l'ADN. Un groupe de 3 nucléotides représente un codon.

Etape 1

Hypothèses:

  • Début du gène : "start codon" ATG
  • Fin du gène : "stop codon" TAA
  • Gène: tous les codons entre un start codon et un stop codon (inclus)

| remarques il existe d'autre stop codon et les vrais gènes ne contiennent que des codons (donc leur longueur exprimée en nucléotide est un multiple de 3)

Nous allons réutiliser la méthode en 7 étapes pour écrire un algorithme permettant de trouver un gène. Pour cela, nous avons besoin de 3 nouveaux concepts:

Comment représenter la position de quelque chose dans une chaîne?

Exemples d'utilisation de tableau

Utilisation des tableaux de characters pour la recherche

Il est tout à fait possible de coder une fonction de recherche de pattern dans une chaine de characters en utilisant uniquement des tableaux. Il est toute fois préférable d'utiliser les méthodes prévues par la classe String car:

Notez l'utilisation de la classe Character dans le code suivant:

la méthodes String.subString

Consultez la documentation de la méthode substring et comprenez son usage, puis testez la et répondez aux questions de l'extrait de code.

Autres méthodes que nous allons utiliser

Live Coding Recherche simple de gène

On cherche un volontaire

Améliorons notre algorithme pour trouver plusieurs gènes

Des Outils supplémentaires: la boucle while et les ArrayList<>

Algorithme à implémenter

  1. on trouve la première occurrence de ATG
  2. on trouve le TAA après ATG
  3. Vérifie que la distance est un multiplicateur de 3
  4. ce n'est pas le cas, donc on trouve le prochain TAA

Boucle While

Méthode en 7 etapes

Boucle While

\scriptsize

                       11  13  15  17  19  21  23
                       v   v   v   v   v   v   v
 A T G A T C G C T A A T G C T T A A G C T A T G
 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^   ^   ^   ^   ^   ^   ^
 0 1 2 3 4 5 6 7 8 9 10  12  14  16  18  20  22
  • nous avons trouvé que la première occurrence d'ATG était à l'index 0
  • nous avons trouvé que le "TAA" après l'ATG à partir de l'index 3 commençait à l'index 8
  • nous avons vérifié si la distance entre eux était un multiple de 3
  • ça n'était pas le cas, donc nous avons trouvé le "TAA" suivant commençant à l'index 9
  • nous avons vérifié si la distance entre eux était un multiple de 3
  • c'était le cas, donc tout ce qui est entre ceux deux codons est ma réponse

Généralisation

Généralisation

Généralisation

Généralisation

Généralisation

Généralisation

Généralisation

Généralisation (enfin)

Syntaxe de la boucle while

 while( x < y ){
   System.out.println(x);
   x=x+3;
 }

Live Coding!

3 codons de fin

Quel codon choisir?

On veut celui qui arrive en premier (ici TAG)

3 codons de fin: résolution en repartant de l'algo d'avant

Algo d'avant

  1. trouver la première occurrence d'ATG et l'appeller startIndex
  2. si startIndex = -1 retourne la chaîne vide.

Abstraction de la recherche de codon de fin

  1. trouver la première occurrence d'ATG et l'appeller startIndex
  2. si startIndex = -1 retourne la chaîne vide.
  3. findStopCodon(dnaStr,startIndex,"TAA") et appeler le résultat taaIndex
  4. findStopCodon(dnaStr,startIndex,"TAG") et appeler le résultat tagIndex
  5. findStopCodon(dnaStr,startIndex,"TGA") et appeler le résultat tgaIndex
  6. prendre le plus petit entre taaIndex, tagIndex, tgaIndex et l'appeller minIndex
  7. La réponse est le texte commençant à startIndex jusqu'à minIndex + 3

FindStopCodon

Live Coding