Identification of signatures of positive selection has long been a major issue for understanding the unique features of any given species. However, only a fraction of human genes have been interrogated. Genes within segmental duplications are usually omitted due to the limitations of draft genome assemblies and the methodological reliance on accurate gene trees. In this work, we show the feasibility of a new method that does not need accurate gene trees or individual high-quality assemblies. We applied the concept to study exon evolution in the human genome, identifying 74 exons with evidence for rapid coding sequence evolution during human and Old World monkey evolution. Our results suggest abundant accelerated coding sequence evolution within duplicated regions of the genome and provide a more comprehensive view of the role of selection on the human genome. / La identificación de señales debidas a la acción de la selección positiva es de gran relevancia para desvelar características únicas de las especies. A pesar de ello, solo una fracción de genes humanos han sido analizados. Los genes incluidos en duplicaciones segmentarias son normalmente ignorados debido a limitaciones impuestas por la naturaleza preliminar de los genomas distintos al humano, así como por la dependencia en adecuados árboles filogenéticos. En este proyecto, demostramos la viabilidad de un nuevo método que no necesita árboles filogenéticos correctos ni ensamblajes de genomas de alta calidad. Hemos aplicado el concepto al genoma humano y hemos identificado 74 exones que muestran evidencia de haber evolucionado más rápidamente desde la separación de los humanos y los monos del viejo mundo. Nuestros resultados sugieren que ha habido abundante evolución acelerada dentro de las regiones duplicadas y ofrece una visión más esclarecedora del rol de la selección en la evolución del genoma humano.

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.

Bien que de nombreuses séquences génomiques soient maintenant connues, les mécanismes évolutifs qui déterminent la taille des génomes, et notamment leur part d’ADN non codant, sont encore débattus. Ainsi, alors que de nombreux mécanismes faisant grandir les génomes (prolifération d’éléments transposables, création de nouveaux gènes par duplication, ...) sont clairement identifiés, les mécanismes limitant la taille des génomes sont moins bien établis. La sélection darwinienne pourrait directement défavoriser les génomes les moins compacts, sous l’hypothèse qu’une grande quantité d’ADN à répliquer limite la vitesse de reproduction de l’organisme. Cette hypothèse étant cependant contredite par plusieurs jeux de données, d’autres mécanismes non sélectifs ont été proposés, comme la dérive génétique et/ou un biais mutationnel rendant les petites délétions d’ADN plus fréquentes que les petites insertions. Dans ce manuscrit, nous montrons à l’aide d’un modèle matriciel de population que la taille du génome peut aussi être limitée par la dynamique spontanée des duplications et des grandes délétions, qui tend à raccourcir les génomes même si les deux types de réarrangements se produisent à la même fréquence. En l’absence de sélection darwinienne, nous prouvons l’existence d’une distribution stationnaire pour la taille du génome même si les duplications sont deux fois plus fréquentes que les délétions. Pour tester si la sélection darwinienne peut contrecarrer cette dynamique spontanée, nous simulons numériquement le modèle en choisissant une fonction de fitness qui favorise directement les génomes contenant le plus de gènes, tout en conservant des duplications deux fois plus fréquentes que les délétions. Dans ce scénario où tout semblait pousser les génomes à grandir infiniment, la taille du génome reste pourtant bornée. Ainsi, notre étude révèle une nouvelle force susceptible de limiter la croissance des génomes. En mettant en évidence des comportements contre-intuitifs dans un modèle pourtant minimaliste, cette étude souligne aussi les limites de la simple « expérience de pensée » pour penser l’évolution. / Even though numerous genome sequences are now available, evolutionary mechanisms that determine genome size, notably their fraction of non-coding DNA, are still debated. In particular, although several mechanisms responsible for genome growth (proliferation of transposable elements, gene duplication and divergence, etc.) were clearly identified, mechanisms limiting the overall genome size remain unclear. Darwinian selection could directly disadvantage less compact genomes, under the hypothesis that a larger quantity of DNA could slow down the speed of reproduction of the organism. Because this hypothesis was proven wrong by several datasets, non selective mechanisms have been proposed, e.g. genetic drift and/or a mutational bias towards small DNA deletions compared to small DNA insertions. In this manuscript, we use a matrix model to show that genome size can also be limited by the spontaneous dynamics of duplications and large deletions, which tends to decrease genome size even if the two types of rearrangements occur at the same rate. In the absence of Darwinian selection, we prove the existence of a stationary distribution of genome size even if duplications are twice as frequent as large deletions. To test whether selection can overcome this spontaneous dynamics, we simulate our model numerically and choose a fitness function that directly favors genomes containing more genes, while keeping duplications twice as frequent as large deletions. In this scenario where, at first sight, everything seems to favor infinite genome growth, genome size remains nonetheless bounded. As a result, our study reveals a new pressure that could be responsible for limiting genome growth. By illustrating counter-intuitive behaviors in a minimal model, this study also underlines the limits of simple "thought experiments" to understand evolution.

Bien que de nombreuses séquences génomiques soient maintenant connues, les mécanismes évolutifs qui déterminent la taille des génomes, et notamment leur part d'ADN non codant, sont encore débattus. Ainsi, alors que de nombreux mécanismes faisant grandir les génomes (prolifération d'éléments transposables, création de nouveaux gènes par duplication, ...) sont clairement identifiés, les mécanismes limitant la taille des génomes sont moins bien établis. La sélection darwinienne pourrait directement défavoriser les génomes les moins compacts, sous l'hypothèse qu'une grande quantité d'ADN à répliquer limite la vitesse de reproduction de l'organisme. Cette hypothèse étant cependant contredite par plusieurs jeux de données, d'autres mécanismes non sélectifs ont été proposés, comme la dérive génétique et/ou un biais mutationnel rendant les petites délétions d'ADN plus fréquentes que les petites insertions. Dans ce manuscrit, nous montrons à l'aide d'un modèle matriciel de population que la taille du génome peut aussi être limitée par la dynamique spontanée des duplications et des grandes délétions, qui tend à raccourcir les génomes même si les deux types de ré- arrangements se produisent à la même fréquence. En l'absence de sélection darwinienne, nous prouvons l'existence d'une distribution stationnaire pour la taille du génome même si les duplications sont deux fois plus fréquentes que les délétions. Pour tester si la sélection darwinienne peut contrecarrer cette dynamique spontanée, nous simulons numériquement le modèle en choisissant une fonction de fitness qui favorise directement les génomes conte- nant le plus de gènes, tout en conservant des duplications deux fois plus fréquentes que les délétions. Dans ce scénario où tout semblait pousser les génomes à grandir infiniment, la taille du génome reste pourtant bornée. Ainsi, notre étude révèle une nouvelle force susceptible de limiter la croissance des génomes. En mettant en évidence des comporte- ments contre-intuitifs dans un modèle pourtant minimaliste, cette étude souligne aussi les limites de la simple " expérience de pensée " pour penser l'évolution. Nous proposons un modèle mathématique de l'évolution structurelle des génomes en met- tant l'accent sur l'influence des différents mécanismes de mutation. Il s'agit d'un modèle matriciel de population, à temps discret, avec un nombre infini d'états génomiques pos- sibles. La taille de population est infinie, ce qui élimine le phénomène de dérive génétique. Les mutations prises en compte sont les mutations ponctuelles, les petites insertions et délétions, mais aussi les réarrangements chromosomiques induits par la recombinaison ectopique de l'ADN, comme les inversions, les translocations, les grandes délétions et les duplications. Nous supposons par commodité que la taille des segments réarrangés suit une loi uniforme, mais le principal résultat analytique est ensuite généralisé à d'autres dis- tributions. Les mutations étant susceptibles de changer le nombre de gènes et la quantité d'ADN intergénique, le génome est libre de varier en taille et en compacité, ce qui nous permet d'étudier l'influence des taux de mutation sur la structure génomique à l'équilibre. Dans la première partie de la thèse, nous proposons une analyse mathématique dans le cas où il n'y a pas de sélection, c'est-à-dire lorsque la probabilité de reproduction est identique quelle que soit la structure du génome. En utilisant le théorème de Doeblin, nous montrons qu'une distribution stationnaire existe pour la taille du génome si le taux de duplications par base et par génération n'excède pas 2.58 fois le taux de grandes délétions. En effet, sous les hypothèses du modèle, ces deux types de mutation déterminent la dynamique spontanée du génome, alors que les petites insertions et petites délétions n'ont que très peu d'impact. De plus, même si les tailles des duplications et des grandes délétions sont distribuées de façon parfaitement symétriques, leur effet conjoint n'est, lui, pas symétrique et les délétions l'emportent sur les duplications. Ainsi, si les tailles de délétions et de duplications sont distribuées uniformément, il faut, en moyenne, plus de 2.58 duplications pour compenser une grande délétion. Il faut donc que le taux de duplications soit quasiment trois fois supérieur au taux de délétions pour que la taille des génomes croisse à l'infini. L'impact des grandes délétions est tel que, sous les hypothèses du modèle, ce dernier résultat reste valide même en présence d'un mécanisme de sélection favorisant directement l'ajout de nouveaux gènes. Même si un tel mécanisme sélectif devrait intuitivement pousser les génomes à grandir infiniment, en réalité, l'influence des délétions va rapidement limiter leur accroissement. En résumé, l'étude analytique prédit que les grands réarrangements délimitent un ensemble de tailles stables dans lesquelles les génomes peuvent évoluer, la sélection influençant la taille précise à l'équilibre parmi cet ensemble de tailles stables. Dans la deuxième partie de la thèse, nous implémentons le modèle numériquement afin de pouvoir simuler l'évolution de la taille du génome en présence de sélection. En choisissant une fonction de fitness non bornée et strictement croissante avec le nombre de gènes dans le génome, nous testons le comportement du modèle dans des conditions extrêmes, poussant les génomes à croître indéfiniment. Pourtant, dans ces conditions, le modèle numérique confirme que la taille des génomes est essentiellement contrôlée par les taux de duplications et de grandes délétions. De plus, cette limite concerne la taille totale du génome et s'applique donc aussi bien au codant qu'au non codant. Nous retrouvons en particulier le seuil de 2.58 duplications pour une délétion en deçà duquel la taille des génomes reste finie, comme prévu analytiquement. Le modèle numérique montre même que, dans certaines conditions, la taille moyenne des génomes diminue lorsque le taux de duplications augmente, un phénomène surprenant lié à l'instabilité structurelle des grands génomes. De façon similaire, augmenter l'avantage sélectif des grands génomes peut paradoxalement faire rétrécir les génomes en moyenne. Enfin, nous montrons que si les petites insertions et délétions, les inversions et les translocations ont un effet limité sur la taille du génome, ils influencent très largement la proportion d'ADN non codant.

Genome composition and architecture is shaped by two types of processes: those that introduce heritable changes (mutagenesis) and those that determine the fate of such changes in the populations (genetic drift and selection). Chemical and biological properties of mutagenesis determines the frequencies at which different type of mutations occur, which, in turn, determines their rates of fixation by drift and affects the spectrum of mutations available for selection to operate on. As the result, genomes of living organisms carry many signatures mutagenesis.

En aquest treball es presenta l'evolució molecular i estudi funcional de gens localitzats a les duplicacions segmentàries de la regió 7q11.23, implicada en la Síndrome de Williams-Beuren (SWB). S'ha datat l'aparició d'aquestes duplicacions en els últims 25 milions d'anys d'evolució i s'ha proposat un model evolutiu amb reordenaments específics i mecanismes de generació. Correlacions clínico-moleculars en els pacients amb la SWB han permès determinar que l'haploinsuficiència per NCF1, un gen localitzat a les duplicacions, és un factor protector per hipertensió. S'ha proposat un model patogènic per la hipertensió, implicant l'oxidasa NAD(P)H i estrès oxidatiu, suggerint que noves estratègies terapèutiques podrien ser utilitzades. A més, s'ha caracteritzat parcialment la funció de GTF2IRD2, un altre gen de les duplicacions. GTF2IRD2 interacciona amb altres factors de transcripció relacionats, té una localització subcel·lular variable i no s'uneix a ADN. Aquests resultats contribueixen a conèixer millor els mecanismes mutacionals i patogènics de la SWB. / This work presents the molecular evolution along with the functional analysis of the genes located in the segmental duplications flanking the 7q11.23 region, involved in Williams-Beuren syndrome (WBS). The generation of the segmental duplications has been dated to the last 25 million years of evolution and an evolutionary model with specific rearrangements and mechanisms has been proposed. Clinical-molecular correlations in WBS patients have allowed to determine that haploinsufficiency at NCF1, a gene located in the duplications, is a protective factor for hypertension. A pathogenic model for hypertension has been proposed, implicating NAD(P)H oxidase and oxidative stress, and suggesting that novel therapeutic strategies could be used. In addition, the functional characterization of another gene of the duplications, GTF2IRD2, has been partially achieved. GTF2IRD2 has been shown to interact with other related transcription factors, to display variable subcellular localization and to lack DNA binding properties. These results contribute to a better knowledge of the mutational and pathogenic mechanisms of the WBS.