La créature inconnue

Ces énoncés sont ... romancés... Sachez faire la part des choses et gardez à l'esprit que :
  • les problèmes réels de comparaison de génome ne ressemblent que de vraiment très très loin à celui proposé ici ;
  • bon nombre de choses sont inventées dans cet exercice...

Suite à une chute de météorite contenant des traces de vie, l'ADN d'une créature encore inconnue a été prélevé. Ce prélèvement est présenté sous la forme d'une grille 80x80 composée de lettres prises dans l'alphabet : ''AGTC'' (ce sont les 4 nucléotides Adénine, Thymine, Guanine, Cytosine qui forment une molécule d'ADN. La page Wikipédia sur le sujet est très bien illustrée : ADN).

Afin d'identifier l'organisme, on compare le nombre d'apparitions de certaines séquences particulières, avec le nombre d'apparitions de ces mêmes séquences dans des organismes déjà connus. Les séquences caractéristiques sont : AGTCA, TGCA, AAGCT, AGTC et AGTGG

Ces séquences peuvent apparaître verticalement (de haut en bas ou de bas en haut) et horizontalement (de gauche à droite ou de droite à gauche).

Pour identifier l'organisme, il faut donc rechercher le nombre d'apparitions de chacune de ces séquences. Nous appellerons cette série de 5 nombres la signature génétique de l'organisme.

La différence entre deux signatures génétiques vaut exactement la somme des écarts (en valeur absolue) entre chaque nombre de la signature (ce type de distance existe réellement et s'appelle la distance de Manhattan).

  • la distance entre 10,7,4,19,7 et 12,6,4,18,9 est donc : 2+1+0+1+2 c'est à dire 6
  • la distance entre 10,7,4,19,7 et 12,5,4,19,8 est donc : 2+2+0+0+1 c'est à dire 5

Deux organismes sont d'autant plus proches que la distance qui sépare leurs signatures respectives est faible. L'organisme 10,7,4,19,7 ressemble donc plus à 12,5,4,19,8 qu'à 12,6,4,18,9.

Voici le tableau récapitulant les signatures génétiques des organismes extraterrestres connus :

CréatureAGTCATGCAAAGCTAGTCAGTGG
Andorien31 100 36 97 20
Bétazoïde36 102 32 91 21
Kazon38 106 35 90 29
Cardassien 36 107 32 97 24
Tellarite30 102 33 98 27
Ocampa31 108 31 91 25
Trill32 103 32 91 25
Rémien35 100 36 97 26
Ferengi31 108 38 97 22
Denobulan37 109 36 92 25
Anticanien33 109 36 98 28
Ligonien39 100 30 91 22
Xindis36 108 38 93 21
Talaxien36 108 39 90 22
Suliban33 101 33 99 21
Vorta36 104 35 97 29
Klingon38 100 32 90 27
Dreman30 109 34 92 27
Benzite33 104 37 90 27
Breen34 108 37 93 20

Voici la grille contenant le prélèvement d'ADN :

CGTCGGCGCACCCGAAATCGGAGGTTCGCTAGCGAGGTTCTCACAGTCAGAACTTTTCTTCTTATGGGTAGTATGATCAG
AAGGCAACTAGGTCTATTCTCGTATGCTCCCATTCATAAATTGGATTATAATACAAACTACGCGAGCATGGGATGACTAT
GAGATCGAGTCTGTGAAAGTTAAGGGCGGTTAAGACTACAACGGTTATAGGTGCAATATCGTCAAGGCGAAGCCTCGTTA
TTTGTTCTCCGATCGTCTTGTGGTCTACTAGCAATGTAAACCCCGATCACGCAACGGGTCCTACGCCCCTACGCTGGACG
ATGATTAAATTCACCGAATGTTTAACCACGCTGTTGAAGGCACATCGTATGAACTGTGGACAAGGGCTAGTTGCCCGGGG
GGTACATTCGTAGGCCATATGCCGACAAAAATGCTCATAACAAACACAGCGCGCTGGGTAGAGATCTGGAGTACATTAAT
GTGAGTACTTTGATGGGAGCGACTCACGACTATACGTGTCGCGTCGTGATCGGAAACTACTCAGCGGTCTATCTATTTGC
GTAGTAAAATCAAGGGGCAAAAACTCTAATAGTTGAACAAGGTGCGGATCCACATATTCTAGCTCATCCCATGTATCGTA
TAAAGCAAACACACCCGGACTGCTTCGATCAGTAATACCGACAACCGCATGCTGTCTAACAAACCCGATAGTAACGGAAT
GTCGCTCCCAAGATGTATAGAACTAAGCTGCACCACAGGTCTGATACATTTTTTGCCGGCGATAAGAAATTACCGGCAGT
TGGCGAATTTAGTGTCCGGGGTAGCATAAAGTGGGAATGTCGCTAGATTGAATGTACGCAACTAATTCGGGAGGTAGATG
CATATGTGGGAGGCGGGTCAGCAGCTGCAATTGGTAAGTCCCGTTTTACAGGACTGTACGAACACGTCCTACCATGATCG
TCGTATCTACTGCGGAGAGCGTTGATTTTGGGGCGTACGAGACGAATCCCCACCAAAGTAGGAGATGTCGAGCTCGCATG
GAGAGGATCGTGATTACCGTAGCATTGGCTGTTAGGAGCGTTGAAAGGTTGTTTATTGCATTTAAGCGGTAAGCCATCGA
GCGAGTGGATACGTCGGAGGCGTATGCCGCACGCCTATAGAGGGGCAAGGGTGACCATTCAAAGTACTCTAGTTGTTATG
TTCTATCGATATCATCGACTGCATCTGTGTACGGGGACGCGGCACTACCTAGGGGTTTCGAGGACTTGTGCCGCTATCCG
TGCGGGCCGAATCATTGCGATATTGCTGCATTGTATTATGGCACGCACTCGTTAACCATGACCCACGCGATTAGTGTGGG
GTTGATGCGACGAAAAGAGCTATAGACTAGTTCGAGAAGCGCAAAGATTATGCCGTTCACGCAGCCAAGAAACGTTCCGG
AGTTTCCTGACGTCGTCACTAGGAAGCCCTATTGGGACACCGGCTCTGTTCCTCGCACCTCATAGGAGTCCGCGCAACTT
TCCGCACTAGCACCCTTAATTCGTCACCGTTCCGCTACCTGTTCGAATCTGGAGACCTATCTGGTGGAACGCGGTAGGTG
GAGTTTTATTCCGGCGTTCCCGAGTCGCTCCGTGGATTAATTGTCTGCCTGTATTATGTCTATAGCCTGGCCCTGAAAGC
GGCTACCTTAGGCTCCTGCTATAAATCACTGTGATTTTAAACCCCTCGGGCAATTTTACTGTACAGCTAACGGGATCCTT
TCCGTAATCTAGCCGTAGTACTCAAGTGAAGTGCTAAGGTATTTGAGTTTCTGGTCGAAGGCGCTTTGGCACTACAATTG
CTCTAACGAACCGGACTGTCATGAGCTTCCCCGGACCCTTGACGATCATTCTTGGGGCTGGGTGGTTAGACAGCCTTATC
GGGCTTGACCCTCTGACCATTAGTAGATATACTCTGACCTTGAGGATATACGTTGTCCCGCACCTCAAAGGGGGATATTG
GAAATCCCATCCCTTCCAATAAAACGAGCGCACGCCCGTATATAGTACCAACCTTACCAGTCACATATGATGTTTATGGG
ATTAACGCAGGTGACCGCAGGCAAAATAAGGAAATGCACGATTGGTTTGAAGCCGCGATAAGTCGCTGACAGTATAGTGG
TCGTTACTTACACTTCTCGACTCGTAGAAAGGCCAAGGCCTCTCTACGAAGTAAAGCAGACTCGAACATGGAAACTCACG
AGGATCCAGGCGAAGCTGATGTTGACTACAAACGCTGCCGAATGGCTAGTTATGTCTGTGAGCCTACTACTGCTGGAGTG
GACGCCTAATTTGAGTTGGCGTTAAGGCCGTATGGGCAGATAGGGGGGAGAGGCCTACGACGGGTAAGTGATGAAGGTCG
CATCGGTGCGCTTGGACATAGCCCAAGCCGCGAGGATTAGCGTGGTTACTAACGCGATACAGTTACTTTAGTGAAGTTTG
TAGGATTGTGAGCTTTCCTCAAGGGGCCGATCCGTAAATTAAGCGGAATATGGAGATTCACTCGTATGTGGAATGATGCG
CCAGGTCGACGTATGTTGATTTAATGTACTATCGGGATAACTGGACGCATACCGCCGACTCAGTGCGGTTGTGCCTTGGG
CGTCGCCCCCCTGCTTCTGTAGGGTCATGACGCTCCGACATCTGCTGGGCTCTCTAACCGAGACGGGCTCTATGCAAGGT
TTCCGTAAAGGGGGAGTGAAGGTATATACCGAAGCTAATTGAAACCAGGAGGACGACGGTAAAATCCCAGCCAGGACTCT
GGACGCTATTGGGTCTAGGCAAGCATACCGAGAACGCCCGATAGGTTACTCACGTTGTGACGATACGATTGCGGTGGAAC
GTACCAATCTTAAAGGCGTACTGTGGTTAAAGCCTGTGACGGTATCATGGCACAATTTGTCAAGCTGCGCAACACGTCTG
AGGGACAGCCGCCTTCCTGAACCACGTCGTGCCTACGCTGTACGCGCTGGGGTACGGTCACTAGGCTCGGCACGGTAAAT
GTCGAGCGCAATACGCGGAACGGCAGGATCAACCATTACCGTGTAGCTGATACTCTGTGTGTTATCTCTACATTCTGATG
TTTCATTTTAGAGCTTAGGTGCATCCATCTTTGAACCCAGCTAACCGGCGGTGTCCGTTCACCCTAATGGCGCTGAACCT
CCGGTCCGGGTTTATCAAGGAAAAATCCGAACTCGTATGCATCGCGCGTCGTCACAAAGTTCTTTGAGATGCTTCAAGGT
TTGATCCTTGGGCGATTTACTGGCTTTACACTATCGACGGAATTATCCCAACCGGACTTATGTATACATTTCTTACACAG
CTCGTTTCGGCCAGACCCCGTTTCGTATAGCTAATGTTACGATATTTTCCTATGGGGACGATGACGCAATTAAGGAAAAA
GCATGATGCTAGATAGCACCCCCACGTAGGAAACTGTAGGATACAGGTCTGTAGCCGCACAAAGAAACCATCTTACAACT
ACAACAGGGGCAGCCTGTCAAGATGGTCAGCACGTTATTACTTTGGCCCGTGCCGCGAGCAATATAAAGTATTAGGTGCG
ACATAGTAAGAGCTTTCAGTTGCAGATAGTTGTCGGGGAGCCCGGTGAGTGTAACTCGTAGTGATGGCTCAGTTCGACCC
ACATTGGAAACTCGGTTAGTACAAATCACTTGGATTTCGCCTGAGGACCGTACAATGCCTGCCACCTAAACAGTCATGGA
GCTCAGGATCACCTATAGGGTGACATGTTGTCAACGCGCCAATGACAGGAGGGGATCTCTGAACTTCGCGCCAATCAGCT
TATAAACTACTATCTTCCGATAGCACCATCCAGAGACTTCCGCGTATGAGAGAACAACTGCCATTGTCCCTAAGGGACTG
GCCGCATAAGAAGGACCCCATTGTAACTCAACGTAAGTGTTCGACGGCTTGCATTTCTTGATTAGATCGAGCACGTCCCG
TCGGGACTGTATTTGTATTGCTCCTAGTAGAACACGCATGGCAGCACTATGTTCTTTCACCCCATCGTTCGGTGATCGGA
TTATACCCAACGATATCTATTTGACATTACATTCGTAACCTATAACTTCCTTTGCAGTGCTTTGCCTTTGCGAGTACGAA
ACTCGGCACATTTGGCAGCCTACAGACAAACCGACCTGGAGTTTCTCGACAGGCGCTAAACTTGTTTGGTGGCAGTGCGC
AGCGCTCCGTACCACCACGCGTCGGATTGATCCGGGCCAATGTCATGGCCGGGGCTGATACTTCGTTAGCGTGTAAGAAC
AGGCGCTCCTGAAGTACCTACGATACGTTCACGCATGCAAACGAGCCCTTAGAGCCTGCCCGACGTCCGTTAATATGGCG
AGCAGAAGGCATAAATGCTGTTAATCAAGCTTCCTGTACTCCCGCTTATTTACTACTGTGCCAAGTGGAGTTAATGTTGA
GACAAGGACTTGCTTGGTGACCCAGCGGGCTACAACATCCTGAACTTGCCCATGGGTCCGGAGTGTTTCTAGGGGACAAG
GGTTAACAGTATTACCGTGATATTTTCTAACCACGTCAGCCCAATTTAATTCGAAACATGTCGAGTGTCCACTTATGGGC
TACCAAGCTCTAGCGAGTGTAATCTCCGCCTAATGCTCCCCCTAGGAACGTCAGAACGGGACGCGCGTTGCGTACAGAGA
GTTCTGAAATCGGCACTATAAGTGATTAACTGGGTACCGGTCGTTCAGCATCAGAAGCGTCCATTAACCGTGAGCGCGGA
AGATACTGCAGGCTTCATCTCCTCGAGTAATTTTGATGTATGGCATGAATATATACCGTGCATGTGGTTGCTGGCATGAC
CCTGAAAGTCAGAGACTAGTTCCCAGGCCTCGTCAGCTCCTCCCGAGCGCTCACGTCACGTTGATTAATGTCTGCTTGGG
TGGTCTGCCCGTAGCCAGAACTTGGTCGGTATTCCGCACGCACTAAGGCGTGTCATAGAAGCGTCCCTGCTCACCGCGGC
GCAAGGTGAGCGTACATCTTGCCAGGACACAGGTACGGAGAATCCTATCGGGAAGGAGGCCATAACAGTGAGTACAGGTT
CTTAACCCAAACATTCCCTTGGCGGACTACAGAGTAAGACCGGCAACAGCTAAACGAGATTGCCTAGACTTAACATACTC
AGTGATAGTACTCTCCAGGATTTGCCCCGTTAGCAAGTTCGACAAGCTGCGAGCGGATCTCATAGATATCACGACGGGCT
TCTCAATCGTCGTCTAACCAAAGCTACCTATTCGTTCCCCGGGCGACTAGGTTTCTGGGGCCCGGTATGGTAAATTTGTA
TTCGTTATGGCTTTGGGGAGTAAGCACCTAAAAACTGACCTCAGGCCTGTAAATATTCGTAACCCAACACCGCTGGTCTG
TGAGGCGAAAGGTCGCCGGCGCTGCTTGTCGAAGTGGTAACTTGGCTTCTTGCATGACCCATGGATATTTCATAAAGGGA
AGGCTCGACACAATCGCACATCTGACAGAGTAGACTGATTGGTCCGTCGCGTTGTGAGAATTGGTCCAGTAAGCCCAAGT
CTTATACGTCCGTAGTTGATGCGGTGGAACCCATTGAGAGACGAGAATCCCTGGTGATCAAGGCAAGGTGTACCACATCA
AGTAATCCCGTAAAGGTCCTTGCCCTACAGTGAATTTGCCAGCCAGTCTCGGGATTACCATATAACCTCCGTATCCGATC
TTATGGAAACTGGGAGAAGGTAGACCGTGGTAACTACCTAGAAGTCGCAGTCACGGAGTACCCCGTGACATCCATATGGG
ACTTAGGCCGCACTATAACGGCCAGCCATTCAAAGGAGTATTTAGTCACCCGCATCTGATCGGACGTAGTGTCTTCAGCG
CTACGCCTTGTTCGCAAACATTGCTAAGGTGTCCTACTCTCCCCGGATAACCAAAGGAGAGGCCAGATAAGCTTCATCTG
CCGCAAGAACAAGCGCGAACTCAGTCCCGCTGGTTATGGGGTCACTTGCTCTTCACTCCCCCTCCAGGGGGGAACTCGTA
TTGGCCGATCGGGATTGGAGTAGAGGTGATTCAAGGTAAACCGACATTTCGTGCGACTCTATGGAGTATACAGAAATTAC
TGGACTCGGAGAGGCCCTAGCGACCCGAACCGATATAGCAAGGATTAAGGCTTTCAGCAGTTACGTTTCCCATTCGATAC
GCGACTCGATGGCCGAGTAAAGACACAGAGAATTCCGGGTAAACTTAATCTGCATGTTGATCCAATCTACTCTCCGACGT
CCTCGAGAAGTACTGGAAGGCTCCCTGAGATAAACACACGCAACTTGTCCTCACTAAATGTGCAACAACTGTGAAAAAAG

De quel(s) organisme(s) déjà connu(s) cette nouvelle forme de vie est-elle la plus proche ? Et quel est leur niveau de ressemblance ? Si l'organisme identifé est XXXX et que la distance qui le sépare de l'organisme inconnu est n, vous devez répondre en écrivant :

n:XXXX

Exemple

Vous pouvez tester votre programme sur la grille 5x5 suivante :

CCCGC
ACCCA
TATAC
GAGGC
TGTAA

Recherchez les séquences : AGA, A, et AT. Votre programme doit trouver que la séquence AGA apparaît une seule fois (dans l'avant dernière colonne ; attention, on ne compte qu'une apparition ici, et non 2, ce qui serait obtenu par une lecture de haut en bas puis de bas en haut des mêmes 3 lettres), la séquence A apparaît 7 fois et la séquence AT apparaît 5 fois. Notez bien que sur la ligne TATAC, AT apparaît 3 fois (certaines lettres sont partagées par plusieurs apparitions : TATAC, TATAC, et TATAC).

Les nombres caractéristiques seront donc ici : 1, 7 et 5 (pour les séquences AGA, A, et AT).

Si la table de référence était :
AGAAAT
Limaçon de Folfanga1 8 3
Porc Taudanzain vert2 7 6

alors, nous pourrions conclure que le nouvel organisme ressemble probablement à un Porc Taudanzain (vert), car l'écart avec un porc est 2 alors que l'écart avec un Limaçon de Folfanga est 3.

Dans ce cas, il faudrait donc répondre:

2:Porc Taudanzain vert

Type de retour

une chaîne de caractères

Entrée du problème

Pas de donnée d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : multidéfi chaîne recherche