Résumés
On séquence tout et on recommence.
Richard Christen UMR 6543 CNRS
Entre 2005 et 2007 sont apparues trois nouvelles génération de séquenceur d’ADN. 1,2 millions de séquences de 400-450 nt par jour (454) ou environ 100 millions de séquences (35 nt SOLiD, 100 nt Solexa) par semaine pour un coût de 8 000-15 000 $. Le prix d’une séquence a énormément baissé, le nombre de séquences est incroyable, mais l’avantage spectaculaire est qu’on peut maintenant se passer d’un clonage car le séquençage est massivement parallèle. ADN génomiques, ARN messagers, petits ARN, produits PCR,... on peut tout séquencer vite et pour pas cher. Un problème majeur est cependant que cette abondance de données n’est actuellement pas très bien gérée par les centres de dépôt publics (NCBI, EMBL, DDBJ) et que les ressources bioinformatiques dont disposent les laboratoires sont insuffisantes. En prenant principalement pour exemple la mesure de la biodiversité par séquençage des ARN ribosomiqes (prokaryotes ou eukaryotes) je tenterai de faire le point sur les études déj publiées, les avancées en cours et les problèmes existants.
Analyse de données métagenomiques de communautés virales lacustres
Simon Roux Laboratoire Microorganismes : Génome et Environnement. Université Blaise Pascal, Clermont-Ferrand
Les virus sont les entités biologiques les plus abondantes de la biosphère et jouent un rôle primordial dans les écosystèmes, notamment aquatiques, en intervenant dans les cycles biogéochimiques, la régulation des populations bactériennes, et le transfert d’information génétique. Le développement récent des techniques de métagénomique, consistant en un séquençage massif de fragments d’ADN issus d’un prélèvement, permet une nouvelle approche des communautés virales de l’environnement. Dans ce contexte, la création et l’analyse de deux viromes (métagénome sur la fraction virale) issus de deux lacs d’eau douces (le lac Pavin et le lac du Bourget) ont été réalisées au sein de notre équipe. Deux groupes viraux principaux ont pu être mis en évidence : les Caudovirales, ou bacteriophages queue (génomes ADN double brin entre 20 et 500 Kbp) et les virus ADN simple brin (génomes compris entre 2 et 15 Kpb). Pour chacun de ces groupes, de nouveaux clades ont été détectés par l’observation d’arbres phylogénétiques. Ces observations ont été complétées par l’assemblage des séquences métagénomiques, qui a permis une étude plus précise de ces nouveaux groupes (composition en gène, synthénie, FFP pour les génomes circulaires de petits virus). En parallèle, une comparaison de la diversité virale globale a été réalisée partir d’un ensemble de viromes déj publiés. D’une part, une comparaison directe des séquences témoigne d’une similarité génétique entre les viromes issus des mêmes types d’environnement, indépendamment de la distance géographique entre les lieux d’échantillonnage. D’autre part, une comparaison de la richesse en gène des différents viromes semble indiquer que cette richesse est liée la richesse en gène des communautés d’hôtes potentiels. La taille des fragments et la profondeur de séquençage (700.000 fragments de 450 pb par virome, technologie GS-FLX TITANIUM) a permis de réaliser des analyses (phylogénies, assemblage, etc...) impossibles pour les viromes publics déj séquencés (100 200pb). Ainsi, les travaux exposés portent la fois sur les résultats de l’analyse des deux viromes lacustres ainsi que sur les outils et procédures bioinformatiques développées spécifiquement pour ce ´ nouveau ª type de données, appelé se généraliser.
Adaptation to Environmental Temperature is a Major Determinant of Molecular Evolutionary Rates in Archaea
Mathieu Groussin Laboratoire de Biométrie et Biologie Evolutive, LBBE, Université Lyon 1
Methods to infer the ancestral conditions of life are commonly based on geological and palaeontological analyses. Recently, several studies focused on the use of genomes to gain information about past ecological conditions. Many used the fact that the G+C and amino- acid contents of bacterial and archaeal rDNA genes and proteins, respectively, are strongly influenced by the environmental temperature. The adaptation to optimal growth temperature (OGT) since the Last Universal Cellular Ancestor (LUCA) over the universal tree of life was examined and it was concluded that LUCA was likely to have been a mesophilic organism and that a parallel adaptation to high temperature occurred independently along the two lineages leading to the ancestors of Bacteria on one side and of Archaea+Eukarya on the other side. Here, we focus on Archaea to gain a precise view of the adaptation to OGT over time in this domain. It has been often proposed on the basis of indirect evidence that the last archaeal common ancestor was a hyperthermophilic organism. Moreover, many results showed the influence of environmental temperature on the evolutionary dynamics of archaeal genomes: thermophilic organisms generally display lower evolutionary rates than mesophiles. However, to our knowledge, no study tried to explain the differences of evolutionary rates for the entire archaeal domain and to investigate the evolution of substitution rates over time. A comprehensive archaeal phylogeny and a non‐homogeneous model of the molecular evolutionary process allowed us to estimate ancestral base and amino acid compositions and optimal growth temperatures at each internal node of the archaeal phylogenetic tree. The last archaeal common ancestor is predicted to have been hyperthermophilic and adaptations to cooler environments can be observed for extant mesophilic species. Furthermore, mesophilic species present both long branches and high variation of nucleotide and amino acid compositions since the last archaeal common ancestor. The increase of substitution rates observed in mesophilic lineages along all their branches can be interpreted as an ongoing adaptation to colder temperatures and to new metabolisms. We conclude that environmental temperature is a major factor that governs evolutionary rates in Archaea.
The small, slow and specialized CRISPR and anti-CRISPR of Escherichia and Salmonella.
Marie Touchon Microbial Evolutionary Genomics group, Institut Pasteur, CNRS URA2171
Prokaryotes thrive in spite of the vast number and diversity of their viruses. This partly results from the evolution of mechanisms to inactivate or silence the action of exogenous DNA. Among these, Clustered Regularly Interspaced Short Palindromic Repeats (CRISPR) are unique in providing adaptive immunity against elements with high local resemblance to genomes of previously infecting agents. Here, we analyze the CRISPR loci of 51 complete genomes of Escherichia and Salmonella. CRISPR are in two pairs of loci in Escherichia, one single pair in Salmonella, each pair showing a similar turnover rate, repeat sequence and putative linkage to a common set of cas genes. Yet, phylogeny shows that CRISPR and associated cas genes have different evolutionary histories, the latter being frequently exchanged or lost. In our set, one CRISPR pair seems specialized in plasmids often matching genes coding for the replication, conjugation and antirestriction machinery. Strikingly, this pair also matches the cognate cas genes in which case these genes are absent. The unexpectedly high conservation of this anti-CRISPR suggests selection to counteract the invasion of mobile elements containing functional CRISPR/cas systems. There are few spacers in most CRISPR, which rarely match genomes of known phages. Furthermore, we found that strains divergent less than 250 thousand years ago show virtually identical CRISPR. The lack of congruence between cas, CRISPR and the species phylogeny and the slow pace of CRISPR change make CRISPR poor epidemiological markers in enterobacteria. All these observations are at odds with the expectedly abundant and dynamic repertoire of spacers in an immune system aiming at protecting bacteria from phages. Since we observe purifying selection for the maintenance of CRISPR these results suggest that alternative evolutionary roles for CRISPR remain to be uncovered.
Horizontal gene transfer as a molecular clock
Gergely J Szollosi, Eric Tannier, Bastien Boussau and Vincent Daubin, LBBE, Villeurbanne
The phylogenetic histories of genes in a genome are not identical, but reflect individual histories of duplications, transfers and losses. As has become clear in the last two decades, persistent horizontal transfer has left a tangle of phylogenetic incongruence in its wake. However, the history of horizontal transfer events also contains a wealth of untapped evolutionary information. In particular, this history of gene transfer events records which lineages were concurrent and hence the relative time of their divergence. Here we use an explicit probabilistic model of duplication, transfer and loss (DTL) that views the phylogenetic histories of homologous gene families (i.e., gene trees) as independent samples generated by the processes of DTL. We demonstrate that it is possible to accurately infer the time order of divergence events and DTL rates by maximizing the likelihood of the forest of gene trees given the species tree. Based on a simplified version of the dynamic programing approach of Tofigh et al. [1,2] we developed a probabilistic DTL model that is capable of taking as its input gene trees from all homologous gene families of several dozen genomes while remaining tractable. To asses the robustness of our inference we use simulated datasets with realistic loss rates (inferred from phylogenetic profiles of bacterial and archaeal phyla) and consider different caveats of real datasets (such as rate variation, fragmentation of homologous gene families and transfer from unsampled species). We also present results on the reconstruction of the time order of major diversification events within cyanobacteria using a database of homologous gene families from complete genomes (HOGENOM). [1] Tofigh A, Sjˆstrand J, Sennblad B, Arbestad L and Lagergren J Detecting LGTs using a novel probabilistic model integrating duplications, LGTs, losses, rate variation,and sequence evolution in Tofigh A: Using Trees to Capture Reticulate Evolution. PhD Thesis, KTH, Stockholm (2009) [2] Doyon JP, Scornavacca C, Szollosi GJ, Ranwez V and Berry V An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications, and transfers submitted to Bioinformatics (2010)
MACSE: Alignement multiple de séquences codantes avec ruptures de cadre de lecture
Ranwez V., Harispe S., Delsuc F. & Douzery E. J. P. (1,2) (1) Université Montpellier 2 (2) CNRS & IRD, Institut des Sciences de l’Evolution (UMR 5554)
La majorité des programmes d’alignement traite les séquences nucléotidiques codantes sans prendre en compte leur structuration en codons. Nous avons développé une solution algorithmique spécialement conçue pour l’alignement multiple de séquences nucléotidiques codantes qui prend en compte la traduction en acides aminés de ces séquences, tout en autorisant l’apparition de changements de cadre de lecture et de codons stop. Dans le cas où les séquences ne contiennent pas ce type d’évènements rares, notre programme MACSE (Multiple Alignment of Coding SEquences) produit des alignements d’une qualité proche de celle des meilleures solutions actuelles (e.g. alignement obtenu via Muscle sur les séquences protéiques correspondantes). Cependant, tout l’intérêt de MACSE réside dans sa capacité aligner des séquences contenant des changements de cadre de lecture réels (ex. pseudogènes) ou apparents (erreurs de séquençage). MACSE permet ainsi de détecter des erreurs potentielles dans les séquences des bases de données publiques, d’aligner des séquences de (pseudo)-gènes ou des séquences obtenues gr‚ce aux nouvelles technologies de séquençage (ex. le 454), particulièrement sujettes aux erreurs par insertion délétion de nucléotides.
The Evolution of Prophages in Enterobacteriacaea.
Louis-Marie Bobay Génomique Evolutive des Microbes. URA2171, Institut Pasteur
Bacterial genomic evolution is a long-term process. However, some large genomic modifications are frequent and instantaneous. Many of these are caused by the chromosomal integration of phages. Such prophages are detrimental for their host as they can spontaneously lead to cell death. This study aims at understanding how prophages integrate genomes and how they subsequently decay. Prophages of 55 Salmonella and Escherichia genomes were detected and classified. Their investigation revealed a genomic distribution biased towards some hotspots and the leading strand. It was also possible to point out putative orthologous relationships between prophages providing a first glimpse on prophage evolution. Several prophages features suggest that a large part of them are non-functional remnants and that their decay is discontinuous with initial long deletions and later slow pseudogenization. This might reveal different selective pressures for deletion along prophages and even selection for the maintenance of small non-functional phages for the protection of the bacteria from large functional phages.
Evidence for adaptive evolution in Silene latifolia and close relatives from EST data: implications for the evolution of dioecy in plants.
Jos Käfer Laboratoire de Biométie et Biologie Evolutive, UMR CNRS 5558 - UCB Lyon I
Dioecy (i.e. having separate sexes) is rather rare in plants. Population genetic models have been used to explain why dioecy evolves, as a means to avoid inbreeding. Other models explain why dioecy does not persist: the fact that dioecious breeding systems in living plants are of recent origin has led to the hypothesis of a higher extinction risk in dioecious species. We use EST data from five species (three closely related dioecious Silene (among which S. latifolia), a gynodioecious Silene, and a gynodioecous outgroup species, Dianthus), from which we select orthologous sequences to estimate synonymous and nonsynonymous substitution rates. We find that the dioecious species undergo adaptive evolution, and discuss these results in the light of current theories on the evolution of dioecy and gynodioecy.
Gene families as communities in a similarity network
Vincent Miele, Simon Penel, Vincent Daubin, Daniel Kahn & Laurent Duret, LBBE, Villeurbanne
La constitution de familles de proteines homologues est une étape cruciale pour la constitution de bases de données phylogénomiques. A partir de l’ensemble considérable des comparaisons de séquences (Blast) deux deux, le challenge est de construire une approche de clustering qui soit la fois spécifique (des familles trop grandes intégreraient des proteines sans lien réel d’homologie) et sensible (des familles trop petites ne reconstitueraient pas la diversité nécessaire la reconstruction phylogénomique). Dans cette optique, une récente approche (Miele et al, submitted) proposait de revisiter le clustering par simple lien en intégrant de fortes contraintes de couverture et d’identité, et de modéliser l’ensemble des relations d’homologie par un réseau ou graphe de similarité. Chaque famille de proteines se trouvait alors être une composante connexe de ce réseau. Cependant, nous observons de manière empirique que certaines grandes familles ainsi obtenues peuvent faire l’objet d’investigations supplémentaires. Le sous-réseau de similarité associé une famille présente en effet une structure topologique en communautés. Afin de vérifier la cohérence en terme d’homologie de chaque famille et le cas échéant de découper celle-ci en sous-familles, nous proposons d’exploiter la structure en communautés trouvée par un algorithme ad-hoc (Clauset et al, 2004, préalablement sélectionné par un benchmark). Nous constituons donc des sous-familles en combinant des communautés. Par la suite nous utilisons MAFFT et HMMER pour obtenir un modèle d’alignement par sous-famille. Par une approche statistique de sélection de modèle (Biernacki et al, 2000), nous construisons un critère de vraisemblance (sous le modèle d’alignement) pénalisée (par une fonction du nombre de sous-familles). De cette façon, nous proposons un algorithme de clustering qui intégre intrinsèquement la balance entre spécificité et sensibilité dans ce critère pénalisé. Pour valider l’approche, nous étudions manuellement les familles de proteines mitochondriales, puis nous comparons nos résultats sur l’ensemble des familles présentes dans la base de données HOGENOM (Penel et al, 2009) vis vis de ceux obtenus avec d’autres outils publiquement disponibles.
Bio++2.0: nouvelles classes, nouveaux outils et modèles
Julien Dutheil & Laurent Guéguen, ISEM, LBBE
Bio++ est une librairie C++ dédiée la bioinformatique, en particulier l’analyse phylogénétique. Le passage la version 2.0 traduit le fait que Bio++ a été enrichie par de nombreuses améliorations et de nombreux développements, tant au niveau des classes qu’au niveau des modèles et des outils. Nous présenterons l’essentiel de ces progrès, du point de vue de programmeurs en C++ et du point de vue d’utilisateurs de programmes prêts l’emploi.
Similarité de séquence et microsynténie pour la reconstruction de systèmes: exemple sur la voie Chaperonne-Usher
Calderon Virginie(1), Roland Barriot(1), Sophie de Bentzmann(2), Yves Quentin(1) et Gwenanele Fichant(1)
(1)LMGM, CNRS- Université Paul Sabatier, Toulouse (2)LISM, CNRS, Marseille
La voie Chaperonne-Usher (CUP) est uniquement présente chez les Protéobactéries. Elle permet l’assemblage de structures la surface bactérienne allant de la simple exposition d’une adhésine l’assemblage d’un filament de type fimbriae ou pili. Ces facteurs de virulence sont impliqués dans l’adhésion aux cellules hôte et dans la formation de biofilm. Les gènes impliqués dans cette voie sont organisés en un opéron qui code au minimum pour 3 protéines différentes, (i) un usher, protéine de la membrane externe formant un pore de translocation, (ii) une chaperonne périplasmique, et (iii) les sous unités pilines ou adhésines prises en charge par la chaperonne. Les sous-unités pilines et adhésines sont peu conservées en séquences et donc mal annotées dans les génomes. Une faible conservation ne permet pas la reconstruction d’arbres phylogénétiques pour appréhender l’évolution au niveau de la famille. Le usher apparaît comme l’élément du système le plus conservé, il peut donc servir de point d’ancrage pour reconstruire les systèmes complets. Une première classification des systèmes CUP a été proposée en 6 sous-familles (Nuccio et Bäumler, 2007), en se basant sur l’étude phylogénétique de 189 ushers. Afin de reconstruire les systèmes CUP fonctionnels et de les classer en groupes de systèmes orthologues, nous avons utilisé une approche par biclustering alliant microsynténie et relation d’orthologie. Le principe de cette approche est d’utiliser la microsynténie comme un indicateur de relation évolutive et fonctionnelle: pour un gène donné, ses voisins sur le génome sont aussi pris en compte. Tous les orthologues dans cette région sont récupérés par recherche de similarité de séquence dans les génomes complets procaryotes. Les données sont représentées sous forme de graphe non orienté et non pondéré, les noeuds représentent les gènes et les arêtes un lien d’orthologie. Une méthode de partition, MCL (Dongen, 2000), est ensuite appliquée ce graphe afin d’isoler les groupes d’orthologues qui devraient avoir conservé la même fonction. La microsynténie et les liens d’orthologie peuvent être représentés simultanément dans une même matrice dans laquelle une cellule correspond un gène, une colonne un ensemble de gènes voisins sur le même génome, et une ligne un groupe d’orthologues. La dernière étape consiste utiliser une méthode de biclustering (Bergmann et al., 2003) pour identifier des sous-ensembles de systèmes composés de partenaires orthologues, appelés biclusters, liés la fois par une relation d’orthologie et par microsynténie dans un génome. Ces sous-ensembles constituent les sous-familles coeur. Nous avons appliqué cette approche de biclustering aux 360 systèmes CUP présents dans les génomes complets (sans redondance de souche) en ancrant l’analyse sur le usher. L’analyse a permis d’établir 8 sous-familles coeur dont les séquences peuvent servir établir des profils spécifiques pour chaque partenaire de chaque sous-famille pour une meilleure annotation des systèmes dans les nouveaux génomes. La classification obtenue par biclustering est cohérente avec la classification proposée par Nuccio et Bäumler, elle permet cependant une classification plus fine en faisant émerger des sous sous-familles de systèmes CUP qui présentent une stricte conservation du voisinage chromosomique. Les profils établis partir des sous-familles coeur peuvent être utilisés pour attribuer une sous-famille aux séquences non classées par notre approche. En effet, l’étape de partitionnement de graphe, les gènes n’appartenant pas un groupe d’orthologues sont exclus de l’analyse, ceci peut être dû un voisinage génomique non conservé, des pertes ou duplications de gènes. Dans notre analyse, 58% des systèmes CUP appartiennent aux sous-familles coeur, et l’utilisation de profils permet au final de classer plus de 80% des systèmes CUP. L’annotation et la classification des systèmes CUP dans les génomes complets a permis d’établir que ces systèmes CUP étaient majoritairement présents chez les entérobactéries, les pseudomonadales et les burkholdériales. On retrouve un maximum de 15 systèmes CUP dans 2 génomes, Proteus mirabilis et Citrobacter koseri, mais le nombre de système par génome n’est pas corrélé la taille du génome. Dans la suite de notre travail, nous rechercherons si le contenu en CUP des génomes peut être corrélé au pouvoir pathogène de la bactérie et/ou sa spécificité d’hôte.
Références: -Bergmann, S., Ihmels, J. and Barkai, N. (2003) Iterative signature algorithm for the analysis of large-scale gene expression data. Phys Rev E Stat Nonlin Soft Matter Phys., 67, 031902-1:031902-18. -van Dongen, S. (2000) Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, Utrecht, Nederlands. -Nuccio, S. and Bäumler, A. (2007) Evolution of the Chaperone/Usher Assembly Pathway: Fimbrial Classification Goes Greek. Microbiol. Mol. Biol. Rev., 71: 551-575.
Simultaneous inference of gene trees and organism tree in the presence of duplications and losses
Bastien Boussau, Gergely Szollosi, Laurent Duret, Manolo Gouy, Eric Tannier, Vincent Daubin, LBBE, UMR CNRS 5558 ; Université de Lyon ; Université lyon 1
Organism trees are usually built as an average of the signal of at most a few dozen gene families. However, several biological processes can affect gene families to the extent that gene family trees may strongly differ from the true organism tree. Duplications and losses of genes are two such processes. In order to reconstruct an organism tree from gene sequences, we propose to model gene family evolution in the presence of gene duplication and loss, and consequently separately infer gene family trees and organism tree. In this model, each branch of the organism tree is associated to particular duplication and loss parameters. We explain how one can efficiently compute the likelihood of an organism tree and gene family trees with such a model, and present its parallel implementation in PHYLDOG, a program able to analyze simultaneously dozens of species and thousands of gene families in a statistical framework. We show that PHYLDOG performs very well on simulated data, and we reveal general trends of genomic evolution by applying it to more than 7000 gene families in 37 whole genome sequences from mammalian species.
Utilisation pratique des méthodes combinatoires de reconstruction de réseaux phylogénétiques
Philippe Gambette Institut de Mathématiques de Luminy - CNRS / Université Aix-Marseille 2
Les réseaux phylogénétiques représentent l’évolution en prenant en compte et en faisant apparaître les événements d’hybridation, de recombinaison ou de transferts horizontaux, dans des parties réticulées. Plusieurs méthodes et logiciels ont été développés pour les reconstruire partir de données combinatoires (triplets, quadruplets, clades et bipartitions) provenant d’arbres de gènes contradictoires. Nous les présenterons brièvement avant d’évoquer les limites d’utilisation pratique de ces outils sur des données réelles. En effet, ces méthodes considèrent généralement que les données en entrée sont complètes et correctes, et nous montrerons comment procéder pour satisfaire ces conditions par une sélection et un prétraitement appropriés des données. Enfin, nous présenterons un panorama des résultats de ces diverses méthodes, tous visualisés avec le logiciel Dendroscope. Ceci illustrera une approche exploratoire de reconstruction phylogénétique avec réticulations, où la reconstruction du réseau est suivie d’un retour aux arbres, et aux séquences, pour repérer les possibles transferts de matériel génétiques entre espèces co-existantes.
The origin of the modern Testudinoidea
João Lourenço ISEM - Institut des Sciences de l’Evolution Montpellier
The superfamily Testudinoidea is the most diverse living turtle group, classified in three families: the Geoemydidae (mostly Paleartic), the Emydidae (mostly Neartic), and the Testudinidae (widely distributed). Recently, the Big-headed turtle (Plastysternon megacephalum) has also been included in this group. The oldest known fossils of modern testudinoids are reported from the Early Eocene of Europe and North America. The fossil record indicates a radiation from the stem group Lindholmemydidae, which is known only from the Cretaceous and Paleocene of Asia. However, the fossil record is rather poor before the Eocene, so that the origin and early evolution of the modern testudinoids is still an open question. To address this topic, we infered the molecular phylogeny of 38 species of living turtles, based on both mitochondrial and nuclear genes. Our molecular dataset includes four relevant species for which we have sequenced the nearly complete mitochondrial genome. To estimate the timing of the testudinoid radiation, we used fossil data to calibrate the internal nodes of the phylogeny. Our results indicate an earlier origin of the modern testudinoids, when compared to the timing suggested in previous studies. One of the key results is the suggestion of an early split between Platysternon and the Emydidae around the Turonian (Late Cretaceous), which is consistent with the existence of a land bridge between Asia and North America, high global temperatures that could have favored dispersal, and the first occurrence of Asian taxa in the North American fossil record around that time.
Calcul des intervalles communs approchés de plusieurs séquences
Pierre Riou LIRMM Montpellier
La génomique comparée a pour objet la recherche de similarités et de différences entre plusieurs génomes. La méthode présentée ici permet de chercher des régions de contenu en gènes proches sur des génomes complets. Elle permet donc de détecter des réarrangements complexes (avec des insertions/délétions) ou de grande taille. Afin d’obtenir des données d’entrée une étude des marqueurs communs entre les génomes étudier est nécessaire. Ces marqueurs peuvent être par exemple des gènes homologues. Dans ce cas, on peut obtenir des relations d’homologies dans des bases de données comme OMA, KOG, ... On construit ensuite une séquence par génome, qui contient les identifiants de ces marqueurs dans l’ordre dans lequel ils apparaissent sur le génome. Notre méthode calcule les intervalles communs approchés pour les séquences d’entrée, qui sont une généralisation des intervalles communs de séquence utilisés par exemple par Schmidt et Stoye (2004). Ils permettent d’autoriser un nombre limité d’insertions à l’intérieur d’une zone commune réarrangée détectée. Etant donnés k génomes, des entiers s et d, nous cherchons tous les intervalles communs approchés de taille au moins s et tels que le nombre d’insertions maximal à l’intérieur de ces zones réarrangées soit inférieur à d. L’algorithme de calcul de ces intervalles communs approchés procède grâce à la construction d’un graphe permettant de représenter la proximité entre des intervalles communs exacts. Dans une deuxième phase, le calcul des cliques maximales dans ce graphe permet d’obtenir les intervalles communs approchés pour les séquences données en entrée. Le problème de l’énumération de toutes les cliques d’un graphe est NP-complet ( il peut y avoir un nombre exponentiel de cliques dans le graphe). Des algorithmes exacts, mais également des heuristiques ont donc été implémentés. Une application sur des génomes bactériens est en cours.
Bibliographie : [1] T. Schmidt and J. Stoye. Quadratic time algorithms for finding common algorithms in two or more sequences. Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, 2004. [2] K. Jahn. Efficient computation of approximate gene clusters based on reference occurrences. Lecture Notes in Computer Science, 6398/2011(DOI: 10.1007/978-3-642-16181-0-22):264–277, 2011.
Prunier: Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests.
Sophie Abby Génomique Evolutive des Microbes, Institut Pasteur, Paris
Lateral gene transfers (LGT) are thought to be an efficient way for prokaryotes to acquire new functions and/or to adapt quickly to rapid environmental changes, making them key events in prokaryotic genome evolution. Phylogenetic methods are a gold standard to detect LGT from gene trees. They consist in the detection of deviations of gene histories from the species histories by comparing gene trees and species trees. But building reliable gene histories is difficult, and one should take into account uncertainties in gene trees. In particular, some branching can be not significantly different from those found in the species trees, and could not correspond to transfer events. We propose a new phylogenetic method for transfer detection, Prunier, that deals with support values of gene trees to detect LGT. Prunier is a greedy algorithm, and was compared to two combinatorial methods, EEEP (Beiko et Hamilton 2006) and Riata-HGT (Nakhleh et al., 2005). On a simulated dataset, Prunier showed the best performances. In particular, it inferred less false positives than the more robust of the two other methods. This showed the relevance of using support values as a guide during LGT search. An improved version of Prunier is proposed, aiming at further alleviating the number of false positives events by using a less greedy procedure.
The phylogenomic analysis of the ACP/C and its targets points to a complex and modern-like control of the cell cycle in LECA
Laura Eme, Aurélie Trilles, David Moreira, Céline Brochier-Armanet, Laboratoire de Chimie Bactérienne UPR9043, Marseille
The Anaphase Promoting Complex/Cyclosome (APC/C) is an ubiquitin ligase [E3] that plays a crucial role in the control of the cell cycle and cell proliferation by marking target proteins for degradation by the 26S proteasome. APC/C is the largest (1.5 MDa) and most complex E3 known to date, being composed of one or several copies of at least a dozen subunits and cofactors. Using a phylogenomic approach, we show that 14 out of the 21 known APC/C components and cofactors and 9 out of its 13 main targets were already present in the Last Eukaryotic Common Ancestor (LECA) and were conserved to few exceptions in all present-day eukaryotic lineages. This finding indicates that LECA had a complex and highly controlled modern-like cell cycle. With only two exceptions, we do not identify any homologue of APC/C components/cofactors/targets in prokaryotes indicating that this large complex and its main targets are eukaryotic innovations that emerged in the eukaryote stem, i.e. prior to the diversification of present-day eukaryotic lineages. Surprisingly, we also highlighted massive losses of APC/C components in a few lineages, such as Apicomplexa, a major eukaryotic group comprising numerous parasites (e.g. Plasmodium falciparum or Cryptosporidium hominis) suggesting recent drastic changes in the control of some steps of their cell cycle. The second aspect of this work is that the phylogenetic analysis of the APC/C components inferred to be present in LECA shows that they contain a good phylogenetic signal to reconstruct the phylogeny of this domain of life. The resulting phylogeny is globally in agreement with those based on large concatenations of informational genes, indicating that, contrarily to what is generally assumed, proteins involved in housekeeping cellular functions can represent interesting alternative to study the phylogeny of Eukaryotes.
Epissages de caractères et technique du ’ratchet’. Récents développements pour améliorer les techniques d’inférence phylogénétique.
Alexis Criscuolor Institut Pasteur
Les techniques standards d’inférence phylogénétique s’appuient sur des alignements de séquences homologues pour rechercher l’arbre optimisant un critère donné en utilisant, le plus souvent, des heuristiques de recherche locale. Durant cet exposé, je décrirai quelques nouvelles approches récemment développées pour pré-traiter les alignements de séquences et pour améliorer certaines heuristiques recherchant l’arbre optimisant le critère du Maximum de Vraisemblance (ML). Dans un premier temps, je présenterai un nouveau logiciel, nommé BMGE (Block Mapping & Gathering with Entropy), qui a été récemment implémenté pour permettre de sélectionner des sous-ensembles de caractères au sein d’un alignement de séquences. Cette sélection s’effectue suivant deux méthodes distinctes : la première détermine les blocs de caractères trop variables pour induire un signal phylogénétique non-ambigu puis supprime ces caractères induisant un effet de saturation, alors que la deuxième approche détermine si les séquences sont de compositions non-homogènes puis, le cas échéant, y sélectionne un sous-ensemble de caractères de composition homogène. Je présenterai ensuite une nouvelle implémentation permettant d’appliquer une technique de recherche locale nommée ’ratchet’ pour inférer des arbres par optimisation du critère ML. Cette technique permet la recherche heuristique de sortir de certains optima locaux en bruitant l’alignement de séquences analysé. Initialement proposée et utilisée pour améliorer les heuristiques de recherche d’arbres optimisant le critère du Maximum de Parcimonie (MP), son adaptation au cas du critère ML permet d’observer des résultats intéressants. En m’appuyant sur différents résultats de simulation, je montrerai tout au long de cet exposé que ces différentes techniques (i.e. pré-traitements des alignements de séquences, inférences ML par recherches locales avec ’ratchet’) peuvent avoir un impact significatif sur la qualité des arbres phylogénétiques inférés.
Investment in growth determines the relative evolutionary rates among essential proteins
Sara Vieira-Silva Microbial Evolutionary Genomics group, Institut Pasteur
Proteins evolve at very different rates and these rates are thought to change through time. The major known universal determinant of protein evolutionary rates is the level of expression in that highly expressed proteins evolve slower than lowly expressed ones. Yet, the relative weight of highly expressed proteins in the cell budget increases with growth rate. At very fast growth a few percent of genes account for over 90% of all gene expression. We therefore hypothesized that changes in maximal growth rates should impact the evolutionary rate of highly expressed proteins but not, or much less so, that of lowly expressed proteins. We analyzed the 85 families of orthologs identified in 59 different proteobacterial species and found that indeed the difference between the rates of evolution of highly and lowly expressed essential proteins is greater for rapidly dividing organisms. These results were confirmed when analyzing the concatenation of the protein constituents of the ribosome and DNA polymerase, well-described essential protein complexes with strikingly different expression levels. Under the premise that among fast growers the most highly expressed proteins do evolve slower relative to other essential lowly expressed proteins, we also propose that the topology of deep-phylogenetic inferences could be influenced by the choice in protein dataset. When using highly expressed ubiquitous informational protein coding proteins the clades rich in slow-growers have longer branch lengths and therefore branch deeper in the phylogenetic trees. Our results show for example that clades such as cyanobacteria, which are believed to have experienced long-term absence of selective pressure for fast growth, branch deeper in a highly expressed proteins based phylogenetic reconstruction of the tree of Prokaryotes than in one based on lowly expressed proteins. These results therefore show how the biochemical adaptation to ecological strategies can strongly influence the evolutionary patterns of essential proteins along time.
Échantillonner dans l’espace des scénarios de remaniements
Eric Tannier, I Miklos, INRIA, LBBE, Lyon
On cherche à expliquer les différences structurales entre deux génomes par des séquences de remaniements chromosomiques. La plupart du temps, il existe un très grand nombre de solutions qui rendent inutile l’examen de l’une d’entre elles. On propose donc de générer des propriétés probables de telles séquences en échantillonnant l’espace des solutions. On montre que sous certains modèles, on peut donner une garantie théorique sur la vitesse de convergence de la chaîne de Markov Monte Carlo qui nous sert à explorer l’espace. On l’applique à plusieurs types de génomes, et on voit que certaines branches semblent privilégier certains types de remaniements au détriment d’autres.
Searching for virus phylotypes using extrinsic traits and statistical criteria
Francois Chevenet, Tulio de Oliveira, Olivier Gascuel, LIRMM
Abstract Motivation: Very large virus phylogenies are built today to study their evolution, trace the origin of epidemics, establish their mode of transmission or survey the apparition of drug resistances. However, no tool is available to quickly inspect these phylogenies and combine them with extrinsic traits (e.g. geographic location, risk group, presence of a given resistance mutation,), aiming to extract strain groups with specific interest or requiring surveillance. Method: We propose a method to extract such groups, which we call phylotypes, from a phylogeny having taxa (strains) annotated with extrinsic traits. Phylotypes are subsets of taxa with close phylogenetic relationships and common trait values. A phylotype is not necessarily a clade from the input tree, but may be part of a clade, with the remaining taxa in this clade being exceptions and possibly forming another phylotype. The method combines ancestral trait reconstruction and numerical and statistical criteria measuring tree shape characteristics and the diversity and separation of the potential phylotypes. A shuffling procedure is used to assess significance. Results: This method is implemented in an interactive web application (www.phylotype.org), which processes large data sets in a few seconds or minutes ( 10 minutes with 6352 taxa and 5 shuffling steps). A number of tools are available to root the tree, combine traits using logical connectors and draw the resulting tree and phylotypes. A variety of criteria can be selected and adjusted interactively by users to define their phylotypes depending on data analyzed. We apply this software to HIV transmission chains and drug resistance. The method is able to recover evolutionary scenarios that were previously established (Hué et al. 2009) using more sophisticated and time consuming approaches, or using lengthy manual analyzes. Moreover, new drug resistance groups are identified. Availability: Web application freely available from www.phylotype.org Contacts: chevenet@lirmm.fr, tdeoliveira@africacentre.ac.za, gascuel@lirmm.fr
neXtProt: A new knowledge platform on human proteins
Pascale Gaudet, CALIPHO, Suisse
neXtProt is a new knowledge platform from the Swiss Institute for Bioinformatics specialized on human proteins. neXtProt is being developed in the framework of the CALIPHO project (Computer and Laboratory Investigation of Proteins of Human Origin), whose objective is to use a combination of bioinformatics and experimental methodologies to increase our knowledge of human proteins. neXtProt contents: By focusing on a single species, neXtProt is able to integrate much more information than Swiss-Prot. In addition to the corpus of data on human proteins available in Swiss-Prot, neXtProt contains additional data, including expression data from microarrays and ESTs and tissue localization. Over the next few months the amount and variety of data will continue to increase, to include proteomics, protein structure and pathway data. We will also integrate phylogenetics data, at two levels: (i) we will integrate the knowledge from closely related species to make predictions of gene functions for human proteins, and (ii) we will provide orthology information, as well as phylogenetic distributions. This will probably be done in collaboration with the Panther project (panther.org). neXtProt functionality: Our vision is not only to provide a knowledgebase, but a true collaborative platform for organizing, sharing and generating knowledge. Over the next year we will deploy new functionalities to favorise and label proteins, as well as tools to share data and information with other users of neXtProt, thus facilitating collaborations and data sharing. The data in neXtProt is organized in such a way that it is intuitive to make powerful queries, while taking into account the complexity and the heterogeneity of the data available. We are in the process of developing new and innovative search tools that take advantage of the flexible organization of the database. The first public version was released in early 2011, and is accessible at beta.nextprot.org.
Evidence of large-scale gradients of replication fork polarity - Relation to genome 3D structure
Antoine Baker Laboratoire Joliot-Curie ENS Lyon
The human genome has been previously segmented in N-domains, where the compositional skew S=(T-A)/(T+A)+(G-C)/(G+C) displays a N-shape pattern. Replication timing data in different cell lines show that N-domains often correspond to replication timing domains shaped as a U, that we called U-domains. We think that skew N-domains are replication timing U-domains in the germline, we can indeed relate the two introducing the replication fork polarity (proportion of sense forks minus the proportion of antisense forks). We show how the replication fork polarity can be extracted from replication timing data and why compositional skew is expected to be proportional to the replication fork polarity. We found that replication timing U-domains have remarkable properties in term of chromatin state and 3D structure. U-domains borders are strongly enriched in open chromatin markers and long-range chromatin interaction (Hi-C) data show that they correspond to self-interacting structural units.
Analyse évolutive des récepteurs couplés aux protéines G par multidimensional scaling
Julien Pelé et Marie Chabbert, UMR CNRS 6214 - INSERM U771, Faculté de Médecine, 3 rue Haute de Reculée, 49045 ANGERS, FRANCE
Les récepteurs couplés aux protéines G (RCPG) de classe A forment la plus grande famille de récepteurs transmembranaires du génome humain. Leur analyse évolutive par les méthodes classiques de phylogénie est très difficile du fait de la taille de cette famille et du grand nombre de sous-familles. Afin d’obtenir des informations complémentaires sur l’évolution de cette famille, nous avons exploré leur espace de séquence par multidimension scaling (MDS). La visualisation des séquences dans un espace trois dimensions met en évidence une distribution inhomogène des récepteurs qui forment quatre groupes. Pour interpréter ces directions, nous avons analysé les déterminants de séquences spécifiques de chaque groupe. Nos résultats sont en accord avec un modèle d’évolution radiale partir d’un noyau central. Les directions privilégiées obtenues par MDS sont interprétables en termes de trois chemins évolutifs principaux. Le premier chemin correspond la différentiation des récepteurs d’amines. Le second a été initié par la délétion d’un résidu dans l’hélice transmembranaire 2 et a conduit trois sous-familles par divergence. Le troisième chemin correspond l’évolution parallèle de plusieurs sous-familles en lien avec un mécanisme de covarion. Comme en témoigne l’exemple des RCPG, le multidimensional scaling permet de mettre en évidence des informations originales sur l’histoire évolutive des familles de protéines.
Probabilistic substitution mapping to explore the heterogeneity of sequence evolutionary process across a phylogenetic tree.
Jonathan Romiguier Institut des Sciences de l’Evolution de Montpellier
With a set of aligned sequences and a reference phylogenetic tree, Markov models of evolution can be used to map the substitutions that occurred at each site onto each branch (Dutheil et al. 2005). To assess the robustness of this probabilistic substitution mapping, we simulated sequence data sets (of nucleotide or codons) from non-homogeneous model, and compared their known substitutional history with the ones inferred under various model assumptions. We showed that probabilistic mapping is robust, whatever the substitution model or branch lengths used for the inference. On the basis of this robustness, we designed a new clustering algorithm which groups infers branch partitions with similar substitution process in a given tree. The resulting candidate partitions can be statistically validated by fitting the corresponding non homogeneous model and comparing it to simpler models, for instance using a likelihood ratio test. We demonstrate the power of this new method for providing more accurate models of sequence evolution on several data sets, and suggest that this method can also be used for reconstructing ancestral processes of sequence evolution.
HMMs basés sur la phylogénie pour la modélisation d’homologues distants
Jean-Baka Domelevo Entfellner, LIRMM
À partir d’un alignement de séquences, on sait construire un modèle probabiliste de type HMM profil en désignant un certain nombre de sites comme étant des colonnes conservées, qui constituent l’ossature du modèle (états "Match"). Un HMM profil encode les probabilités de transition entre états ainsi que les probabilités d’émission sur les états Match et Insertion, toutes étant le produit d’un comptage avec lissage.
L’information phylogénétique n’est donc pas utilisée lors de la construction du HMM profil, qui est une sorte de modèle médian représentant un consensus probabiliste entre toutes les séquences de l’alignement de départ.
Nous présentons plusieurs outils permettant l’utilisation d’informations phylogénétiques explicites dans le cadre de la mise au point de modèles plus adaptés à la recherche de protéines homologues distantes : 1) Remplacement du couple classique comptes + priors par un processus de reconstruction phylogénétique s’appuyant sur un arbre sous-jacent pour la détermination des probabilités d’émission sur les états Match et Insertion, 2) Utilisation de l’alignement des transitions utilisées par les séquences d’apprentissage sur le HMM pour faire également de la reconstruction phylogénétique et prédire comment une séquence va s’enrouler sur le HMM en fonction de sa localisation connue ou inférée dans l’arbre, 3) Estimation des longueurs des zones d’insertion par reconstruction d’après une phylogénie sur des caractères quantitatifs entiers.
L’intégration de ces différents outils aboutit à un générateur simple de HMM profils permettant d’obtenir à partir d’un alignement de séquences et d’un arbre support un jeu de HMMs, chacun résultant d’une reconstruction en un nœud de l’arbre. Ce travail continue et raffine ceux de Mitchison et Durbin (J. Mol. Evol. 1995 et 1999), Qian et Goldstein (Proteins, 2003) et Löytynoja et Goldman (Science 2008). En présentant des résultats obtenus sur des séquences biologiques issues de superfamilles SCOP/ASTRAL, nous mettons en évidence des performances accrues en termes de vraisemblance sur des séquences homologues distantes.
Home
