Detecter des similarites et des homologies entre proteines est une etape cruciale du processus d'annotation des genomes. Afin de detecter des homologies, les alignements de sequences, globaux ou locaux, sont couramment utilises. Neanmoins, dans la "zone d'ombre," nous devons utiliser les methodes de reconnaissance de repliements. Dans ce domaine, le probleme du "Protein Threading" (PTP) utilise des parametres paires pour aligner globalement une sequence de proteine avec une structure de proteine. A notre connaissance, il n'existe pas de methode d'alignement local utilisant des parametres paires. A partir du PTP, nous proposons cinq modelisations mathematiques de ces alignements locaux qui ont ete implementees et testees grace au logiciel CPLEX 10.0. Nous avons ensuite developpe un algorithme dedie permettant de resoudre un de ces modeles. Cet algorithme utilise des techniques connues en recherche operationnelle: la separation-evaluation, la descente de sous-gradient et la relaxation lagrangienne. Bien que les alignements locaux soient d'une plus grande complexite, nous montrons qu'ils sont realisables et qu'ils ameliorent la qualite des alignements."