ADN revisité – Épreuve régionale 2010

ÉNONCɶ

Dans ce problème, une séquence d'ADN est une suite finie de lettres dans l'ensemble {A,T,G,C}. Chaque lettre sera appelée un nucléotide.

Un biologiste dispose d'une séquence s d'ADN de longueur N dont il ne connaît pas l'agencement des nucléotides. L'opération qui consiste à découvrir la suite des nucléotide est le séquençage. Pour séquencer son brin d'ADN, le biologiste fabrique physiquement plusieurs copies de s. Toutes ces copies sont ensuite placées dans une machine, qui les casse aléatoirement en petits morceaux plus facilement reconnaissables. Enfin, la machine renvoie la séquence exacte de certains de ces petits morceaux. Le but de ce problème est de calculer combien de séquences s sont possibles, sachant que s est de longueur N, et en connaissant les données renvoyées par la machine.

Prenons un exemple. La séquence initiale (mais qui nous est inconnue) est TAAACG. La machine en fait plusieurs copies, et morcelle chacune de celles-ci comme suit :

• TAAACG -> TA, AA, CG
• TAAACG -> T, AAAC, G
• TAAACG -> T, AA, AACG

Ensuite, la machine lit certains de ces morceaux (pas nécessairement dans le bon sens !). Imaginons qu'elle renvoie les morceaux suivants : AT, AACG (remarquez que le premier morceau est inversé).

Alors 22 chaînes de longueur 5 sont possibles : AACGAT AACGTA ATAACG ATGCAA AGCAAT TAAACG TAACGA TAACGT TAACGG TAACGC TAGCAA TTAACG TGCAAT GTAACG GGCAAT GCAAAT GCAATA GCAATT GCAATG GCAATC CTAACG CGCAAT

Remarquez que toutes ces chaînes contiennent AT et AACG, dans un sens ou dans l'autre, et se chevauchant éventuellement.

ENTRÉE¶

• Sur la première ligne : l'entier N (entre 1 et 25, bornes incluses).
• Sur la deuxième ligne : l'entier M (entre 1 et 7, bornes incluses).
• Sur les M prochaines lignes, les morceaux d'ADN tels que lus par la machine.

SORTIE¶

• Un entier, le nombre de chaînes initiales possibles.