C’est la séance 2B0 de la formation 2013-2014.
Ce TP met en œuvre la recherche de sous-chaînes et l’utilisation d’heuristiques dans un contexte d’application à la génomique.
Il est inspiré par le document élaboré par Pierrick Bouttier au sein du groupe Algorithmique et Logique de l’IREM, lui même basé sur l’article À la recherche de régions codantes de François Rechenmann sur http://interstices.info.
Sommaire
Introduction
On reprend ici les deux premiers paragraphes de l’article de François Rechenmann, ce qui nous évitera de mal les reformuler.
Stricto sensu, le génome d'un organisme est l'ensemble de ses gènes ; autrement dit, l'information nécessaire à ses cellules pour synthétiser les protéines qui assurent des fonctions diverses : structure, transport, catalyse, etc. Par extension, le terme génome désigne également le support physique de cette information, la molécule d'ADN (Acide DésoxyriboNucléique), composant des chromosomes présents au sein de chacune des cellules de l'organisme. L'ADN est un enchaînement de nucléotides de quatre types différents distingués par leur base azotée : adénine, thymine, cytosine et guanine, et notés par les initiales A, T, C et G. Et c'est cet enchaînement qui code l'information génétique, au même titre qu'une suite de 0 et de 1 peut coder un son, une image ou une suite d'instructions.
Au sein d'un gène, et plus précisément au sein de sa région codante (ou CDS pour CoDing Sequence), la suite des triplets de nucléotides, appelés codons, dicte la séquence en acides aminés de la protéine. La correspondance entre les 64 (4³) codons possibles et les 20 acides aminés constitue le code génétique, identique à peu de variantes près chez tous les organismes vivants.
Données
Pour référence, voici la liste des nucléotides 285000 à 290999 du génome de Bacillus subtilis subsp. subtilis str. 168, tirée de la base de données European Nucleotide Archive (ENA).
TTTAACGACTATCGCGGATATGTCCGCTGTACAGTGACGCCTCACCAAGTGGAAAGCCGA TTATCGGGTGATGCCATTTGTGACCGAGCCGGGCGCAGCCATTTCCACGCGGGCTTCATT CGTTTACCAGAAAGACCAAACCGGGTTGAGAAAGGTATCATCCACAACAATCCAAGGCGG GGTGAAGCAATCCGATGAGGTCGAAGAGGATCGTTTCTTTTCGCACAACAAAGCCCACGA AAAACAAATGATTAAGAAGCGTGCAAAAATCACGAATTAAGGAGTGGAAATTATGTTTTC AAACATTGGAATACCGGGCTTGATTCTCATCTTCGTCATCGCCCTCATTATTTTTGGCCC TTCCAAGCTGCCGGAAATCGGGCGTGCCGCCGGACGGACACTGCTGGAATTTAAAAGCGC CACAAAATCACTTGTGTCTGGTGATGAAAAAGAAGAGAAATCAGCTGAGCTGACAGCGGT AAAGCAGGACAAAAACGCGGGCTGAATGCTGATGAGGCAGACACCGGGTCTGCCTCTTTT TTTATGAAAGGGAGGGCTTTTTTGAATGGATAAAAAAGAAACCCATCTGATCGGGCATTT AGAAGAGCTTCGCCGCCGGATTATCGTCACCCTTGCGGCATTTTTTCTATTTCTCATCAC GGCTTTTTTGTTCGTACAGGACATTTATGACTGGCTGATCAGGGATTTGGATGGAAAGCT GGCTGTGCTAGGACCGAGTGAAATCCTCTGGGTGTATATGATGCTTTCCGGCATTTGTGC CATTGCGGCTTCTATCCCTGTTGCCGCGTACCAGCTGTGGCGTTTCGTTGCACCGGCGCT GACTAAAACGGAGCGCAAGGTGACGCTCATGTACATCATGTACATACCAGGTTTATTTGC GTTGTTTTTGGCGGGCATCTCCTTCGGATACTTTGTCTTGTTTCCGATCGTGCTCAGCTT TTTGACTCATTTATCCTCCGGCCACTTTGAAACGATGTTTACGGCTGACCGCTACTTTAG GTTTATGGTGAATTTGAGCCTGCCGTTCGGCTTCTTGTTTGAGATGCCCTTGGTGGTGAT GTTTTTAACAAGGCTGGGCATCTTAAATCCTTACAGACTGGCCAAAGCGAGAAAGCTTTC CTATTTTCTGCTGATTGTCGTGTCCATATTGATTACACCGCCTGATTTTATTTCTGATTT TCTCGTGATGATCCCGCTTCTTGTCCTGTTTGAAGTGAGTGTCACCCTATCGGCGTTTGT CTACAAAAAGAGGATGAGGGAAGAAACAGCGGCGGCCGCTTAGTGCAGCGTACCACCCGG TGACTTCACATCCTCATCATATTGTGCGGCCGTAACAGCGGCGATTCTCAATGCCCGGAC AATCGTGTCCAGGCTGAGGCTCGGCGCTGTTTTGTCGATTGTTTGCTGCGGAATGTAAGG AATATGAATAAAACCGCCGCGAATGTGTGGGGATGTCCGGCTAATGTGATCCATTAACCC GTAGAACAAATAGTTGCATACAAAGGTCCCCGCTGTGTAGGAAACCGCAGCTGGAATGCC GTGTTCCTTCATCTTAGCAGTCATTCGTTTCACGGGAAGCCTTGTCCAGTAAGCGGCGGG CCCATCTGGAGAAATCTCTTCATCAATCGGCTGATGTCCTTCGTTATCGGGGATTCGCGC ATCTGCAAGGTTGATTGCCACTCGTTCCGGTGTAATCTGCATCCGTCCTCCTGCTTGGCC GACACAAATTACGATATCTGGCTGATGTTTTTGAATGGCTTGGCGCAGAGTGTCCAGAGC GGATCTAAAGACGGTTGGAATTTGTTCCGCTGTAATAATGGCTTCTTCTGTCTCGAAGCC ATTAAGCCGTTTCGCCGCTTCCCATGATGGATTGACGGTTTCTTTGTCAAAAGGGTCAAA GCCTGTGATCAGCACTTTTTTTCTCATTCTCCCATCTCCTTTTTCTTTTATTCTATTGTT TATTTATGGGTTTTTCATCAAAATAATGTAAAGGAGTGAATCATAATGGAGCATTTGCCG GAGCAGTATCGCCAGTTATTCCCAACCTTGCAGACGCATACGATGCTTGCCAGCTGTTCT CAGAGCGCATTGGCAGAGCCTGTATCAAGGGCGATCCAGGATTATTATGATAGCCTGCTG TATAAAGGGACGAACTGGAAAGAAGCGATTGAAAAAACAGAGTTTGCGAGAAACGAGTTT GCAAAGCTGATCGGGGCTGAACCGGATGAAGTGGCGATTGTGCCGTCAGTTTCTGATGCA CTGGTTTCTGTAGCATCGTCCTTAACTGCATTTGGAAAGAAGCACGTTGTATATACAGAT ATGGATTTTCCGGCGGTGCCTCATGTTTGGCAGGCACACTCCGATTATACCGTATCCGTC ATTCCATCAATAGACGGCGTGCTGCCGCTTGAACAATATGAAACGCATATTTCGGATGAA ACAGTACTGACGTGTGTTCCTCACGTTCATTATCGTGACGGCTATGTTCAGGATATAAAA GCGATTGCCGAGATTTCTCAGAGAAAGGGCTCTTTATTGTTTGTAGATGCTTATCAATCA GCCGGGCATATTCCCATTGATGTGAAGGAATGGGGCGTAGATATGCTGGCAGCAGGCACC CGGAAGTATTTGCTCGGCATACCGGGTGTGGCGTTTCTTTATGTGAGAAAGGAGCTGGCT GACGCACTGAAGCCGAAAGCATCAGCTTGGTTCGGAAGAGAGAGCGGATTTGATGGGGCT TATGCAAAAGTCGCGCGCCGTTTTCAAACGGGCACCCCAGCTTTTATCAGCGTATACGCA GCTGCAGCGGCTTTATCGCTGCTGAATCATATTGGGGTTTCTCATATCAGGGATCATGTG AAAACGATCTGTGCCGATGCAGTTCAATATGCCGCTGAAAAAGGCCTGCAGCTGGCGGCG GCACAAGGTGGGATTCAGCCGGGCATGGTTGCGATCCGGGATGAGCGGGCATCGGAAACG GCGGGGTTGCTGAAGAAGAAAAAAGTGATTTGCGCGCCGCGGGAAAATGTTATCCGTCTC GCTCCCCATTTTTATAATACGAAGGAGGAAATGCGGCACGCGATTGATGAAATCGCGGCG AAAACGATCCACAAGTAAACATGAAAAAGCCCCTGAACACTAGTCAGGGGCTTTTCATAT TAATGATCTACTTTAACGCGTTTCATAAAGAAAGCGCCAATTAAACCGATAATGGCAACA ATCATTGCAAACACAAATGCGTGCTGTACGCCTGCTGTCAAAGCTTGCGGGATGACTGCC GGATCGGCAGGGTTTTTAACTGTACTCATATAATCATGCTGGCCTGCAGCCATAATGCTG ACCGCAACCGCTGTTCCGATAGCGCCGGCCATTTGCTGCAGCGTGTTCATAATGGCGGTG CCGTCTGGATAAAATTCACGCGGCAGTTGGTTTAAACCGTTTGTCTGTGCAGGCATCATG ATCATAGAAATCCCGATCATCAAGCAGGTGTGCAGGATGATAATCAGCACAGCTGTTGAA GTGGTCGTGACATTTGAGAAGAACCATAGTACAACGGTGACAATCACAAATCCCGGAATG ACAAGCCATTTCGGCCCGTATTTATCGAACAAGCGGCCTGTAACAGGGGACATAAATCCA TTTAAAATACCGCCCGGCAAGAGAACAAGACCAGATGCAAATGCAGTGAGGACTAAGCCG CCTTGCAGATACATCGGCAGAAGCAGCATAGATGACAGAATGACCATCATACAAATGAAC ACCATGATCACACCCAAAATAAACATCGGGTATTTGAACGCACGGAGGTTCATCATAGGC TGCTTCATTGTCAGCTGGCGGATTGAAAATAAGATAAGGCCGACAACGCCGACAATCAGC GACACGATAACAGTCGGGCTGGACCATCCCCCGGAGCCTTCACCCGCGTTGCTGAATCCG AATACAATGCCGCCGAAGCCAATCGTCGACAGGATGATAGACAATACATCGATTTTCGGC TTTGTCGTTTCAGATACATTTTGCATATATGCGATACCGAAAACAAGCGCCAGCACAAGG AATGGAAGAGAGATCCAGAAAATCCAGTGCCAGTTGAGATGCTCCAGAACCAATCCTGAG AAAGTTGGGCCGATGGCGGGCGCGAACATAATGACAAGCCCGATCGTTCCCATTGCGGCA CCCCGTTTATGAGGCGGGAAAATCACCAAGATTGTGTTAAACATCAGCGGCAGTAAAAGA CCGGTTCCAAGTGCCTGAACGATCCTTGCCGCTAATAAAAACGAGAAGCTCGGCGCAAGC GCCGCAATGAATGTACCTAAAATTGAAAAGATAAGTGACACGGTAAAAAGCTGTCTTGTT GTGAACCACTGCAACAGCAGTCCTGAAACAGGAACAAGGATACCGAGTACAAGCAGGTAG CCCGTCGTTAACCATTGGACGGTTGCCGCTGTAATGTTCAATTCCTTCATAAGGTCGGTT AACGCAATATTCAGCGCTGTTTCACTGAACATGCCGATAAAACCGGCCAACAGCAAGGAA ATCATAATCGGCATCACTTTGTATTGCTGAGATGCTTTAGCTGTTGTTTCCAAAATCATT TCCCCTCTCTATCAACTGCATGTAGTATGTCGTTTTTTTTATCTCTTCAGCAGGTCAGGA ATGCAGCTGGAGATATGAAGGAGCGGCGTACTGTTTTTTGCCGTCAAAGATAAAAGGATG CCGCCTTCAATCATCGCGTTAACCACAGTGCTGGCTTCTTTTGCACGGCTCTCGCTGCAG CCAGTCTGCCGCAGTTTTTCCTCATACACAGAGGCCCATTCTTTGTAGGCTTCATGACAG GCTTCGCGCAACGGTTCGCTTTTCAATGACGTCTCAGCCGCTAGCAAGCCCACAGGCAAG CCTTCAATGTCTTCCGTACATGAAAACTGGCAGGAGAGCTCCTTCAAAAAGGCTTGAATG CCTTCCGCTGGATCGGTGCAGGCTTCCATGCAGTCCGCGATTTTCTGACGGATATACTCC TTCATCTCATTCACGGCTTCGATCGCAAGCTGTTCTTTACCCCCGGGAAAGTGGTAGTAA AGAGAGCCTTTAGGCGCGCCGCTTTCCTTTATAATCTGGTTCAGCCCCGTGCCGTAATAC CCTTGCAGCTGAAAAAGCCGGGTAGCTGCCGAAAGGATTTTCTCACGGGAATCTCCATAA CTCATAACATTCCCACCTTACTGAATTGCAATCAAAAATATAGTGACTGGTCTATTATCT TGATTCAATCATCAATTGTCAAGAAAAATTCATTGTATGAAAAGACAAAAAAAGAAGGAT ATGACAACAAAAAATACTGAGAGAAAAGCTGACTGATCTTTTGACTGAATAGATAAAATG TACAATGATTAATCATCATATGGATGTAAGGAGAGAAATAGATGAAAAAACAACGAATGC TCGTACTTTTTACCGCACTATTGTTTGTTTTTACCGGATGTTCACATTCTCCTGAAACAA AAGAATCCCCGAAAGAAAAAGCTCAGACACAAAAAGTCTCTTCGGCTTCTGCCTCTGAAA AAAAGGATCTGCCAAACATTAGAATTTTAGCGACAGGAGGCACGATAGCTGGTGCCGATC AATCGAAAACCTCAACAACTGAATATAAAGCAGGTGTTGTCGGCGTTGAATCACTGATCG AGGCAGTTCCAGAAATGAAGGACATTGCAAACGTCAGCGGCGAGCAGATTGTTAACGTCG GCAGCACAAATATTGATAATAAAATATTGCTGAAGCTGGCGAAACGCATCAACCACTTGC TCGCTTCAGATGATGTAGACGGAATCGTCGTGACTCATGGAACAGATACATTGGAGGAAA CCGCTTATTTTTTGAATCTTACCGTGAAAAGTGATAAACCGGTTGTTATTGTCGGTTCGA TGAGACCTTCCACAGCCATCAGCGCTGATGGGCCTTCTAACCTGTACAATGCAGTGAAAG