Alignement Textuel Monolingue Avec Recherche de D placements

Ce travail r pond une probl matique suscit e par la critique g n tique. Cette discipline tudie la gen se des oeuvres litt raires gr ce aux brouillons d' crivains en recherchant, entre autres, les d placements entre deux versions d'un m me texte. Ceci nous a amen d finir la probl matique de l'alignement textuel monolingue avec recherche de d placements. D'un point de vue informatique, nous avons mis jour la n cessit de calculer un alignement entre deux textes de type distance d' dition avec recherche des d placements, ce qui est NP-difficile. Nous proposons une formalisation en un probl me d'optimisation combinatoire multiobjectif int grant un objectif syntaxique. Un algorithme d'alignement de s quences par fragments est propos . En bioinformatique, cette technique permet de traiter des g nomes de mammif res. Notre algorithme est bas sur la coordination de la r solution des recouvrements entre occurrences d'une r p tition. Il r sout le probl me avec une complexit efficace et passe l' chelle. Il est maintenant utilis par les g n ticiens du texte afin d' tudier les brouillons d' crivains.