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éature	AGTCA	TGCA	AAGCT	AGTC	AGTGG
Andorien	31	100	36	97	20
Bétazoïde	36	102	32	91	21
Kazon	38	106	35	90	29
Cardassien	36	107	32	97	24
Tellarite	30	102	33	98	27
Ocampa	31	108	31	91	25
Trill	32	103	32	91	25
Rémien	35	100	36	97	26
Ferengi	31	108	38	97	22
Denobulan	37	109	36	92	25
Anticanien	33	109	36	98	28
Ligonien	39	100	30	91	22
Xindis	36	108	38	93	21
Talaxien	36	108	39	90	22
Suliban	33	101	33	99	21
Vorta	36	104	35	97	29
Klingon	38	100	32	90	27
Dreman	30	109	34	92	27
Benzite	33	104	37	90	27
Breen	34	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 : AT, TAC, et CG. Votre programme doit trouver que la séquence AT apparaît 5 fois, la séquence TAC apparaît 2 fois et la séquence GC apparaît 4 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 : 5, 2 et 4 (pour les séquences AT, TAC, et CG).

Si la table de référence était :

	AT	TAC	CG
Limaçon de Folfanga	5	3	2
Porc Taudanzain vert	6	2	5

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