|
Chaîne la plus proche En informatique théorique, et notamment en algorithmique du texte, la chaîne la plus proche (en anglais closest string) d'un ensemble de chaînes de caractères données est une chaîne à distance minimale des chaînes, selon la distance de Hamming. La recherche de la chaîne la plus proche est un problème algorithmique NP-difficile[1]. ExemplePour les cinq chaînes
la chaîne la plus proche est
Elle est à distance 2 des chaînes données. Les coïncidences sont marquées en rouge :
Définition formelleÉtant donné n chaînes s1, ..., sn de même longueur m, le problème de la chaîne la plus proche consiste à déterminer une nouvelle chaîne s de longueur m telle que d(s,si) ≤ k pour tout i, où d est la distance de Hamming, et où k est aussi petit que possible[2]. Le problème de décision correspondant, qui est NP-complet, prend également l'entier k en entrée et demande s'il existe une chaîne qui est à distance de Hamming au plus k de toutes les chaînes données[1]. Le problème est NP-difficile même sur un alphabet binaire[3]. MotivationEn bio-informatique, le problème de la chaîne la plus proche est un aspect très étudié du problème de détection de signaux dans les ADN. Le problème a aussi des applications en théorie des codes (problème du rayon minimal)[3]. Le problème de la sous-chaîne la plus proche formalise des applications biologiques dans la recherche de régions conservées, l'identification de cibles de médicaments génétiques et la génération de sondes génétiques en biologie moléculaire. En algorithmique du texte, c'est un problème de combinatoire de chaînes de caractères[4]. Ce problème de chaînes et d'autres qui se posent dans diverses applications allant de l'exploration de texte à l'analyse de séquence biologique sont souvent NP-difficiles. Ceci motive la recherche de cas spéciaux traitables (fixed-parameter tractable) de ces problèmes. Ceci a un sens dans les cas où il y a plusieurs paramètres naturellement associés, comme la taille de l’alphabet, le nombre de chaînes, ou un majorant sur la distance. Le problème de la chaîne la plus proche peut être vu géométriquement comme une instance du problème du 1-centre avec comme distance la distance de Hamming. Simplifications et réduction de donnéesDes instances du problème de la chaîne la plus proche peuvent contenir des informations qui ne sont pas significatives pour le problème ou, autrement dit, qui ne contribuent pas à la difficulté du problème. Par exemple, si certaines chaînes contiennent le caractère a, et qu'aucune ne contient le caractère z, remplacer tous les a par des z donne une instance essentiellement équivalente, c'est-à-dire qu'à partir d'une solution de l'instance modifiée, la solution originale peut être facilement restaurée et vice-versa. Normalisation de l'entréeEn écrivant les chaînes d'entrée les unes sous les autres, on obtient une matrice. Certains types de lignes ont essentiellement les mêmes influences sur la solution. Par exemple, remplacer une colonne qui a les entrées (a, a, b) par une colonne (x, x, y) peut mener à une chaîne solution différente, mais ne peut affecter la solvabilité, car les deux colonnes expriment la même structure, où les deux premières entrées sont égales, mais différentes de la troisième. Une instance d'entrée peut être normalisée en remplaçant, dans chaque colonne, le caractère qui se produit le plus souvent par a, le caractère qui se produit en deuxième par b, et ainsi de suite. Étant donné une solution de l'instance normalisée, l'instance d'origine peut être retrouvée en remplaçant les caractères de la solution par leur version d'origine dans chaque colonne. L'ordre des colonnes ne contribue pas à la difficulté du problème. Cela signifie que si on permute les chaînes d'entrée selon une certaine permutation π et si on obtient une chaîne solution s à cette instance modifiée, alors π−1(s) est une solution de l'instance d'origine. ExempleOn considère une instance formée des trois mots uvwx, xuwv, et xvwu (voir schéma en haut). Sous forme de matrice, on obtient la table suivante :
Dans la première colonne (u, x, x), c'est le symbole x qui apparaît le plus souvent (2 fois) ; on le remplace par a et le caractère u par b, ce qui donne la nouvelle première colonne (b, a, a). La deuxième colonne (v, u, v) est remplacée, par la même stratégie, par (a, b, a). En procédant de même pour les autres colonnes, on aboutit à
Réduction de données par normalisationLa normalisation a pour conséquence que la taille de l'alphabet est au plus égale au nombre de chaînes d'entrées. Ceci peut s'avérer utile pour des algorithmes dont le temps de calcul dépend de la taille de l’alphabet. ApproximationLi et al. ont décrit un schéma d'approximation en temps polynomial[5], mais qui est inutilisable en pratique à cause de grandes constantes cachées. Complexité paramétréeLe problème de la chaîne la plus proche peut être résolu en O(nL+nd × dd), où n est le nombre de chaînes données en entrée, L est la longueur commune de toutes les chaînes et d est la distance désirée de la solution à toutes les chaînes données[6]. Il est ainsi dans la classe de complexité paramétrée FPT (fixed-parameter tractable). Relations avec d'autres problèmesLe problème de la chaîne la plus proche est un cas particulier du problème plus général de la sous-chaine la plus proche qui est strictement plus difficile . Alors que le problème de la chaîne la plus proche est fixed parameter tractable de différentes manières, le problème de la sous-chaine W[1]-difficile par rapport à ces paramètres. La kernelisation de ces problèmes et de problème voisin a fait l'objet d'une étude détaillée qui montre que soit on peut obtenir un noyau polynomial soit qu'un tel noyau ne peut être obtenu sous les hypothèses usuelles en théorie de la complexité, et notamment la Exponential Time Hypothesis (ETH)[7]. Ces problèmes sont de trouver une sous-structure ou une superstructure commune à ensemble de chaînes donné. Les problèmes les plus fondamentaux sont la plus longue sous-séquence commune, la plus courte super-séquence commune et la plus petite séquence commune. En outre, il y a le problème plus général de l'alignement de séquences multiples, qui est d'une importance capitale dans l'analyse des séquences biologiques[4]. Notes et références
Articles liés |
