Tous les défis
Moyen 0 résolus 0 % de réussite

Répétitions en tandem courtes (STR) dans l'ADN

Pour chaque répétition en tandem courte, trouvez la plus longue suite de copies consécutives dans une séquence d'ADN.

Ce que vous allez apprendre

  • Comparer une sous-chaîne à un motif
  • Compter les copies consécutives à partir d'une position
  • Garder le meilleur compte pour chaque motif

Problème

Les laboratoires de police scientifique comparent les individus grâce aux répétitions en tandem courtes (STR, short tandem repeats) : de courts motifs d'ADN, comme AGAT, qui se répètent de nombreuses fois à la suite. Pour chaque motif, le laboratoire relève la plus longue suite de copies consécutives dans toute la séquence. Dans TTAGATAGATAGATCAGATAGAT, le motif AGAT apparaît trois fois de suite près du début et deux fois plus loin, donc son compte est 3.

Implémentez dna_str_count(sequence, repeats).

Entrée

sequence : la séquence d'ADN, écrite avec les lettres A, C, G et T.

repeats : les motifs STR à mesurer.

Sortie

Renvoyez un compte par motif, dans le même ordre que repeats : le plus grand nombre de copies qui se suivent sans interruption. Un motif qui n'apparaît jamais a un compte de 0.

Contraintes

0 ≤ longueur de sequence ≤ 5 000

1 ≤ nombre de motifs ≤ 10

Chaque motif compte de 1 à 8 lettres

Exemples

Exemple 1
Entrée :
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Sortie attendue :
expected = [3, 1]
Entrée :
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Sortie attendue :
std::vector<long long> expected = {3, 1};
Entrée :
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Sortie attendue :
long[] expected = new long[] {3, 1};

Explication

AGAT se répète 3 fois au début et seulement 2 fois à la fin, donc son score est 3 ; CA apparaît une fois, donc son score est 1.

Exemple 2
Entrée :
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Sortie attendue :
expected = [3, 1, 0]
Entrée :
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Sortie attendue :
std::vector<long long> expected = {3, 1, 0};
Entrée :
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Sortie attendue :
long[] expected = new long[] {3, 1, 0};

Explication

AATG se répète 3 fois, TATC une fois et GATA jamais : [3, 1, 0].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

À partir d'une position de départ, avancez de la longueur du motif tant que le morceau suivant est égal au motif.

Indice 2

Essayez toutes les positions de départ et retenez la plus longue série.

Indice 3

Un motif qui ne correspond jamais laisse le meilleur compte à 0.

Complexité attendue

temps O(n × m × k), espace supplémentaire O(m)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.