Algorithme du plus long palindrome

Récemment un étudiant m'a demandé de l'aider à la compréhension d'un problème d'algorithme qui peut être résumé par l'énoncé suivant: « En bio-informatique, le séquençage de l'ADN est codé par une suite finie composée de 4 caractères A,T,G,C. A partir d'une telle séquence déterminer la taille de la plus longue sous-séquence qui soit identique lorsque la lecture est faite de gauche à droite et de droite à gauche »

Trouver le modèle
A mon avis pour mieux appréhender un problème algorithmique, il vraiment utile de le reformuler en essayant de réduire le problème à un modèle générique. Cette démarche consiste à redéfinir le problème en termes plus formels pour s'intéresser à la nature même du problème. Ainsi je peux reformuler la question de manière suivante:

« Etant donné un ensemble ordonné, non vide et composé de caractères d'un alphabet quelconque, déterminer la taille du plus grand sous ensemble muni du même ordre et dont les éléments consécutifs forment le plus long palindrome »

Engage le jeu que je le gagne
Un palindrome est un mot ou un groupe de mots qui peut se lire dans les deux sens tout préservant l'ordre des lettres, par exemple « Et Luc lamina l'animal culte ». La définition par récurrence d'un palindrome peut être donnée non formellement de la façon suivante:

1. Un mot d'un caractère est un palindrome.
2. Un mot de plus d'un caractère est un palindrome si et seulement si son premier caractère est égal à son dernier caractère et que le reste du mot, sans le premier et le dernier caractère, est aussi un palindrome.

Avec une telle définition il devient aisé d'écrire un algorithme récursif déterminant si un mot quelconque est un palindrome ou pas. Ci-dessous le code en Python:

def est_un_palindrome(sequence):
if len(sequence) <= 1: # mot vide et d'un caractère est un palindrome
return True
# un mot w = {a0,...,an} est un palindrome ssi a0 = an et w' = {a1,...,an-1} est un palindrome
if sequence[0] == sequence[-1] and est_un_palindrome(sequence[1:-1]):
return True
return False

L'approche naïve
L'approche élémentaire pour trouver le plus long sous-ensemble qui soit palindrome serait de considérer toutes les sous-séquences de la séquence en entrée. Donc dans un premier temps, il faut construire l'ensemble des parties de la séquence.

def ensemble_des_parties(sequence):
if len(sequence) == 1:
return [sequence] # une sequence d'un caractère n'a que lui comme sous-sequence
# une sous sequence est composée du premier caractère seul, de
return [sequence[0]] + [sequence[0] + seq for seq in compositions(sequence[1:])] + compositions(sequence[1:])

Pour finir, il ne reste qu'à parcourir l'ensemble des parties de la séquence et déterminer avec la fonction est_un_palindrome et len quel est le plus long palindrome.