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

2011

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 …