Cette thèse porte sur des classes d'objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l'intérieur du génome : la duplication et l'inversion. Nous étudions d'une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l'identité est la classe de permutations qui évite les permutations alternées de longueur 2^p+1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l'identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l'identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d'autres classes proches. La restriction de la relation d'ordre < induite par le code de Gray réfléchi à l'ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d'ordre < restreinte à l'ensemble des compositions bornées d'un intervalle fournit encore un code de Gray. L'ensemble des n compositions bornées d'un intervalle généralise simultanément l'ensemble produit et l'ensemble des compositions d'un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d'un entier à l'aide d'une unique relation d'ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi.

Étude de divers problèmes lies aux graphes de Hamming

Le cube de Fibonacci est un sous-graphe isométrique de l'hyper- cube ayant un nombre de Fibonacci de sommets. Le cube de Fibonacci a été initialement introduit par W-J. Hsu comme un réseau d'interconnexion et, comme l'hypercube, il a des propriétés topologiques très attractives, mais avec une croissance plus modérée. Parmi ces propriétés, nous discutons de l'hamiltonicité dans le cube de Fibonacci et aussi dans le cube de Lucas qui est obtenu à partir du cube de Fibonacci en supprimant toutes les chaînes qui commencent et nissent avec 1. Nous trouvons également le nombre de som- mets des cubes de Fibonacci et Lucas ayant une certaine excentricité. En n, nous présentons une étude de deux cubes du point de vue de la domination et du 2-packing.

Le cube de Fibonacci est un sous-graphe isométrique de l'hyper- cube ayant un nombre de Fibonacci de sommets. Le cube de Fibonacci a été initialement introduit par W-J. Hsu comme un réseau d'interconnexion et, comme l'hypercube, il a des propriétés topologiques très attractives, mais avec une croissance plus modérée. Parmi ces propriétés, nous discutons de l'hamiltonicité dans le cube de Fibonacci et aussi dans le cube de Lucas qui est obtenu à partir du cube de Fibonacci en supprimant toutes les chaînes qui commencent et nissent avec 1. Nous trouvons également le nombre de som- mets des cubes de Fibonacci et Lucas ayant une certaine excentricité. En n, nous présentons une étude de deux cubes du point de vue de la domination et du 2-packing. / The Fibonacci cube is an isometric subgraph of the hypercube having a Fibonacci number of vertices. The Fibonacci cube was originally proposed by W-J. Hsu as an interconnection network and like the hypercube it has very attractive topological properties but with a more moderated growth. Among these properties, we discuss the hamiltonicity in the Fibonacci cube and also in the Lucas cube which is obtained by removing all the strings that begin and end with 1 from the Fibonacci cube. We give also the eccentricity sequences of the Fibonacci and the Lucas cubes. Finally, we present a study of both cubes from the domination and the 2-packing points of view.

Cette thèse porte sur des classes d’objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l’intérieur du génome : la duplication et l’inversion. Nous étudions d’une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l’identité est la classe de permutations qui évite les permutations alternées de longueur 2p + 1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l’identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l’identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d’autres classes proches. La restriction de la relation d’ordre < induite par le code de Gray réfléchi à l’ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d’ordre < restreinte à l’ensemble des compositions bornées d’un intervalle fournit encore un code de Gray. L’ensemble des ncompositions bornées d’un intervalle généralise simultanément l’ensemble produit et l’ensemble des compositions d’un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d’un entier à l’aide d’une unique relation d’ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi. / This thesis considers classes of combinatorial objects that model data in bioinformatics. We have studied two methods of mutation of genes within the genome : duplication and inversion. At first,we study the problem of the whole mirror duplication-random lossmodel in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this method after p duplications from the identity is the class of permutations avoiding alternating permutations of length 2p + 1.We also enumerate the number of duplications that are necessary and sufficient to obtain any permutation of length n from the identity. We also suggest two efficient algorithms to reconstruct two different paths between the identity and a specified permutation. Finally,we give related results on other classes nearby. The restriction of the order relation < induced by the reflected Gray code for the sets of compositions and bounded compositions gives new Gray codes for these sets. The order relation < restricted to the set of bounded compositions of an interval also yields a Gray code. The set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so < puts under a single roof all theseGray codes.We re-expressWalsh’s and Knuth’sGray codes for (bounded) compositions of an integer in terms of a unique order relation, and so Walsh’s Gray code becomes a sublist of Knuth’s code, which in turn is a sublist of the Reflected Gray Code.

Cette thèse porte sur des classes d'objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l'intérieur du génome : la duplication et l'inversion. Nous étudions d'une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l'identité est la classe de permutations qui évite les permutations alternées de longueur 2p + 1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l'identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l'identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d'autres classes proches. La restriction de la relation d'ordre < induite par le code de Gray réfléchi à l'ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d'ordre < restreinte à l'ensemble des compositions bornées d'un intervalle fournit encore un code de Gray. L'ensemble des ncompositions bornées d'un intervalle généralise simultanément l'ensemble produit et l'ensemble des compositions d'un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d'un entier à l'aide d'une unique relation d'ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi.