Alignement, séquence consensus, recherche de similarités : complexité et approximabilité

Dans ce mémoire, nous étudions la complexité algorithmique de plusieurs problèmes combinatoiresconcernant la comparaison de séquences biologiques. Nous nous pla¸cons successivement du point de vue dechacune des trois principales théories de la complexité algorithmique : la NP-complétude, l'approximabilitéet la complexité paramétrique.Dans un premier temps, nous considérons plusieurs formes du problème de l'extraction des motifs communsà un ensemble de séquences donné. Les motifs communs permettent, en pratique, de classifier les protéinesgrâce à leur structure primaire, par exemple en fabriquant des séquences consensus.En particulier, le problème de la médiane (resp. du centre) pour la distance d'édition consiste à rechercherune séquence consensus minimisant la somme (resp. le maximum) des distances d'édition la séparant dechacune des séquences prises en entrée. Nous affinons les résultats connus sur la difficulté de chacun de cesdeux problèmes : nous montrons, par exemple, qu'ils sont tous les deux W[1]-difficiles lorsqu'on lesparamétrise par le nombre des séquences étudiées et ce, même dans le cas d'un alphabet binaire. Nousconsidérons également le problème de la plus longue sous-séquence commune. Ce problème a étéexhaustivement étudié dans sa forme usuelle. Or, on trouve dans la nature des séquences d'ADN et d'ARNcirculaires qu'il est utile de comparer. Dans ce mémoire, nous menons à bien la première étude du problèmede la plus longue sous-séquence commune à plusieurs séquences circulaires et/ou non orientées.Dans un second temps, nous considérons plusieurs problèmes liés à la recherche de similarités approchéesentre séquences biologiques. C'est dans ce domaine que l'application de l'informatique à la biologiemoléculaire a été la plus fructueuse. En pratique les similarités permettent de déterminer les propriétés desmolécules nouvellement séquencées à l'aide de celles des séquences déjà annotées. En effet, une similarité enséquence entraîne généralement une similarité en structure ou en fonction.La plupart des nombreux logiciels dédiés à la détection de similarités locales, mettent en oeuvre des filtresheuristiques : deux portions de séquences ne possédant pas certains motifs spécifiques en commun sontconsidérées d'emblée comme dissimilaires. Le choix des motifs conditionne la sensibilité et la sélectivité dufiltre associé. Dans ce mémoire nous considérons un certain type de motifs appelé graine. Il s'agit en fait desous-chaînes à trous.Nous étudions plusieurs problèmes algorithmiques liés à la conception de bonnes graines. En particulier,nous montrons que le problème suivant est NP-difficile : étant donnés deux entiers naturels k, m et unegraine, décider si le filtre associé est sans perte lorsque l'on restreint la notion de similarité aux paires demots de même longueur m, séparés par une distance de Hamming au plus k. Notons que plusieursalgorithmes exponentiels ont été proposés pour des généralisations de ce problème