J'aimerais faire une sorte d'algorithme de "recherche et remplacement" qui, de manière efficace si possible, identifie une sous-chaîne d'une chaîne qui survient plus d'une fois et remplace toutes les occurrences de cette chaîne sous-chaîne avec un jeton. Par exemple, avec une chaîne "AbcAdAefgAbijkAblmnAbAb", notez que "A" se répète, réduisez donc la première fois à "# 1bC# 1d # 1efg # 1bijk # 1blmn # 1b # 1b" où #_ est un modèle indexé (nous notons les motifs dans une table indexée), puis notons que "# 1b" se reproduit donc réduire à "# 2C# 1d # 1efg # 2ijk # 2lmn # 2 # 2". Plus de motifs apparaissent dans la chaîne, donc nous avons terminé.Sous-séquences récurrentes et compression
J'ai trouvé quelques informations sur les "plus longues sous-séquences communes" et les algorithmes de compression, mais rien ne semble le faire. Ils sont soit pour comparer deux chaînes ou pour obtenir un résultat de stockage optimal.
Mon objectif, d'autre part, est de réduire le génome à ses "mots" au lieu de "lettres". c'est-à-dire, au lieu de gatcatcgatc je veux voir 2c1c2c. Je pourrais faire quelques regex après pour trouver des choses comme "# 42 * # 42"; ce serait cool de voir des parenthèses récurrentes dans l'ADN.
Si je pouvais juste trouver cela en ligne, je sauterais le faire moi-même, mais je ne peux pas voir cette question répondue en termes que je pourrais découvrir. À tous ceux qui peuvent me diriger dans la bonne direction merci beaucoup.