Combinatoire and Bio-informatique : Comparaison de structures d'ARN et calcul de distances intergénomiques

摘要: Nous presentons un ensemble de resultats concernant deux types problemes biologiques: (1) la comparaison structures molecules d'ARN et (2) le calcul distances intergenomiques en presence genes dupliques. Dans ce manuscrit, nous determinons complexite algorithmique certains lies soit a (distance d'edition, probleme APS, recherche motifs 2-intervalles, design d'ARN), aux rearrangements genomiques (distances breakpoints d'intervalles conserves). \\ L'approche adoptee pour l'ensemble ces ete determiner, si possible, des algorithmes exacts rapides repondants poses. Pour tout lequel cela ne semblait pas avons essaye prouver qu'il peut etre resolu fa\ccon rapide. faire, demontrons que question est algorithmiquement difficile. Enfin, cas echeant, poursuivons l'etude proposant, essentiellement, trois resultats: Approximation, Complexite parametree, (3) Heuristique. utilisons, dans notions d'optimisation combinatoire, mathematique, theorie graphes d'algorithmique.