Search

National audience; High-throughput DNA and RNA sequencing has become a routine experiment in molecular biology and life sciences in general. It is increasingly used in the hospital as a key procedure of person-alized medicine. Compared to the second generation, third generation sequencing technologies produce longer reads with comparatively lower throughput and higher error rate. Those errors include substitutions, indels, and they hinder or at least complicate downstream analysis like mapping or de novo assembly. However, these long read data are often used in conjunction with short reads of the 2nd generation. I will present a hybrid strategy for correcting the long reads using the short reads that we introduced last year. Unlike existing error correction tool, ours, called LoRDEC, avoids the alignment of short reads on long reads, which is computationally very intensive. Instead, it takes advantage of a succinct graph to represent the short reads, and compares the long reads to paths in the graph. Experiments show that LoRDEC outperforms existing methods in running time and memory while achieving a comparable correction performance. In conclusion, i will comment on the impact of read error correction. Work in collaboration with L. Salmela from University of Helsinki. LoRDEC is available at: http://www.lirmm.fr/~rivals/lordec/

Read mapping on De Bruijn graphs additional file. Three complementary tables are presented. Main characteristics of data sets used in this study. Assembly and mapping approach comparison. Results of BGREAT on real read sets. (PDF 40 kb)

National audience; De par son comportement, ses déplacements, ses communications, chaque individu laisse des traces digitales qui sont aujourd'hui de plus en plus souvent mémorisées par des systèmes informatiques. Cette masse d'information peu structurées, diverses, réparties géographiquement renferme dans les relations entre ces informations des connaissances sur ces individus. Explorer ces informations par traitement informatique pour en extraire ces connaissances est le rôle de la fouille de données – ou de l'extraction de connaissances. Les techniques utilisées sont pluridisciplinaires : statistique classique, analyse de données, et divers domaines de l'informatique tels que l'apprentissage automatique, les bases de données et l'algorithmique. Aujourd'hui les applications les plus visibles de la fouille de données concerne l'analyse des requêtes internet pour élaborer de la publicité ciblée ou l'analyse des comportements internet pour inférer le profil des visiteurs ou des clients à des fins de gestion ou de marketing. Clairement, ce type de méthodes et d'analyse s'appliquent au domaine médical et aux sciences de la vie. L'hétérogénéité des données et la complexité du domaine rendent leur application plus délicate. En revanche, l'intérêt et les avantages potentiels de ces applications sont énormes : potentiel en médecine personnalisée ou de précision, inférence de règles pour l'aide thérapeutique, économies dues à une meilleure prise en charge. Cette présentation contient une introduction à la fouille de données et sa variante concernant les très grands volumes de données, le « Big Data », liste quelques applications au domaine médical, et donne quelques intuitions sur les méthodes informa-tiques utilisées.

Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. SCCS can also be solved by a greedy algorithm. Here, we propose a linear time algorithm for solving SCCS based on a Eulerian graph that captures all greedy solutions in linear space. Because the graph is Eulerian, this algorithm can also find a greedy solution of SCCS with the least number of cyclic strings. This has implications for solving certain instances of the Shortest linear or cyclic Superstring problems.

for the keynote presentation; International audience; High-throughput DNA and RNA sequencing has become a routine experiment in molecular biology and life sciences in general. It is increasingly used in the hospital as a key procedure of personalized medicine. Compared to the second generation, third generation sequencing technologies produce longer reads with comparatively lower throughput and higher error rate. Those errors include substitutions, in-dels, and they hinder or at least complicate downstream analysis like mapping or de novo assembly. However, these long read data are often used in conjunction with short reads of the 2nd generation. I will present a hybrid strategy for correcting the long reads using the short reads that we introduced last year. Unlike existing error correction tool, ours, called LoRDEC, avoids the alignment of short reads on long reads, which is computationally very intensive. Instead, it takes advantage of a succinct graph to represent the short reads, and compares the long reads to paths in the graph. Experiments show that LoRDEC outperforms existing methods in running time and memory while achieving a comparable correction performance. In conclusion, i will comment on the impact of read error correction. LoRDEC is available at http://atgc.lirmm.fr/lordec and is a joint work with Leena Salmela.

Background Comparing and aligning genomes is a key step in analyzing closely related genomes. Despite the development of many genome aligners in the last 15 years, the problem is not yet fully resolved, even when aligning closely related bacterial genomes of the same species. In addition, no procedures are available to assess the quality of genome alignments or to compare genome aligners. Results We designed an original method for pairwise genome alignment, named YOC, which employs a highly sensitive similarity detection method together with a recent collinear chaining strategy that allows overlaps. YOC improves the reliability of collinear genome alignments, while preserving or even improving sensitivity. We also propose an original qualitative evaluation criterion for measuring the relevance of genome alignments. We used this criterion to compare and benchmark YOC with five recent genome aligners on large bacterial genome datasets, and showed it is suitable for identifying the specificities and the potential flaws of their underlying strategies. Conclusions The YOC prototype is available at https://github.com/ruricaru/YOC. It has several advantages over existing genome aligners: (1) it is based on a simplified two phase alignment strategy, (2) it is easy to parameterize, (3) it produces reliable genome alignments, which are easier to analyze and to use. Electronic supplementary material The online version of this article (doi:10.1186/s12859-015-0530-3) contains supplementary material, which is available to authorized users.

Background Cost effective next generation sequencing technologies now enable the production of genomic datasets for many novel planktonic eukaryotes, representing an understudied reservoir of genetic diversity. O. tauri is the smallest free-living photosynthetic eukaryote known to date, a coccoid green alga that was first isolated in 1995 in a lagoon by the Mediterranean sea. Its simple features, ease of culture and the sequencing of its 13 Mb haploid nuclear genome have promoted this microalga as a new model organism for cell biology. Here, we investigated the quality of genome assemblies of Illumina GAIIx 75 bp paired-end reads from Ostreococcus tauri, thereby also improving the existing assembly and showing the genome to be stably maintained in culture. Results The 3 assemblers used, ABySS, CLCBio and Velvet, produced 95% complete genomes in 1402 to 2080 scaffolds with a very low rate of misassembly. Reciprocally, these assemblies improved the original genome assembly by filling in 930 gaps. Combined with additional analysis of raw reads and PCR sequencing effort, 1194 gaps have been solved in total adding up to 460 kb of sequence. Mapping of RNAseq Illumina data on this updated genome led to a twofold reduction in the proportion of multi-exon protein coding genes, representing 19% of the total 7699 protein coding genes. The comparison of the DNA extracted in 2001 and 2009 revealed the fixation of 8 single nucleotide substitutions and 2 deletions during the approximately 6000 generations in the lab. The deletions either knocked out or truncated two predicted transmembrane proteins, including a glutamate-receptor like gene. Conclusion High coverage (>80 fold) paired-end Illumina sequencing enables a high quality 95% complete genome assembly of a compact ~13 Mb haploid eukaryote. This genome sequence has remained stable for 6000 generations of lab culture. Electronic supplementary material The online version of this article (doi:10.1186/1471-2164-15-1103) contains supplementary material, which is available to authorized users.

International audience; When a reference genome is available, analysis of Next Generation Sequencing (NGS) reads require to determine the plausible genomic position(s) for all reads. This computational step is termed mapping. This lecture will provide an overview of underlying concepts of the mapping question, algorithms, and pitfalls: alignment, approximate motif searching, filtration, and indexing data structures (like the Burrows Wheeler Transform). The impact of the read length, the background mapping probability, or sequencing errors on the results will be illustrated. This will lead us to present the most current mapping algorithms and their limitations; the results of a comparison will be presented. The cases of genomic and transcriptomic data will be considered in this regard, and finally the question of efficiency will be addressed. In a second time, we will give a short overview of concepts for assembly methods.

International audience; Next-generation sequencing technologies are presently being used to answer key biological questions at the scale of the entire genome and with unprecedented depth. Whether determining genetic or genomic variations, cataloguing transcripts and assessing their expression levels, finding recurrent mutations in cancer, identifying DNA-protein interactions or chromatin modifications, surveying the species diversity in an environmental sample, all these tasks are now tackled with High Throughput Sequencing (HTS). For genomics and transcriptomics data set, the current paradigm of analysis of large read sets consists in: 1. mapping the reads to a reference genome contigously allowing as many differences as one expects to be necessary to accomodate sequence errors and small polymorphisms; 2. using uniquely mapped reads to determine covered genomic regions, either for computing a local coverage to predict SNPs and filter out sequence errors (cf. program ERANGE), or for delimiting expressed exons approximately (with RNA-seq; cf. programs TopHat GMORSE), 3. re-aligning unmapped reads, which were not mapped contigously at step one, to reveal exon boundaries or larger indels. As shown by the results of approaches following this paradigm, a number of pitfalls/drawbacks must be accomodated: mapping errors induce false predictions at further steps, indels larger than 4 bp are not handled, the impossibility to distinguish SNPs from sequence errors at mapping stage, the lack of precision on exon boundaries, etc. On the other hand, we have developped an exact mapper, called MPSCAN, for short reads [2], and analysed its performance in detecting uniquely mapped regions in function of tag length [1]. We could show that one can estimate depending on the genome length, a length k of substring that will in average point to a single genomic location. Building on this work, we have conceived a new approach to analyse nowadays longer reads (> 50 bp). We record for all the k-mers along the read their matching genomic positions and number of occurrences in the reads, and then analyse jointly these profiles to determine whether a read can be mapped contigously or detect multiple causes of alignment disruption: large indels, introns, rearrangements. In this talk, we will present this procedure, the underlying data structures, show that it distinguishes SNP from sequence errors, and allies sensitivity and specificity in the prediction of exon boundaries, indels, and rearrangements. Work in collaboration with M. Salson (U. Rouen), N. Philippe et T. Commes (U. Montpellier 2). Related publications: [1] Using reads to annotate the genome: influence of length, background distribution, and sequence errors on prediction capacity N. Philippe*, A. Boureux*, L. Bréhèlin, J. Tarhio, T. Commes, E. Rivals Nucleic Acids Research (NAR) doi:10.1093/nar/gkp492; 2009. [2] MPSCAN: fast localisation of multiple reads in genomes E. Rivals, L. Salmela, P. Kiiskinen, P. Kalsi, J. Tarhio Proc. 9th Workshop on Algorithms in Bioinformatics. Lecture Notes in BioInformatics (LNBI), Springer-Verlag, Vol. 5724, p. 246-260, 2009.

National audience; Ultra-high throughput sequencing (HTS) is used to analyse the transcriptome or interactome at unprecedented depth on a genome-wide scale. These techniques yield short quence reads that are then mapped on a genome sequence to predict putatively transcribed or protein-interacting regions. We argue that factors such as background distribution, sequence errors, read length impact on the prediction capacity of sequence census experiments. Here we suggest a computational approach to measure these factors and analyse their influence on both transcri mic and epigenomic assays. We developped and tuned a bioinformatic pipeline to assess the expression level of known mRNAs and predict novel splicing variants based on the transcript sig ures (reads) obtained by Digital Gene Expression (DGE). However, almost 30% of the signatures map to non coding regions, suggesting the existence of unknown transcripts. To cross validate in ico those novel RNAs, we take advantage of RNA-seq, as well as other publicly available DGE data, and visualise all data in the genomic context.

submitted; A superstring of a set of words is a string that contains each input word as a sub-string. Given such a set, the Shortest Superstring Problem (SSP) asks for a super-string of minimum length. SSP is an important theoretical problem related to the Asymmetric Travelling Salesman Problem, and also has practical applications in data compression and in bioinformatics. Indeed, it models the question of assembling a genome from a set of sequencing reads. Unfortunately, SSP is known to be NP-hard even on a binary alphabet and also hard to approximate with respect to the superstring length or to the compression achieved by the superstring. Even the variant in which all words share the same length r, called r-SSP, is NP-hard whenever r > 2. Numerous involved approximation algorithms achieve approximation ratio above 2 for the superstring, but remain difficult to implement in practice. In contrast the greedy conjecture asked in 1988 whether a simple greedy agglomeration algorithm achieves ratio of 2 for SSP. Here, we present a novel approach to bound the superstring approximation ratio with the compression ratio, which leads to a first proof of the greedy conjecture for 3-SSP.

International audience; Background: Cost effective next generation sequencing technologies now enable the production of genomic datasets for many novel planktonic eukaryotes, representing an understudied reservoir of genetic diversity. O. tauri is the smallest free-living photosynthetic eukaryote known to date, a coccoid green alga that was first isolated in 1995 in a lagoon by the Mediterranean sea. Its simple features, ease of culture and the sequencing of its 13 Mb haploid nuclear genome have promoted this microalga as a new model organism for cell biology. Here, we investigated the quality of genome assemblies of Illumina GAIIx 75 bp paired end reads from Ustreococcus touri, thereby also improving the existing assembly and showing the genome to be stably maintained in culture. Results: The 3 assemblers used, ABySS, CLCBio and Velvet, produced 95% complete genomes in 1402 to 2080 scaffolds with a very low rate of misassembly. Reciprocally, these assemblies improved the original genome assembly by filling in 930 gaps. Combined with additional analysis of raw reads and PCR sequencing effort, 1194 gaps have been solved in total adding up to 460 kb of sequence. Mapping of RNAseq II lumina data on this updated genome led to a twofold reduction in the proportion of multi-exon protein coding genes, representing 19% of the total 7699 protein coding genes. The comparison of the DNA extracted in 2001 and 2009 revealed the fixation of 8 single nucleotide substitutions and 2 deletions during the approximately 6000 generations in the lab. The deletions either knocked out or truncated two predicted transmembrane proteins, including a glutamate receptor like gene. Conclusion: High coverage (>80 fold) paired end Illumina sequencing enables a high quality 95% complete genome assembly of a compact 13 Mb haploid eukaryote. This genome sequence has remained stable for 6000 generations of lab culture.

International audience; In higher plants, hermaphrodites may genetically loose their male fertility through the cytoplasmic male sterility (CMS) system. In radish, a nuclear locus, denoted Rfo, has evolved that is able to counteract the effect of CMS and restore the fertility. This locus encodes three similar genes in tandem that belong to the pentatricopeptide repeat (PPR) family and each gene encloses a tandem repeat of PPR motif. Among the hundreds of members of this family, some play a role in the post-transcriptional gene regulation in organelles (mitochondria and chloroplasts). In this study, we recently sequenced a European non-restorer allelic locus and compare it to the original Rfo restorer allele to investigate its evolutionary dynamics. We conducted bioinformatic analysis to determine the putative border of tandem duplications both at protein motif level and at gene level. Our results present the picture of complex evolution with multiple gene duplications at a fast evolving locus.

International audience; Suffix trees belong to the most studied indexing data structures for strings. Generalised suffix trees can index the substrings of a set of input words. In its construction algorithm Ukkonen used implicit suffix trees, which relax the assumption that a suffix is not a prefix of another suffix, and thus represent some suffixes by internal nodes rather than by leaves. In computational biology, for the sake of genome assembly, one wishes to assemble a target sequence from a multitude of input strings, usually called the reads. Numerous algorithms build assembly related graphs that represent the overlaps of the input reads: for instance, the overlap graph, or a special version of the De Bruijn graph, in which only k-mers occurring within the reads are represented by nodes. We address the question of algorithms for building the overlap graph and the De Bruijn graph directly from indexing data structures of the read set, and investigate it when the index in an implicit generalised suffix tree. We will present the algorithms for the De Bruijn graph and for its contracted version, and show they run in a time that is linear in the size of the index. Generally, this work establishes algorithmic paths to convert classical indexing data structures in graph representations useful for assembly. Work in collaboration with Bastien Cazaux et Thierry Lecroq.

Given a directed graph G with weights on its arcs, the Maximum Asymmetric Travelling Salesman Problem (Max- ATSP) asks for a Hamiltonian path of maximum weight covering G. Max-ATSP, a central problem in computer science, is known to NP-hard and hard to approximate. In the general case, when the Triangle Inequality is not satisfied, the best approximation ratio known to date equals 2/3. Now consider the Overlap Graph for a set of finite words P := {s1 , . . . , s p }: the directed graph in which an arc links two words with a weight equals to the length of their maximal overlap. When Max-ATSP is applied to the Overlap Graph, it solves the Maximal Compression or Shortest Superstring problem, where one searches for a string of minimal length having each input word as a substring. Again these problems are hard to approximate. Both for Max-ATSP and for Maximal Compression, good approximation algorithms use a cover of the graph by a set of cycles or of the words by a set of cyclic strings. These questions are known as Maximal Directed Cyclic Cover (MDCC) and as Shortest Cyclic Cover of Strings (SCCS), and can be solved in polynomial time. However, among these four problems, the approximation ratio achieved by a simple greedy algorithm is known only for Maximal Compression. In a seminal but complex proof, Tarhio and Ukkonen showed that it achieves 1/2 compression ratio. Taking advantage of the power of subset systems, we investigate the approximation of associated greedy algorithms for these four problems, and show they reach a ratio of 1/3 for Max- ATSP, 1/2 for Maximal Compression and for Maximal Cyclic Cover, and gives an exact solution for the Shortest Cyclic Cover of Strings. The proof for Maximal Compression is simpler than known ones. For these problems, greedy algorithms are easier to implement and often faster than existing approximation algorithms, an important fact since these problems have practical applications, for instance in data compression and computational biology.

International audience; Tandem repeats are repeated sequences whose copies are adjacent along the chromosomes. They account for large portion of eukaryotic genomes and are found in all types of living organisms. Among tandem repeats, those with repeat unit of middle size are called minisatellites. These loci depart from classical loci because of the propensity to vary in size due to the addition or the removal of one or more repeat units. Due to this polymorphism, they prove useful in genetic mapping, in population genetics, and forensic medicine. Moreover, some specific tandem repeat loci are involved in diseases, like the insulin minisatellite, which is implicated in type I diabetes and obesity. Those loci also undergo complex recombination events. Presently, some programs to compare tandem repeats alleles exist and yield good results when recombination is absent, but none correctly handles recombinant alleles. Our goal is to develop an adequate tool for the detection of recombinant among a set of minisatellite sequences. By combining a multiple alignment tool and a method based on phylogenetic profiling, we design a first solution, called {\msp}, for this task. The method has been implemented, tested on real data sets from the insulin minisatellite, and proven to detect recombinant alleles.

International audience; Profile Hidden Markov Models (pHMMs) represent sequence regions, called domains or motifs, that are conserved among the proteins of a family. They are routinely used either i/ to recognize the presence of a domain in a protein and thereby to test its membership of a known family, or ii/ to tag the precise position of a domain in the sequence. However, a majority of proteins are composed of several domains, and during evolution, events such as rearrangements or duplications may create different domain architectures in proteins of the same family. Due to their intrinsic linear structure, pHMMs cannot model several distinct domains whose number and relative order may be variable in a family. We lack efficient tools to perform recognition and tagging in the case of complex domain architectures. Here, we propose a generalized HMM to solve exactly this. In our solution, called cyclic profile HMM (CpHMM), specific transitions can model the repetition of units, as well as different relative orders of domains. In a CpHMM, complete domains are modeled by nested pHMMs. We provide a program for the construction of CpHMMs that takes as input pHMMs, thereby allowing the user to capitalized on already developed pHMMs (PFAM). We adapted recognition and tagging algorithms to CpHMMs and test them on both the family of PentatricoPeptide Repeats proteins (PPR) and on the superfamily of saposins. Our results demonstrate that CpHMMs improve on pHMMs for the recognition and tagging of proteins with complex domains architectures, while keeping their efficiency. The architecture of PPR proteins has been manually annotated for a subfamilly in arabidopsis, however only the recognition with the PFAM PPR motif has been previously performed for the rice and poplar tree. Comparing our results with the annotations of arabidopsis PPR, we show that more than 88% of the motifs are precisely recognized by the cpHMM. Moreover, we completed the recognition of PPR, as well as the determination of their architecture, for both rice and poplar tree proteomes.

International audience; Here, we consider a central notion of word combinatorics and string algorithmics: the periods of a string. A period is an offset (i.e., a shift) at which a word can overlap itself. A word may have several periods, which we call its set of periods, and distinct words of the same length may share the same period set. When denoted by a binary string, a period set is called the autocorrelation of a word. In the early 80's, Guibas and Odlyzko provided the first investigation of the structure of period sets [3, 2] and characterized them. Considering the set Gn of all period sets of strings of length n over a finite alphabet, they showed that Gn is independent of the alphabet (provided the cardinality of S >= 2). Pursuing the goal of finding an enumeration algorithm for Gn, we study further the properties of Gn and exhibit the redundancy in period sets. It enables us to introduce the notion of an irreducible period set and to elucidate the structure of both Gn and the set of all irreducible period sets, denoted Ln. We then propose the first efficient enumeration algorithm for Gn. We also exhibit a relation between the number of binary partitions of n and the number of distinct period sets (i.e., the cardinality of Gn). It allows us to improve upon the previously known asymptotic lower bounds on the cardinality of Gn [3]. Additionally, from these results we derive a new recurrence to compute the population of a period set, as well as an algorithm to sample uniformly irreducible and classical period sets. All above mentioned results were published in [6, 7]. Related entries of the Encyclopedia of Integer Sequences [8] are A018819 and A000123. This study has been extended to partial words [1]. The enumeration algorithm found applications for the computation of several statistics about the vocabulary of strings, like the number of missing words of length n in a text or the number of common words between two texts [4, 5].

International audience; With High Throughput Sequencing (HTS) technologies, biology is experiencing a sequence data deluge. A single sequencing experiment currently yields 100 million short sequences, or reads, the analysis of which demands efficient and scalable sequence analysis algorithms. Diverse kinds of applications repeatedly need to query the sequence collection for the occurrence positions of a subword. Time can be saved by building an index of all subwords present in the sequences before performing huge numbers of queries. However, both the scalability and the memory requirement of the chosen data structure must suit the data volume. Here, we introduce a novel indexing data structure, called Gk arrays, and related algorithms that improve on classical indexes and state of the art hash tables.

Poster abstract in a workshop: COST Action BM 1006 (SeqAhead): MC BUSINESS MEETING AND SCIENTIFIC MEETING; International audience; The question of read indexing remains broadly unexplored. However, the increase in sequence throughput urges for new algorithmic solutions to query large read collections efficiently. We pro- pose a solution, named Gk arrays, to index large collections of reads, an algorithm to build the structure, and procedures to query it. Once constructed, the index structure is kept in main memory and is repeatedly accessed to answer various types of queries. We compare our data structure to other possible solutions to investigate its scalability and computational efficiency. Gk arrays are im- plemented in a general purpose library, which may prove useful for assembly purposes, for evaluating the expression level in RNA-seq, and others high throughput sequencing applications.

National audience; The processing of huge collection of sequencing reads obtained with High Throughput Sequencing (HTS) technologies currently demands for their analysis complex processing pipelines and hours or even days of computing. Numerous articles present processing pipelines able to predict for genomic or transcriptomic reads one type of biological events like small mutations, insertions-deletions, rearrangements, or either normal or chimeric splice junctions (in transcriptomic data). We will present, CRAC, a new read analysis program that fulfills multiple purposes in the sense that it can predict simultaneously, in a single analysis step, the different kinds of above-mentioned biological events, including junctions of chimeric RNAs. Thus, CRAC simplifies genomic or transcriptomic read analysis from the user's point of view. It includes sequencing error detection to avoid confusion with true mutations. Moreover, integrating all predictions in a single step improves the sensitivity and specificity of the predictions. We will show that compared to other current solutions CRAC delivers multiple predictions in highly competitive computing times. CRAC constitutes the basis of a HTS analysis service available at the ATGC bioinformatics platform http://www.atgc-montpellier.fr/ngs/.

Proceeding JOBIN 2009 online Open Accès; National audience; Whole genome alignment is a challenging problem in computational comparative genomics. It is essential for the functional annotation of genomes, the understanding of their evolution, and for phylogenomics. Many global alignment programs are heuristic variations on the anchor based strategy, which relies on the initial detection of similarities and their selection in an ordered chain. Considering that alignment tools fail to align some pairs of bacterial strains, we investigate whether this is intrinsically due to the strategy or to a lack of sensitivity of the similarity detection method. For this, we implement and compare 6 programs based on three different detection methods (from exact matches to local alignments) on a large benchmark set. Our results suggest that the sensitivity of well known methods, like MGA or Mauve, can be greatly improved in the case of divergent genomes if one exploits spaced seeds at the detection phase. In other cases, such methods yield alignments that cover nearly the whole genome. Then, we focus on global reliability of alignments: should an aligned pair of segments be included in the global genome alignment? We investigate this reliability according to both the segment ”alignability” and to inclusion of orthologs. Again, we provide evidence that for both close and divergent genomes, one of our programs, YH, achieves alignments with sometimes a lower coverage, but a higher inclusion of orthologs. It opens the way to the first reliable alignments for some highly divergent species like Buchnera aphidicola or Prochlorococcus marinus.

National audience; Next-generation sequencing technologies, able to yield millions of sequences in a single run, allow to interrogate the transcriptome or to assay protein-DNA interactions (by Chromatin ImmunoPrecipitation by sequencing or ChIP-seq) at a genome-wide scale. These assays yield short sequences (

Special issue : Abstracts of the 3rd MC-GARD Meeting; International audience; The transcriptome or the interactome at unprecedented depth. These techniques yield short sequence reads that are then mapped on a genome sequence to predict putatively transcribed or protein-interacting regions. We argue that factors such as false locations, sequence errors, and read length impact on the mapping prediction capacity of these short reads. Here we suggest a computational approach to measure those factors and analyse their influence on both transcriptomic and epigenomic assays. This investigation provides new clues on both methodological and biological issues. First, we estimate that 4.6% of reads are affected by SNPs. Second, we show that the nucleotide error probability is low, and it significantly increases with the position in the sequence. Third, by choosing a read length above 19 bp, we practically eliminates the risk of finding irrelevant positions. However, the number of uniquely mapped reads decreases with sequences above 20 bp. Following our procedure, we obtain 0.6% of false positives among genomic locations. Therefore, even rare signatures, if they are mapped on the genome, should identify biologically relevant regions. This indicates that digital transcriptomics may help to characterise the wealth of yet undiscovered, low abundance transcripts.

International audience; Next-generation sequencing technologies, able to yield millions of sequences in a single run, allow to interrogate the transcriptome or to assay protein-DNA interactions (by Chromatin ImmunoPrecipitation by sequencing or ChIP-seq) at a genome-wide scale. These assays yield short sequences (

International audience; Analysis of several million expressed gene signatures (tags) revealed an increasing number of different sequences, largely exceeding that of annotated genes in mammalian genomes. Serial Analysis of Gene Expression (SAGE) can reveal new RNAs transcribed from previously unrecognized genomic regions. However, conventional SAGE tags are too short to identify unambiguously unique sites in large genomes. Here, we design a novel strategy with tags anchored on two different restrictions sites of cDNAs. New transcripts are then tentatively defined by the two SAGE tags in tandem and by the spanning sequence read on the genome between these tagged sites. Having developed a new algorithm to locate these tag-delimited genomic sequences, we first validated its capacity to recognize known genes and its ability to reveal new transcripts with two SAGE libraries built in parallel from a single RNA sample. Our algorithm proves fast enough to experiment this strategy at a large scale. We then collected and processed the complete sets of human SAGE tags to predict yet unknown transcripts. A cross-validation with tiling arrays data shows that 47%of these tag-delimited genomic sequences overlap transcriptional active regions. Our method provides a new and complementary approach for complex transcriptome annotation.

International audience; The tetranucleotide microsatellite locus Spl-106 has been widely used as a molecular marker in sturgeon studies. To investigate the evolutionary process of this highly variable locus in Acipenseriforms, cross-species amplifications were performed in 130 individuals from 15 species and successful in 13 species. All PCR products were sequenced. According to the flanking sequences, a total of 94 alleles at locus Spl-106 were found in 11 out of 13 species. Twenty-three haplotypic flanking sequences were detected and four of them are dominant types present in 70 out of 94 alleles. Two of the dominant types are species-specific types, and the other two are composed of alleles from species of the Pacific and Atlantic lineages, respectively. The repeat region evolved synchronously with the flanking region. The Atlantic clade was also found in the genealogy tree of the repeat region constructed using the MS Align method. Although the basic repeat structure was variable, several alleles were highly conserved among species and evolved independently. The evolutionary process of this locus in Acipenseriforms was reconstituted from a single repeat (TAGA)n to compound repeats (TAGA)n(TAAA)m, then to another single repeat (TAAA)n, and finally to a totally new compound repeat structure (TAAA)m(GAAA)n. Reciprocally, for the sturgeon phylogeny, our results suggest that Acipenser sturio diverged earlier than Schphirhynchus platorynchus, and infirm the Huso genus, since the two Huso species are classified within the Acipenser species of the Pacific and Atlantic lineages, respectively. Moreover, the sequence information also supports the close relationship between A. sinensis and A. dabryanus, and the relationships among A. transmontanus, A. schrenckii, and H. dauricus.

International audience

Four hypervariable minisatellite loci were scored on a panel of 116 individuals of various geographical origins representing a large part of the diversity present in House Mouse subspecies. Internal structures of alleles were determined by Minisatellite Variant Repeat mapping PCR (MVR-PCR), to produce maps of intermingled patterns of variant repeats along the repeat array. To reconstruct the genealogy of these arrays of variable length, the specifically designed software MS_Align was used to estimate molecular divergences, graphically represented as neighbour-joining trees. Given the high haplotypic diversity detected (mean He=0.962), these minisatellite trees proved to be highly informative for tracing past and present genetic exchanges. Examples of identical or nearly identical alleles were found across subspecies and in geographically very distant locations while monophyly was only detected for the X-chromosome locus MMS30 in M. m. musculus, This lack of complete lineage sorting and fits well with the likely phylogeographic scenario according to which M. m. castaneus is a recent offshoot from the so-called central populations that would have occupied the speciesÕ ancestral range, while M. m. domesticus and M. m. musculus would have diverged earlier when migrating out of it. This strongly suggests that, at least for the chromosomal regions under scrutiny, wild House Mice subspecies constitute a set of interrelated gene pools still connected through long range gene flow or genetic exchanges occurring in the various contact zones existing nowadays or having existed in the past. Identifying genomic regions that do not follow this pattern will be a challenging task for pinpointing genes important for speciation.

National audience; The sequential analysis of several million expressed gene signatures (tags) has revealed an increasing number of different sequences, largely exceeding the number of annotated gene loci in mammalian genomes. Serial Analysis of Gene Expression (SAGE) has the potential to reveal new polyadenylated RNAs transcribed from previously unrecognized chromosomal sites. However, conventional SAGE tags are not long enough to identify unambiguously unique sites in large genomes. In this work, we design a novel strategy in which two SAGE libraries are built in parallel from the same polyadenylated RNA sample, with tags anchored on two different restrictions sites of cDNAs. New transcripts are then tentatively defined by the two SAGE tags in tandem and by the spanning sequence read on the genome between the two tagged sites. Having developed a new algorithm to obtain these tag-delimited genomic sequences (TDGS), we evaluated its capacity to recognize already known genes and its ability to reveal new transcripts. This new strategy extends the power of tag-based approaches when dealing with complex genomes.

National audience; Four hypervariable minisatellite loci were scored on a panel of 116 individuals of various geographical origins representing a large part of the diversity present in House Mouse subspecies. Internal structures of alleles were determined by Minisatellite Variant Repeat mapping PCR (MVR-PCR), to produce maps of intermingled patterns of variant repeats along the repeat array. To reconstruct the genealogy of these arrays of variable length, the specifically designed software MS_Align was used to estimate molecular divergences, graphically represented as neighbour-joining trees. Given the high haplotypic diversity detected (mean He=0.962), these minisatellite trees proved to be highly informative for tracing past and present genetic exchanges. Examples of identical or nearly identical alleles were found across subspecies and in geographically very distant locations while monophyly was only detected for the X-chromosome locus MMS30 in M. m. musculus, This lack of complete lineage sorting and fits well with the likely phylogeographic scenario according to which M. m. castaneus is a recent offshoot from the so-called central populations that would have occupied the speciesÕ ancestral range, while M. m. domesticus and M. m. musculus would have diverged earlier when migrating out of it. This strongly suggests that, at least for the chromosomal regions under scrutiny, wild House Mice subspecies constitute a set of interrelated gene pools still connected through long range gene flow or genetic exchanges occurring in the various contact zones existing nowadays or having existed in the past. Identifying genomic regions that do not follow this pattern will be a challenging task for pinpointing genes important for speciation.

National audience; The Rfo locus, first described in Asian radish cultivars and later introduced into Brassica, is involved in the restoration of fertility in the Ogura cytoplasmic male sterility system (CMS). CMS systems are constituted of two actors: a mitochondrial protein that causes male sterility and a nuclear gene that encodes a mitochondria-targeted protein able to impair the expression of the sterility gene. The nuclear restorer gene in the Rfo-Ogura system, as all identified restorer genes (with the only exception of the Rf2 Texas maize restorer), encodes a protein belonging to the pentatricopeptide repeat (PPR) family. The PPR gene family is a very large family in plants, with about 450 members in A. thaliana, and their function is largely unknown, although some members have proven to play roles in posttranscriptional organelle gene regulation. Recent studies analyzing chromosomes regions with duplicated PPR genes (allelic variants of a restorer locus in rice and two chromosome regions in A. thaliana) suggest revealed high levels of recombination in these regions. In addition, restorer genes (because of their ability to adapt to specificity changing/fast evolving targets) are evolved in a similar way as “resistant genes”. Anyway, evolutionary dynamics of these loci is largely unknown so far. In the Rfo region, the restorer gene seems to be duplicated too: three genes encoding highly related PPR proteins are present in the Rfo locus (even if just one of the proteins is able to restorer fertility). We recently sequenced a European non-restorer allelic locus. Analysis of this sequence shows the presence of only two PPR genes in an apparently very dynamic region. In this study, we analyzed the European allelic variant sequence of the Rfo locus and the possible evolutionary events that occurred in both loci, in order to give insight into the dynamics and evolution of the Rfo locus.

International audience; Four hypervariable minisatellite loci were scored on a panel of 116 individuals of various geographical origins representing a large part of the diversity present in House Mouse subspecies. Internal structures of alleles were determined by Minisatellite Variant Repeat mapping PCR (MVR-PCR), to produce maps of intermingled patterns of variant repeats along the repeat array. To reconstruct the genealogy of these arrays of variable length, the specifically designed software MS_Align was used to estimate molecular divergences, graphically represented as neighbour-joining trees. Given the high haplotypic diversity detected (mean He=0.962), these minisatellite trees proved to be highly informative for tracing past and present genetic exchanges. Examples of identical or nearly identical alleles were found across subspecies and in geographically very distant locations while monophyly was only detected for the X-chromosome locus MMS30 in M. m. musculus, This lack of complete lineage sorting and fits well with the likely phylogeographic scenario according to which M. m. castaneus is a recent offshoot from the so-called central populations that would have occupied the speciesÕ ancestral range, while M. m. domesticus and M. m. musculus would have diverged earlier when migrating out of it. This strongly suggests that, at least for the chromosomal regions under scrutiny, wild House Mice subspecies constitute a set of interrelated gene pools still connected through long range gene flow or genetic exchanges occurring in the various contact zones existing nowadays or having existed in the past. Identifying genomic regions that do not follow this pattern will be a challenging task for pinpointing genes important for speciation.

National audience; Background: Four hypervariable minisatellite loci were scored on a panel of 116 individuals of various geographical origins representing a large part of the diversity present in House Mouse subspecies. Internal structures of alleles were determined by Minisatellite Variant Repeat mapping PCR (MVR-PCR), to produce maps of intermingled patterns of variant repeats along the repeat array. To reconstruct the genealogy of these arrays of variable length, the specifically designed software MS_Align was used to estimate molecular divergences, graphically represented as neighbour-joining trees. Results: Given the high haplotypic diversity detected (mean He=0.962), these minisatellite trees proved to be highly informative for tracing past and present genetic exchanges. Examples of identical or nearly identical alleles were found across subspecies and in geographically very distant locations, together with a poor lineage sorting among subspecies except for the X chromosome locus MMS30 in M. m. musculus. Given the high mutation rate of mouse minisatellite loci, this picture cannot be interpreted only with simple splitting events followed by retention of polymorphism, but implies recurrent gene flow between already differentiated entities. Conclusion: This strongly suggests that, at least for the chromosomal regions under scrutiny, wild House Mice subspecies constitute a set of interrelated gene pools still connected through long range gene flow or genetic exchanges occurring in the various contact zones existing nowadays or having existed in the past. Identifying genomic regions that do not follow this pattern will be a challenging task for pinpointing genes important for speciation.

International audience; Tandemly repeated sequences are ubiquitous components of both prokaryotic and eukaryotic genomes. Renowned examples of tandem repeats (TR) include micro-satellites, mini-satellites, or satellite DNA, as well as tandemly repeated genes. The evolutionary event that giveq rise to tandem repeats, tandem duplication, is major force that drives the formation of gene families and the evolution of the genome shape. The remarkable feature of some tandem repeats is their polymorphism: the number of copies evolve through tandem duplication or contraction that add or remove copies to the array. The polymorphism can also modify the arrangements of the variants of the repeat along the array by interleaving point mutations and duplications. This variability has dramatic effects when the TR is included in a gene or in its regulation region, as exemplified by the triplet-repeat neurodegenerative diseases in human or some diseases induced by minisatellite. In population genetics, tandem repeats polymorphism made them extremly useful markers to detect genetic variations between species, inside a population, or even between individuals for the most polymorphic ones. In this talk, we will consider two problematics in the analysis of these sequences: first, the search for tandem repeats in genomes, and second, the comparison of tandem repeat alleles to understand their evolution. We will describre algorithmical solutions for these questions and present their applications in the analysis of the evolution of the Mouse genome, as well as of a large plant specific protein family.

Recently, experiments based on tiling arrays have revealed the huge difference between number of active transcripts and the number of annotated genes. This discrepancy is not only due to differentially spliced variants, since many active transcriptional units were predicted far apart from genes. We are thus confronted to the challenge of annotating and characterizing more precisely the human transcriptome. For this purpose, approaches based on the sequencing of transcript signatures, like SAGE, which yield one tag par transcript expressed in the cell, do not provide enough sequence information per transcript to allow finding the unique corresponding loci on the genome. Indeed, on the human genome conventional SAGE tags (14 bps) occur in average more than 3000 times (theoretically), while long SAGE tags (21 bps) match a unique location in only 49% of the cases. To address this annotation challenge, we designed a novel strategy in which two SAGE libraries are built in parallel from the same polyadenylated RNA sample, with tags anchored on two different restrictions sites of cDNAs. In other words, the experiment yields per transcript two tags (14 bps) anchored at different positions on the transcript (the first NlaIII and the first Sau3A restriction sites starting from the 3' end), but the association of these is unknown. Among the many tags of each sort obtained by sequencing the libraries, one does not know a priori which pair corresponds to which transcript. We developed a fast program to find these associated pairs, called tandem tags, on the genome sequence. We first tested our strategy using two small twin SAGE libraries prepared from a unique RNA sample extracted from terminally differentiated macrophages. These two SAGE datasets were first used to assemble a set of 489 pairs mapping on well annotated human transcript sequences. This set enables us to evaluate the ability of our method to recover the genome locus from which each known transcript originates. In the remaining SAGE sets, we selected the subsets of tags that are not linked in any way to known transcripts, and searched on the genome for compound pairs of tags. This yields a set of 250 tag-delimited genomic sequences (TDGS), which were then investigated in silico, and for a selection, tested in vitro to see if they reveal unknown transcripts. When dealing with complex genomes, the results shows that this strategy improves on classical tag based approaches for the identification of novel transcript units.

Proteins are composed of structural units, called domains, which can be detected using computational methods. In many families, proteins contain several domains, or several conserved sequence parts, called motifs. During the evolution, rearrangements (swaps or circular permutations) may alter the relative order of these units (domains or motifs) [Bornberg et al. 05], while tandem duplications can change their number. In a family, it results in a variable organization of the units along the chain. Profile HMMs (pHMMs) are the preferred models to represent motifs or domains. They serve to recognize new members of a protein family. Profile HMMs have a linear structure which can model a single unit, and if iterated they can detect repeats of this unit. To perform a "multiple tagging", that is to identify the sequence regions corresponding to each possible motif, one needs to combine the results of each pHMM. This was done following heuristic criteria (e.g., choosing the best scoring motif when the detections overlap). Up to now, we lack a method to perform a multiple tagging automatically and optimally according to a global criterion. To solve this problem, we generalize pHMMs to a novel structure called Cyclic Profile HMMs (CpHMMs), which can predict the most probable motif organization of a protein. It can cope with repeated units whose number varies, and with changes in the relative order of the units. We used CpHMMs to tag multiple motifs in the Pentatrico-Peptide Repeats (PPR) protein family of plants. PPR proteins contain tandem repeats of PPR motifs (named P, L, S) as well as other motifs (E, E+, Dyw). Half of the PPR proteins form the PPRP subfamily, while the other half is represented by the PCMP subfamily. PPRPs can be defined using a PROSITE like regular expression where letters represent motifs: (P*-S*)*, and the organization of PCMPs is described by: (P-L-S*)*-[E-[E+ -[Dyw]]] [Lurin et al. 04]. We used the motifs pHMMs as input to build a CpHMM that can process the entire motif sequence. It allows to obtain the globally optimal "multiple tagging" solution and also measures its statistical significance. Thus, we obtained an automatic, "multiple tagging" tool and applied it first to the Arabidopsis PCMP subfamily. We validated our results compared to the manual motif annotation available for the PCMPs of Arabidopsis and found less than 10% discordance. We were able to retrieve the expected PCMP classes distribution [Rivals et al. 06]. After this validation, we used our tool to annotate the PPRP subfamily in Arabidopsis and to perform the first motif annotation of the complete PPR family of rice (522 proteins). This allows to compare the PPR motif organization between the model plants of monocotyledons and dicotyledons. In conclusion, we prove the capacity of the CpHMM structure to solve the problem of "multiple tagging" and verified its efficiency for a large number of sequences. CpHMMs are a versatile structure that adapts to new situations, like the PPR family of other species, or even to other protein families with complex unit organization (eg leucine rich repeats). In future work, we will concentrate on the fine identification of new subfamilies.

Conférence invité; National audience