Prologin
2025
É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.