Diss. (sammanfattning) Uppsala : Uppsala universitet, 2009.

Relatively little is known about the evolutionary histories of most classes of non-protein coding RNAs. Here we consider Y RNAs, a relatively rarely studied group of related pol-III transcripts. A single cluster of functional genes is preserved throughout tetrapod evolution, which however exhibits clade-specific tandem duplications, gene-losses, and rearrangements.

My dissertation explores several aspects of the relationship between morphological and molecular evolution in amoeboid lineages: Chapter 1 - General Introduction: This chapter provides an overview of the most pressing issues in Amoebozoa phylogeny that are dealt with in the remainder of the thesis Chapter 2 - Reducing the impact of PCR-mediated recombination in molecular evolution and environmental studies using a new generation high fidelity DNA polymerase: This chapter addresses the methodological difficulty in the study of large gene families, the generation of artifactual sequences by recombination during PCR. Chapter 3 - Evolution of the actin gene family in testate lobose amoebae (Arcellinida) is characterized by two distinct clades of paralogs and recent independent expansions: This chapter explores intriging patterns of evolution in the actin gene families of testate amoebae. Chapter 4 - Comprehensive phylogenetic reconstruction of Amoebozoa based on concatenated analysis of SSU-rDNA and actin genes: A deep phylogenetic analyses of the Amoebozoa, enables exploration of well supported taxonomic units within the group. Chapter 5 - Interpreting the evolutionary history of the Tubulinea (Amoebozoa), in light of a multigene phylogeny: This chapter explores a more restrict taxonomic unit within the Amoebozoa - the Tubulinea - based on an expanded sample of genes and taxa. Chapter 6 - The chastity of amoebae: re-evaluating evidence for sex in amoeboid organisms: This chapter asks whether the null-hypothesis that amoebae are asexual is consistent with current phylogenetic evidence

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.

Darwin a révélé au monde que les espèces vivantes ne cessent jamais d'évoluer, mais les mécanismes moléculaires de cette évolution restent le sujet de recherches intenses. La biologie systémique propose que les relations entre génotype, environnement et phénotype soient sous-tendues par un ensemble de réseaux moléculaires dynamiques au sein de la cellule, mais l'organisation de ces réseaux demeure mystérieuse. En combinant des concepts établis en biologie évolutive et systémique avec la cartographie d'interactions protéiques et l'étude des méthodologies d'annotation de génomes, j'ai développé de nouvelles approches bioinformatiques qui ont en partie dévoilé la composition et l'organisation des systèmes cellulaires de trois organismes eucaryotes : la levure de boulanger, le nématode Caenorhabditis elegans et la plante Arabidopsis thaliana. L'analyse de ces systèmes m'a conduit à proposer des hypothèses sur les principes évolutifs des systèmes biologiques. En premier lieu, je propose une théorie selon laquelle la traduction fortuite de régions intergéniques produirait des peptides sur lesquels la sélection naturelle agirait pour aboutir occasionnellement à la création de protéines de novo. De plus, je montre que l'évolution de protéines apparues par duplication de gènes est corrélée avec celle de leurs profils d'interactions. Enfin, j'ai mis en évidence des signatures de la co-évolution ancestrale hôte-pathogène dans l'organisation topologique du réseau d'interactions entre protéines de l'hôte. Mes travaux confortent l'hypothèse que les systèmes moléculaires évoluent, eux aussi, de manière darwinienne.

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.

No description available.

Le but de cette thèse est d'étudier la distribution des tailles des répétitions au sein d'un même génome, ainsi que la distribution des tailles des appariements obtenus en comparant différents génomes. Ces distributions présentent d'importantes déviations par rapport aux prédictions des modèles probabilistes existants. Étonnamment, les déviations observées sont distribuées selon une loi de puissance. Afin d'étudier ce phénomène, nous avons développé des modèles mathématiques prenant en compte des mécanismes évolutifs plus complexes, et qui expliquent les distributions observées. Nous avons aussi implémenté des modèles d'évolution de séquences in silico générant des séquences ayant les mêmes propriétés que les génomes étudiés. Enfin, nous avons montré que nos modèles permettent de tester la qualité des génomes récemment séquencés, et de mettre en évidence la prévalence de certains mécanismes évolutifs dans les génomes eucaryotes. / In this thesis, we study the length distribution of maximal exact matches within and between eukaryotic genomes. These distributions strongly deviate from what one could expect from simple probabilistic models and, surprisingly, present a power-law behavior. To analyze these deviations, we develop mathematical frameworks taking into account complex mechanisms and that reproduce the observed deviations. We also implemented in silico sequence evolution models that reproduce these behaviors. Finally, we show that we can use our framework to assess the quality of sequences of recently sequenced genomes and to highlight the importance of unexpected biological mechanisms in eukaryotic genomes.

De la bactérie à l'homme, dispersées ou en tandem, les répétitions peuvent représenter jusqu'à 90 % de la séquence génomique. Malgré leur impact sur la plasticité et l'évolution des génomes eucaryotes, leurs mécanismes de formation sont encore très spéculatifs. L'insertion continue de nouvelles répétitions devrait conduire à une augmentation constante de la taille des génomes. Or, il ne semble pas que ce soit le cas. Y a t-il régulation de la taille des génomes? Le processus de régulation est-il le même dans l'euchromatine et l'hétérochromatine? Afin d'étudier la dynamique des répétitions, j'ai développé un ensemble de programmes informatiques pour la détection des duplications segmentaires (DS) et des répétitions en tandem (RT). A partir des caractéristiques des DS détectées chez Drosophila melanogaster, j'ai proposé un modèle de formation des DS, basé sur un modèle de recombinaison homologue non-allélique. J'ai également identifié les traces de l'implication des éléments transposables (ET) dans ce processus. Afin de caractériser la relation existante entre les répétitions et la structure de la chromatine, j'ai ensuite réalisé une analyse comparative de la dynamique des répétitions euchromatiques et hétérochromatiques. Pour ce travail, nous avons choisi comme modèle d'étude Arabidopsis thaliana. La construction d'arbres phylogénétiques des séquences répétées m'a permis de dater les répétitions. Nous suggérons ainsi une propagation par « vague » des ET. J'ai ensuite estimé les forces d'élimination des copies d'ET. Nos résultats suggèrent que dans l'euchromatine, la pression de sélection due aux gènes induit l'élimination des répétitions. Dans l'hétérochromatine, la faible densité en gènes permet de maintenir une forte densité en ET. Pourtant, les estimations du taux de perte en ADN, prédisent un turnover aussi rapide dans l'euchromatine que dans l'hétérochromatine. Afin de contre-balancer l'insertion des ET dans l'hétérochromatine, nous pouvons invoquer la recombinaison homologue non-allélique.

Lacking experimental data, protein function is often predicted from evolutionary and protein structure theory. Under the 'domain grammar' hypothesis the function of a protein follows from the domains it encodes. Under the 'orthology conjecture', orthologs, related through species formation, are expected to be more functionally similar than paralogs, which are homologs in the same or different species descended from a gene duplication event. However, these assumptions have not thus far been systematically evaluated. To test the 'domain grammar' hypothesis, we built models for predicting function from the domain combinations present in a protein, and demonstrated that multi-domain combinations imply functions that the individual domains do not. We also developed a novel gene-tree based method for reconstructing the evolutionary histories of domain architectures, to search for cases of architectures that have arisen multiple times in parallel, and found this to be more common than previously reported. To test the 'orthology conjecture', we first benchmarked methods for homology inference under the obfuscating influence of low-complexity regions, in order to improve the InParanoid orthology inference algorithm. InParanoid was then used to test the relative conservation of functionally relevant properties between orthologs and paralogs at various evolutionary distances, including intron positions, domain architectures, and Gene Ontology functional annotations. We found an increased conservation of domain architectures in orthologs relative to paralogs, in support of the 'orthology conjecture' and the 'domain grammar' hypotheses acting in tandem. However, equivalent analysis of Gene Ontology functional conservation yielded spurious results, which may be an artifact of species-specific annotation biases in functional annotation databases. I discuss possible ways of circumventing this bias so the 'orthology conjecture' can be tested more conclusively. / At the time of the doctoral defense, the following paper was unpublished and had a status as follows: Paper 6: Epub ahead of print.