6533b827fe1ef96bd1285836

RESEARCH PRODUCT

Etudes d'objets combinatoires : applications à la bio-informatique

subject

description

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.