Comprendre la plus longue sous-séquence commune
Le problème de la plus longue sous-séquence commune (PLSC) est un défi fondamental en informatique avec des applications variées en bio-informatique (alignement de séquences ADN), en contrôle de version (comparaison de révisions de fichiers), et plus encore. Étant données deux séquences (chaînes de caractères, listes, tableaux, etc.), la PLSC est la plus longue sous-séquence commune aux deux. Une sous-séquence est dérivée en supprimant zéro ou plusieurs éléments d’une séquence sans changer l’ordre des éléments restants. Crucialement, les éléments de la sous-séquence n’ont pas besoin d’être contigus dans les séquences originales.
Par exemple, considérons les séquences « AGGTAB » et « GXTXAYB ». La plus longue sous-séquence commune est « GTAB » (longueur 4). Notez que « GTAB » est une sous-séquence, pas une sous-chaîne (éléments contigus).
Approche par programmation dynamique
La programmation dynamique offre une solution efficace. Nous construisons une table (matrice) pour stocker les longueurs de la PLSC pour tous les sous-problèmes. Les dimensions de la table sont (m+1) x (n+1), où ‘m’ et ‘n’ sont les longueurs des séquences d’entrée. La ligne et la colonne supplémentaires gèrent les cas de base (sous-séquences vides).
def lcs_dynamic(seq1, seq2):
m, n = len(seq1), len(seq2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if seq1[i - 1] == seq2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Backtracking pour reconstruire la PLSC
i, j = m, n
lcs = ""
while i > 0 and j > 0:
if seq1[i - 1] == seq2[j - 1]:
lcs = seq1[i - 1] + lcs
i -= 1
j -= 1
else:
if dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
seq1 = "AGGTAB"
seq2 = "GXTXAYB"
print(f"PLSC (Programmation dynamique): {lcs_dynamic(seq1, seq2)}") # Sortie: GTAB
Cette approche a une complexité temporelle de O(mn) et une complexité spatiale de O(mn).
Approche récursive avec mémorisation
Une solution récursive, bien que conceptuellement plus simple, est inefficace sans optimisation. La mémorisation améliore considérablement les performances en stockant et en réutilisant les résultats des sous-problèmes.
memo = {}
def lcs_recursive(seq1, seq2, i, j):
if i == 0 or j == 0:
return ""
if (i, j) in memo:
return memo[(i, j)]
if seq1[i - 1] == seq2[j - 1]:
result = seq1[i - 1] + lcs_recursive(seq1, seq2, i - 1, j - 1)
else:
result = max(lcs_recursive(seq1, seq2, i - 1, j), lcs_recursive(seq1, seq2, i, j - 1), key=len)
memo[(i, j)] = result
return result
seq1 = "AGGTAB"
seq2 = "GXTXAYB"
print(f"PLSC (Récursion avec mémorisation): {lcs_recursive(seq1, seq2, len(seq1), len(seq2))}") # Sortie: GTAB
La récursion avec mémorisation a également une complexité temporelle de O(mn) mais peut avoir un facteur constant plus élevé que la programmation dynamique. La complexité spatiale est de O(mn) en raison du dictionnaire de mémorisation.
Optimisations et considérations pour les longues séquences
Pour des séquences extrêmement longues, la complexité spatiale de O(mn) peut devenir problématique. Considérez ces optimisations :
- Optimisation de l’espace en programmation dynamique : L’approche de programmation dynamique peut être optimisée pour utiliser un espace de O(min(m,n)) en ne stockant que la ligne précédente de la table DP.
- Diviser pour régner : Pour des séquences beaucoup plus longues, explorez les algorithmes de « diviser pour régner » qui peuvent offrir de meilleures performances dans certains scénarios.
- Bibliothèques spécialisées : Des bibliothèques comme Biopython offrent des fonctions hautement optimisées pour l’alignement de séquences, utilisant souvent des algorithmes plus avancés que la programmation dynamique de base.
Conclusion
La programmation dynamique et la récursion avec mémorisation offrent toutes deux des solutions efficaces au problème de la PLSC. La programmation dynamique est généralement préférée pour sa clarté et ses performances souvent meilleures. Le choix dépend de votre familiarité avec la récursion et des contraintes spécifiques de votre application. Pour les très longues séquences, considérez les techniques d’optimisation de l’espace ou les bibliothèques spécialisées.
FAQ
- Q : Puis-je utiliser ceci pour des séquences autres que des chaînes de caractères ? R : Oui, ces méthodes fonctionnent pour toutes les séquences comparables (listes, tableaux, etc.) qui prennent en charge l’indexation.
- Q : Qu’en est-il de la recherche de la longueur *seulement* ? R : Modifiez le code pour ne renvoyer que `dp[m][n]` dans l’approche de programmation dynamique ou le résultat de l’appel récursif final dans l’approche récursive.
- Q : Existe-t-il d’autres algorithmes ? R : Oui, mais la programmation dynamique et la mémorisation sont parmi les plus efficaces pour les cas généraux.