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