Publications
Browse by date Browse by category

2017
 Peerreviewed journal articles

Briefings in Bioinformatics, Oxford University Press (OUP), To appear 2017 [hal]Résumé (cliquer pour lire). Computational programs for predicting RNA sequences with desired folding properties have been extensively developed and expanded in the past several years. Given a secondary structure, these programs aim to predict sequences that fold into a target minimum free energy secondary structure, while considering various constraints. This procedure is called inverse RNA folding. Inverse RNA folding has been traditionally used to design optimized RNAs with favorable properties, an application that is expected to grow considerably in the future in light of advances in the expanding new fields of synthetic biology and RNA nanostructures. Moreover, it was recently demonstrated that inverse RNA folding can successfully be used as a valuable preprocessing step in computational detection of novel noncoding RNAs. This review describes the most popular freeware programs that have been developed for such purposes, starting from RNAinverse that was devised when formulating the inverse RNA folding problem. The most recently published ones that consider RNA secondary structure as input are antaRNA, RNAiFold and IncaRNAfbinv, each having different features that could be beneficial to specific biological problems in practice. The various programs also employ distinct approaches, ranging from antcolony optimization to constraint programming, in addition to adaptive walk, simulated annealing and Boltzmann sampling. This review compares between the various programs and provides a simple description of the various possibilities that would benefit practitioners in selecting the most suitable program. It is geared for specific tasks requiring RNA design based on input secondary structure, with an outlook towards the future of RNA design programs.

 Miscellaneous & Submitted

[hal]Résumé (cliquer pour lire). Let $S_n$ denote the network of all RNA secondary structures of length $n$, in which undirected edges exist between structures $s$, $t$ such that $t$ is obtained from $s$ by the addition, removal or shift of a single base pair. Using contextfree grammars, generating functions and complex analysis, we show that the asymptotic average degree is $O(n)$ and that the asymptotic clustering coefficient is $O(1/n)$, from which it follows that the family $S_n$, $n = 1, 2, 3,\ldots$ of secondary structure networks is not smallworld.

 Peerreviewed journal articles

2016
 Peerreviewed journal articles

Nucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 44(11):e104  e104 pp, 2016 [doi] [hal] [pubmed]Résumé (cliquer pour lire). Systematic structure probing experiments (e.g. SHAPE) of RNA mutants such as the mutateandmap protocol give us a direct access into the genetic robustness of ncRNA structures. Comparative studies of homologous sequences provide a distinct, yet complementary, approach to analyze structural and functional properties of noncoding RNAs. In this paper, we introduce a formal framework to combine the biochemical signal collected from mutateandmap experiments, with the evolutionary information available in multiple sequence alignments. We apply neutral theory principles to detect complex longrange dependencies between nucleotides of a single stranded RNA, and implement these ideas into a software called aRNhAck. We illustrate the biological significance of this signal and show that the nucleotides networks calculated with aRNhAck are correlated with nucleotides located in RNARNA, RNAprotein, RNADNA and RNAligand interfaces. aRNhAck is freely available at http://csb.cs.mcgill.ca/arnhack. 
The BRaliBase denta tale of benchmark design and interpretation.Briefings in Bioinformatics, Oxford University Press (OUP), To appear 2016 [doi] [hal] [pubmed]Résumé (cliquer pour lire). BRaliBase is a widely used benchmark for assessing the accuracy of RNA secondary structure alignment methods. In most case studies based on the BRaliBase benchmark, one can observe a puzzling drop in accuracy in the 40%60% sequence identity range, the socalled “BRaliBase Dent”. In the present note, we show this dent is due to a bias in the composition of the BRaliBase benchmark, namely the inclusion of a disproportionate number of tRNAs, which exhibit a very conserved secondary structure. Our analysis, aside of its interest regarding the specific case of the BRaliBase benchmark, also raises important questions regarding the design and use of benchmarks in computational biology. 
ecceTERA: comprehensive gene treespecies tree reconciliation using parsimony.Bioinformatics (Oxford, England), 20568 pp, 2016 [hal] [pubmed]Résumé (cliquer pour lire). A gene treespecies tree reconciliation explains the evolution of a gene tree within the species tree given a model of genefamily evolution. We describe ecceTERA, a program that implements a generic parsimony reconciliation algorithm, which accounts for gene duplication, loss and transfer (DTL) as well as speciation, involving sampled and unsampled lineages, within undated, fully dated or partially dated species trees. The ecceTERA reconciliation model and algorithm generalize or improve upon most published DTL parsimony algorithms for binary species trees and binary gene trees. Moreover, ecceTERA can estimate accurate speciestree aware gene trees using amalgamation.ecceTERA is freely available under http://mbb.univmontp2.fr/MBB/download_sources/16__ecceTERA and can be run online at http://mbb.univmontp2.fr/MBB/subsection/softExec.php?soft=eccetera 
Algorithmica, Springer Verlag, To appear 2016 [hal]Résumé (cliquer pour lire). We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal freeenergy structure. We consider two freeenergy models where the contributions of base pairs are additive and independent: the purely combinatorial WatsonCrick model, which only allows equallycontributing A − U and C − G base pairs, and the realvalued NussinovJacobson model, which associates arbitrary energies to A − U, C − G and G − U base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the fourletter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in Θ(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structureapproximating relaxation of the design, and provide a Θ(n) algorithm which, given a structure S that avoids two trivially nondesignable motifs, transforms S into a designable structure constructively by adding at most one basepair to each of its stems. 
Nucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 44(W1):W308  W314 pp, 2016 [doi] [hal]Résumé (cliquer pour lire). In recent years, new methods for computational RNA design have been developed and applied to various problems in synthetic biology and nanotechnology. Lately, there is considerable interest in incorporating essential biological information when solving the inverse RNA folding problem. Correspondingly, RNAfbinv aims at including biologically meaningful constraints and is the only program todate that performs a fragmentbased design of RNA sequences. In doing so it allows the design of sequences that do not necessarily exactly fold into the target, as long as the overall coarsegrained tree graph shape is preserved. Augmented by the weighted sampling algorithm of incaRNAtion, our web server called incaRNAfbinv implements the method devised in RNAfbinv and offers an interactive environment for the inverse folding of RNA using a fragmentbased design approach. It takes as input: a target RNA secondary structure; optional sequence and motif constraints; optional target minimum free energy, neutrality, and GC content. In addition to the design of synthetic regulatory sequences, it can be used as a preprocessing step for the detection of novel natural occurring RNAs. The two complementary methodologies RNAfbinv and incaRNAtion are merged together and fully implemented in our web server incaRNAfbinv, available at http://www.cs.bgu. ac.il/incaRNAfbinv.

 Conferences with proceedings

Proceedings of ALCOB  3rd International Conference on Algorithms for Computational Biology  2016, Spain, 2016 [hal]Résumé (cliquer pour lire). Pairwise ordered tree alignment are combinatorial objects that appear in RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis.In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a contextfree grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees $S$ and $T$. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the GibbsBoltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal RNA secondary structures alignments. 
Proceedings of GASCOM  10th conference on random generation of combinatorial structures  2016, France, Electronic Notes in Discrete Mathematics, 2016 [hal]Résumé (cliquer pour lire). A lattice walk model is said to be reluctant if the defining step set has a strong drift towards the boundaries. We describe efficient random generation strategies for these walks.

 Conferences without proceedings and/or unrefereed

Proceedings of JOBIM  Journées Ouvertes en Biologie, Informatique et Mathématiques  2016, France, 2016 [hal]Résumé (cliquer pour lire). NextGeneration Sequencing (NGS) technologies have opened new perspectives to refine the process of predicting the secondary structure(s) of structured noncoding RNAs. Herein, we describe an integrated modeling strategy, based on the SHAPE chemistry, to infer structural insight from deep sequencing data. Our approach is based on a pseudoenergy minimization, incorporating additional information from evolutionary data (compensatory mutations) and SHAPE experiments (reactivity scores) within an iterative procedure. Preliminary results reveal conserved and stable structures within UTRs of the Ebola Genome, that are both thermodynamicallystable and highly supported by SHAPE accessibility analysis. 
Proceedings of JOBIM  Journées Ouvertes en Biologie, Informatique et Mathématiques  2016, France, 2016 [hal]Résumé (cliquer pour lire). Aligning macromolecules such as proteins, DNAs and RNAs in order to reveal, or conversely exploit, their functional homology is a classic challenge in bioinformatics, with farreaching applications in structure modelling and genome annotations. In the specific context of complex RNAs, featuring pseudoknots, multiple interactions and noncanonical base pairs, multiple algorithmic solutions and tools have been proposed for the structure/sequence alignment problem. However, such tools are seldom used in practice, due in part to their extreme computational demands, and because of their inability to support general types of structures. Recently, a general parameterized algorithm based on tree decomposition of the query structure has been designed by Rinaudo et al. We present an implementation of the algorithm within a tool named LiCoRNA. We compare it against stateoftheart algorithms. We show that it both gracefully specializes into a practical algorithm for simple classes pseudoknot, and offers a general solution for complex pseudoknots, which are explicitly outofreach of competing softwares.

 Peerreviewed journal articles

2015
 Peerreviewed journal articles

Evolution of genes neighborhood within reconciled phylogenies: an ensemble approachBMC Bioinformatics, BioMed Central, 16(Suppl 19):S6 pp, 2015 [doi] [hal]Résumé (cliquer pour lire). CONTEXT:The reconstruction of evolutionary scenarios for whole genomesin terms of genome rearrangements is a fundamental problem in evolutionaryand comparative genomics. The DeCo algorithm, recently introducedby Berard et al., computes parsimonious evolutionary scenarios forgene adjacencies, from pairs of reconciled gene trees. However, asfor many combinatorial optimization algorithms, there can exist manycooptimal, or slightly suboptimal, evolutionary scenarios thatdeserve to be considered.CONTRIBUTION:We extend the DeCo algorithmto sample evolutionary scenarios from the whole solution space underthe Boltzmann distribution, and also to compute Boltzmann probabilitiesfor specific ancestral adjacencies.RESULTS:We apply our algorithmsto a dataset of mammalian gene trees and adjacencies, and observea significant reduction of the number of syntenic conflicts observedin the resulting ancestral gene adjacencies.

 Conferences with proceedings

Proceedings of ISBRA  11th International Symposium on Bioinformatics Research and Applications  2015, United States, 2015 [hal]Résumé (cliquer pour lire). The availability of a large number of assembled genomes opens the way to study the evolution of syntenic character within a phylogenetic context. The DeCo algorithm, recently introduced by Bérard et al. allows the computation of parsimonious evolutionary scenarios for gene adjacencies, from pairs of reconciled gene trees. Following the approach pioneered by Sturmfels and Pachter, we describe how to modify the DeCo dynamic programming algorithm to identify classes of cost schemes that generates similar parsimonious evolutionary scenarios for gene adjacencies, as well as the robustness to changes to the cost scheme of evolutionary events of the presence or absence of specific ancestral gene adjacencies. We apply our method to six thousands mammalian gene families, and show that computing the robustness to changes to cost schemes provides new and interesting insights on the evolution of gene adjacencies and the DeCo model. 
Proceedings of CPM  26th Annual Symposium on Combinatorial Pattern Matching, Italy, 2015 [hal]Résumé (cliquer pour lire). In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem which aims at finding a sequence that admits a given target as its unique base pair maximizing structure. We provide complete characterizations for the structures that can be designed using restricted alphabets. Under a classic fourletter alphabet, we provide a complete characterization of designable structures without unpaired bases. When unpaired bases are allowed, we provide partial characterizations for classes of designable/undesignable structures, and show that the class of designable structures is closed under the stutter operation. Membership of a given structure to any of the classes can be tested in linear time and, for positive instances, a solution can be found in linear time. Finally, we consider a structureapproximating version of the problem that allows to extend bands (helices) and, assuming that the input structure avoids two motifs, we provide a lineartime algorithm that produces a designable structure with at most twice more base pairs than the input structure.

 Book chapters & Editorials

RNA Bioinformatics, Editor(s) Ernesto Picardi, Methods in Molecular Biology, Springer New York, 63100 pp, 2015 [doi] [hal] [pubmed]Résumé (cliquer pour lire). Secondary structure diagrams are essential, in RNA biology, to communicate functional hypotheses and summarize structural data, and communicate them visually as drafts or finalized publicationready figures. While many tools are currently available to automate the production of such diagrams, their capacities are usually partial, making it hard for a user to decide which to use in a given context. In this chapter, we guide the reader through the steps involved in the production of expressive publicationquality illustrations featuring the RNA secondary structure. We present major existing representations and layouts, and give precise instructions to produce them using available free software, including jViz.RNA, the PseudoViewer, RILogo, Rchie, RNAplot, R2R, and VARNA. We describe the file formats and structural descriptions accepted by popular RNA visualization tools. We also provide command lines and Python scripts to ease the user's access to advanced features. Finally, we discuss and illustrate alternative approaches to visualize the secondary structure in the presence of probing data, pseudoknots, RNARNA interactions, and comparative data. 
Preface. Extended versions of selected papers presented at Computational methods for Structural RNAs (CMSR'14)Computational methods for Structural RNAs (CMSR'14), Journal of Computational Biology, Mary Ann Liebert, 189 pp, 2015 [hal] [pubmed]Résumé (cliquer pour lire). This preface introduces to the extended versions of selected papers presented at Computational methods for Structural RNAs (CMSR'14)

 Conferences without proceedings and/or unrefereed

Résultats algorithmiques pour le design d’ARN avec contraintes de séquenceProceedings of SeqBio 2015, France, 2015 [hal]Résumé (cliquer pour lire). Le problème du design consiste à concevoir une ou des séquences d’ARN qui vont, dans un modèleénergétique, se replier en une structure cible. Les algorithmes déjà existants dans le domaine negèrent pour la plupart pas l’ajout au problème des contraintes de séquence, c’estàdire l’interdictionou l’obligation d’utiliser certains motifs.Zhou et al. (2013) ont proposé un algorithme qui utilise de la génération aléatoire dans un langageformel conditionné par un automate fini qui gère les contraintes de motifs interdits/imposés et unegrammaire non contextuelle qui gère les contraintes imposées par la structure recherchée.On propose ici de se baser sur cet algorithme en y ajoutant des optimisations permettant de réduiresa complexité. Ce travail soulève également des questions ouvertes sur la construction efficace d’unautomate (quasi) minimal, ainsi que l’incorporation de contraintes supplémentaires garantissant lerepliement des séquences engendrées vers une structure cible à l’exclusion de tout autre repliement.

 Peerreviewed journal articles

2014
 Conferences with proceedings

Proceedings of BSB  Brazilian Symposium on Bioinformatics  2014, Brazil, Advances in Bioinformatics and Computational Biology, Springer, 8826:4956 pp, 2014 [doi] [hal]Résumé (cliquer pour lire). We consider a recently introduced dynamic programming scheme to compute parsimonious evolutionary scenarios for gene adjacencies. We extend this scheme to sample evolutionary scenarios from the whole solution space under the Boltzmann distribution. We apply our algorithms to a dataset of mammalian gene trees and adjacencies, and observe a significant reduction of the number of syntenic inconsistencies observed in the resulting ancestral gene adjacencies.

 Book chapters & Editorials

1024  Bulletin de la société informatique de France, Editor(s) Eric Sopena, SIF, 2353 pp, 2014 [hal]Résumé (cliquer pour lire). Nous présentons l'histoire et les développements récents de la recherche en bioinformatique des ARN, en insistant particulièrement sur sa dimension algorithmique, ainsi que sur les nombreuses et fructueuses interactions avec d'autres sciences qui jalonnent son histoire.

 Edited books

Proceedings of the 1st workshop on Computational Methods for Structural RNAsEditor(s) Jossinet, Fabrice & Ponty, Yann & Waldispühl, Jérôme, McGill University, ISBN 9782955018705, 2014 [doi] [hal]Résumé (cliquer pour lire). Ribonucleic acids (RNAs) play key roles in various aspects of the gene transcription and regulation processes, and are the focus of an everincreasing interest in all areas of molecular biology. Deciphering the function of a nonprotein coding RNA requires an intimate knowledge of its structure, motivating the development of structurecentric methods. This volume contains original peerreviewed contributions and invited communications presented at "CMSR'14: Computational Methods for Structural RNAs" held on September 7, 2014 in Strasbourg. This event was hosted as an official workshop of ECCB'14: 13th European Conference on Computational Biology.Proceedings are freely downloadable at http://cmsr14.cs.mcgill.ca/

 Miscellaneous & Submitted

[hal]Résumé (cliquer pour lire). Reconstruction of the evolutionary history of genomic characters along a given species tree is a longstanding problem in computational biology, with efficient algorithms to compute parsimonious scenarios for many types of characters, as in the cases of genes and genomes sequences, gene content, and gene family evolution. Recently, Bérard et al. extended the corpus of such results to syntenic characters, as they introduced the notion of adjacency forest, that models the evolution of gene adjacencies within a phylogeny, and described an efficient dynamic programming (DP) algorithm, called DeCo (Berard et al, ECCB 2012), to compute parsimonious adjacency evolutionary histories. Applying the classical parsimonybased approach of DeCo to a dataset of over 6,000 pairs of mammalian gene trees yielded a significant number of ancestral genes involved in more than two adjacencies, which correspond to syntenic inconsistencies.Recently, more general approaches for parsimony problems have been analyzed, either exploring a wider range of parameters, or considering several alternate histories for a given instance. Our work seeks to address the syntenic inconsistencies of DeCo by extending their DP scheme toward an exploration of the whole solution space of adjacency histories, under the Boltzmann probability distribution, that assigns a probability to each solution defined in terms of its parsimony score. This principle has been applied in several contexts and is sometimes known as the “Boltzmann ensemble approach”.While this Boltzmann ensemble approach has been used for a long time in RNA structure analysis, to the best of our knowledge it is not the case in comparative genomics, where exact probabilistic models have been favored as increasing computational capacities allow them to handle realistic datasets. However, such a probabilistic model does not exist so far for gene adjacencies, which motivates our work.We first show that by sampling adjacencies histories under a Boltzmann distribution that favors cooptimal histories and conserving only frequent ancestral adjacencies, we can reduce significantly the number of syntenic inconsistencies. We also implement a inside/outside variant for DeCo, that computes the actual probabilities of each individual adjacency considered under the Boltzmann distribution.

 Conferences with proceedings

2013
 Peerreviewed journal articles

Theoretical Computer Science, Elsevier, 502:177194 pp, 2013 [doi] [hal]Résumé (cliquer pour lire). We address the nonredundant random generation of $k$ words of length $n$ in a contextfree language. Additionally, we want to avoid a predefined set of words. We study a rejectionbased approach, whose worstcase time complexity is shown to grow exponentially with $k$ for some specifications and in the limit case of a coupon collector. We propose two algorithms respectively based on the recursive method and on an unranking approach. We show how careful implementations of these algorithms allow for a nonredundant generation of $k$ words of length $n$ in $\mathcal{O}(k\cdot n\cdot \log{n})$ arithmetic operations, after a precomputation of $\Theta(n)$ numbers. The overall complexity is therefore dominated by the generation of $k$ words, and the nonredundancy comes at a negligible cost. 
A weighted sampling algorithm for the design of RNA sequences with targeted secondary structure and nucleotide distribution.Bioinformatics, Oxford University Press (OUP), 29(13):i30815 pp, 2013 [doi] [hal] [pubmed]Résumé (cliquer pour lire). MOTIVATIONS: The design of RNA sequences folding into predefined secondary structures is a milestone for many synthetic biology and gene therapy studies. Most of the current software uses similar local search strategies (i.e. a random seed is progressively adapted to acquire the desired folding properties) and more importantly do not allow the user to control explicitly the nucleotide distribution such as the GCcontent in their sequences. However, the latter is an important criterion for largescale applications as it could presumably be used to design sequences with better transcription rates and/or structural plasticity. RESULTS: In this article, we introduce IncaRNAtion, a novel algorithm to design RNA sequences folding into target secondary structures with a predefined nucleotide distribution. IncaRNAtion uses a global sampling approach and weighted sampling techniques. We show that our approach is fast (i.e. running time comparable or better than local search methods), seedless (we remove the bias of the seed in local search heuristics) and successfully generates highquality sequences (i.e. thermodynamically stable) for any GCcontent. To complete this study, we develop a hybrid method combining our global sampling approach with local search strategies. Remarkably, our glocal methodology overcomes both local and global approaches for sampling sequences with a specific GCcontent and target structure. AVAILABILITY: IncaRNAtion is available at csb.cs.mcgill.ca/incarnation/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. 
Journal of Computational Biology, Mary Ann Liebert, 20(11):90519 pp, 2013 [doi] [hal] [pubmed]Résumé (cliquer pour lire). The analysis of the sequencestructure relationship in RNA molecules is not only essential for evolutionary studies but also for concrete applications such as errorcorrection in next generation sequencing (NGS) technologies. The prohibitive sizes of the mutational and conformational landscapes, combined with the volume of data to process, require efficient algorithms to compute sequencestructure properties. In this article, we address the correction of NGS errors by calculating which mutations most increase the likelihood of a sequence to a given structure and RNA family. We introduce RNApyro, an efficient, linear time and space insideoutside algorithm that computes exact mutational probabilities under secondary structure and evolutionary constraints given as a multiple sequence alignment with a consensus structure. We develop a scoring scheme combining classical stacking basepair energies to novel isostericity scores and apply our techniques to correct pointwise errors in 5s and 16s rRNA sequences. Our results suggest that RNApyro is a promising algorithm to complement existing tools in the NGS errorcorrection pipeline. 
Nucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 41(Web Server issue):W4805 pp, 2013 [doi] [hal] [pubmed]Résumé (cliquer pour lire). More than a simple carrier of the genetic information, messenger RNA (mRNA) coding regions can also harbor functional elements that evolved to control different posttranscriptional processes, such as mRNA splicing, localization and translation. Functional elements in RNA molecules are often encoded by secondary structure elements. In this aticle, we introduce Structural Profile Assignment of RNA Coding Sequences (SPARCS), an efficient method to analyze the (secondary) structure profile of proteincoding regions in mRNAs. First, we develop a novel algorithm that enables us to sample uniformly the sequence landscape preserving the dinucleotide frequency and the encoded amino acid sequence of the input mRNA. Then, we use this algorithm to generate a set of artificial sequences that is used to estimate the Zscore of classical structural metrics such as the sum of base pairing probabilities and the base pairing entropy. Finally, we use these metrics to predict structured and unstructured regions in the input mRNA sequence. We applied our methods to study the structural profile of the ASH1 genes and recovered key structural elements. A web server implementing this discovery pipeline is available at http://csb.cs.mcgill.ca/sparcs together with the source code of the sampling algorithm. 
Proteinprotein interactions in a crowded environment: an analysis via crossdocking simulations and evolutionary informationPLoS Computational Biology, Public Library of Science, 9(12):e1003369 pp, 2013 [doi] [hal]Résumé (cliquer pour lire). Proteinprotein interactions (PPI) are at the heart of the molecular processes governing life and constitute an increasingly important target for drug design. Given their importance, it is vital to determine which protein interactions have functional relevance and to characterize the protein competition inherent to crowded environments, as the cytoplasm or the cellular organelles. We show that combining coarsegrain molecular crossdocking simulations and binding site predictions based on evolutionary sequence analysis is a viable route to identify true interacting partners for hundreds of proteins with a variate set of protein structures and interfaces. Also, we realize a largescale analysis of protein binding promiscuity and provide a numerical characterization of partner competition and level of interaction strength for about 28000 falsepartner interactions. Finally, we demonstrate that binding site prediction is useful to discriminate native partners, but also to scale up the approach to thousands of protein interactions. This study is based on the large computational effort made by thousands of internautes helping World Community Grid over a period of 7 months. The complete dataset issued by the computation and the analysis is released to the scientific community.

 Conferences with proceedings

Proceedings of RECOMB  17th Annual International Conference on Research in Computational Molecular Biology  2013, China, 2013 [hal]Résumé (cliquer pour lire). Analysis of the sequencestructure relationship in RNA molecules are essential to evolutionary studies but also to concrete applications such as errorcorrection methodologies in sequencing technologies. The prohibitive sizes of the mutational and conformational landscapes combined with the volume of data to proceed require e cient algorithms to compute sequencestructure properties. More speci cally, here we aim to calculate which mutations increase the most the likelihood of a sequence to a given structure and RNA family. In this paper, we introduce RNApyro, an e cient lineartime and space insideoutside algorithm that computes exact mutational probabilities under secondary structure and evolutionary constraints given as a multiple sequence alignment with a consensus structure. We develop a scoring scheme combining classical stacking base pair energies to novel isostericity scales, and apply our techniques to correct pointwise errors in 5s rRNA sequences. Our results suggest that RNApyro is a promising algorithm to complement existing tools in the NGS errorcorrection pipeline. 
Proceedings of ISMB/ECCB  21st Annual international conference on Intelligent Systems for Molecular Biology/12th European Conference on Computational Biology  2013, Germany, 2013 [hal]Résumé (cliquer pour lire). Motivations: The design of RNA sequences folding into predefined secondary structures is a milestone for many synthetic biology and gene therapy studies. Most of the current software uses similar local search strategies (i.e. a random seed is progressively adapted to acquire the desired folding properties) and more importantly do not allow the user to control explicitly the nucleotide distribution such as the GCcontent in their sequences. However, the latter is an important criterion for largescale applications as it could presumably be used to design sequences with better transcription rates and/or structural plasticity. Results: In this paper, we introduce IncaRNAtion, a novel algorithm to design RNA sequences folding into target secondary structures with a predefined nucleotide distribution. IncaRNAtion uses a global sampling approach and weighted sampling techniques. We show that our approach is fast (i.e. running time comparable or better than local search methods), seedless (we remove the bias of the seed in local search heuristics), and successfully generates highquality sequences (i.e. thermodynamically stable) for any GCcontent. To complete this study, we develop an hybrid method combining our global sampling approach with local search strategies. Remarkably, our glocal methodology overcomes both local and global approaches for sampling sequences with a specific GC content and target structure. Availability: IncaRNAtion is available at csb.cs.mcgill.ca/incarnation/ 
Proceedings of RECOMB  17th Annual International Conference on Research in Computational Molecular Biology  2013, China, 2013 [hal]Résumé (cliquer pour lire). We describe the broad outline of a new thermodynamicsbased algorithm, FFTbor, that uses the fast Fourier transform to perform polynomial interpolation to compute the Boltzmann probability that secondary structures di er by k base pairs from an arbitrary reference structure of a given RNA sequence. The algorithm, which runs in quartic time O(n4) and quadratic space O(n2), is used to determine the correlation between kinetic folding speed and the ruggedness of the energy landscape,and to predict the location of riboswitch expression platform candidates. The full paper appears in PLoS ONE (2012) 19 Dec 2012. A web server is available at http://bioinformatics.bc.edu/clotelab/FFTbor/. 
Proceedings of ACMBCB  ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics  2013, United States, 2013 [hal]Résumé (cliquer pour lire). The problem of RNA secondary structure design (also called inverse folding) is the following: given a target secondary structure, one aims to create a sequence that folds into, or is compatible with, a given structure. In several practical applications in biology, additional constraints must be taken into account, such as the presence/absence of regulatory motifs, either at a specific location or anywhere in the sequence. In this study, we investigate the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we develop a general framework based on concepts of language theory, namely contextfree grammars and finite automata. We efficiently combine a comprehensive set of constraints into a unifying contextfree grammar of moderate size. From there, we use generic generic algorithms to perform a (weighted) random generation, or an exhaustive enumeration, of candidate sequences. The resulting method, whose complexity scales linearly with the length of the RNA, was implemented as a standalone program. The resulting software was embedded into a publicly available dedicated web server. The applicability demonstrated of the method on a concrete case study dedicated to Exon Splicing Enhancers, in which our approach was successfully used in the design of \emph{in vitro} experiments.

 Book chapters & Editorials

Introduction to RNA secondary structure comparison.RNA Sequence, Structure, and Function: Computational and Bioinformatic Methods, Methods in Molecular Biology Clifton then Totowa Editor(s) Gorodkin, Jan and Ruzzo, Walter L., Methods in molecular biology, Humana Press (Springer Imprint), 24773 pp, 2013 [doi] [hal] [pubmed]Résumé (cliquer pour lire). Many methods have been proposed for RNA secondary structure comparison, and new ones are still being developed. In this chapter, we first consider structure representations and discuss their suitability for structure comparison. Then, we take a look at the more commonly used methods, restricting ourselves to structures without pseudoknots. For comparing structures of the same sequence, we study base pair distances. For structures of different sequences (and of different length), we study variants of the tree edit model. We name some of the available tools and give pointers to the literature. We end with a short review on comparing structures with pseudoknots as an unsolved problem and topic of active research.

 Peerreviewed journal articles

2012
 Peerreviewed journal articles

Journal of Mathematical Biology, Springer Verlag (Germany), 65(3):58199 pp, 2012 [doi] [hal] [pubmed]Résumé (cliquer pour lire). In "The ends of a large RNA molecule are necessarily close", Yoffe et al. (Nucleic Acids Res 39(1):292299, 2011) used the programs RNAfold [resp. RNAsubopt] from Vienna RNA Package to calculate the distance between 5' and 3' ends of the minimum free energy secondary structure [resp. thermal equilibrium structures] of viral and random RNA sequences. Here, the 5'3' distance is defined to be the length of the shortest path from 5' node to 3' node in the undirected graph, whose edge set consists of edges {i, i + 1} corresponding to covalent backbone bonds and of edges {i, j} corresponding to canonical base pairs. From repeated simulations and using a heuristic theoretical argument, Yoffe et al. conclude that the 5'3' distance is less than a fixed constant, independent of RNA sequence length. In this paper, we provide a rigorous, mathematical framework to study the expected distance from 5' to 3' ends of an RNA sequence. We present recurrence relations that precisely define the expected distance from 5' to 3' ends of an RNA sequence, both for the Turner nearest neighbor energy model, as well as for a simple homopolymer model first defined by Stein and Waterman. We implement dynamic programming algorithms to compute (rather than approximate by repeated application of Vienna RNA Package) the expected distance between 5' and 3' ends of a given RNA sequence, with respect to the Turner energy model. Using methods of analytical combinatorics, that depend on complex analysis, we prove that the asymptotic expected 5'3' distance of length n homopolymers is approximately equal to the constant 5.47211, while the asymptotic distance is 6.771096 if hairpins have a minimum of 3 unpaired bases and the probability that any two positions can form a base pair is 1/4. Finally, we analyze the 5'3' distance for secondary structures from the STRAND database, and conclude that the 5'3' distance is correlated with RNA sequence length. 
Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches ^{*}PLoS ONE, Public Library of Science, 7(12):e50506 pp, 2012 [doi] [hal]Résumé (cliquer pour lire). Using complex roots of unity and the Fast Fourier Transform, we design a new thermodynamicsbased algorithm, FFTbor, that computes the Boltzmann probability that secondary structures differ by k base pairs from an arbitrary initial structure of a given RNA sequence. The algorithm, which runs in quartic time O(n^4) and quadratic space O(n^2), is used to determine the correlation between kinetic folding speed and the ruggedness of the energy landscape, and to predict the location of riboswitch expression platform candidates. A web server is available at http://bioinformatics.bc.edu/clotelab/FFTbor/ 
A global sampling approach to designing and reengineering RNA secondary structures.Nucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 40(20):1004152 pp, 2012 [doi] [hal] [pubmed]Résumé (cliquer pour lire). The development of algorithms for designing artificial RNA sequences that fold into specific secondary structures has many potential biomedical and synthetic biology applications. To date, this problem remains computationally difficult, and current strategies to address it resort to heuristics and stochastic search techniques. The most popular methods consist of two steps: First a random seed sequence is generated; next, this seed is progressively modified (i.e. mutated) to adopt the desired folding properties. Although computationally inexpensive, this approach raises several questions such as (i) the influence of the seed; and (ii) the efficiency of singlepath directed searches that may be affected by energy barriers in the mutational landscape. In this article, we present RNAensign, a novel paradigm for RNA design. Instead of taking a progressive adaptive walk driven by local search criteria, we use an efficient global sampling algorithm to examine large regions of the mutational landscape under structural and thermodynamical constraints until a solution is found. When considering the influence of the seeds and the target secondary structures, our results show that, compared to singlepath directed searches, our approach is more robust, succeeds more often and generates more thermodynamically stable sequences. An ensemble approach to RNA design is thus well worth pursuing as a complement to existing approaches. RNAensign is available at http://csb.cs.mcgill.ca/RNAensign.

 Conferences with proceedings

Proceedings of AOFA  23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms  2012, Canada, DMTCS, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12):243264 pp, 2012 [hal]Résumé (cliquer pour lire). We consider the word collector problem, i.e. the expected number of calls to a random weighted generator before all the words of a given length in a language are generated. The originality of this instance of the nonuniform coupon collector lies in the, potentially large, multiplicity of the words/coupons of a given probability/composition. We obtain a general theorem that gives an asymptotic equivalent for the expected waiting time of a general version of the Coupon Collector. This theorem is especially wellsuited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates knowledge on the number of words of a given composition/probability. We illustrate the application of our theorem, in a stepbystep fashion, on four exemplary languages, whose analyses reveal a large diversity of asymptotic waiting times, generally expressible as $\kappa \cdot m^p \cdot (\log{m})^q \cdot (\log \log{m})^r$, for $m$ the number of words, and $p, q, r$ some positive real numbers. 
Proceedings of CPM  23rd Annual Symposium on Combinatorial Pattern Matching  2012, Finland, Combinatorial Pattern Matching, Springer, 7354:321333 pp, 2012 [doi] [hal]Résumé (cliquer pour lire). La prédiction du repliement, avec pseudonoeuds généraux, d'une séquence d'ARN de taille $n$ est équivalent à la recherche d'un couplage d'énergie libre minimale. Dans un modèle d'énergie simple, où chaque paire de base contribue indépendamment à l'énergie, ce problème peut être résolu en temps $\Theta(n^3)$ grâce à une variante d'un algorithme de couplage pondéré maximal. Cependant, le même problème a été démontré NPdifficile dans le modèle d'énergie dit des plus proches voisins. Dans ce travail, nous étudions les propriétés du problème sous un modèle d'empilements, constituant un modèle intermédiaire entre ceux d'appariement et des plus proches voisins. Nous démontrons tout d'abord que le repliement avec pseudonoeuds de l'ARN reste NPdifficile dans de nombreuses valuations du modèle d'énergie. . Par ailleurs, nous montrons que ce problème est approximable, en proposant un algorithme polynomial garantissant une $1/5$approximation. Ce résultat illustre une différence essentielle entre ce modèle et celui des plus proches voisins, pour lequel nous montrons qu'il ne peut être approché à aucun ratio positif par un algorithme en temps polynomial sauf si $N=NP$. 
Proceedings of ANALCO  12th Meeting on Analytic Algorithmics and Combinatorics  2012, Japan, Omnipress, 107116 pp, 2012 [hal]Résumé (cliquer pour lire). It is well known that, under some aperiodicity and irreducibility conditions, the number of occurrences of local patterns within a Markov chain (and, more generally, within the languages generated by weighted regular expressions/automata) follows a Gaussian distribu tion with both variance and mean in (n). By contrast, when these conditions no longer hold, it has been denoted that the limiting distribution may follow a whole diversity of distributions, including the uniform, powerlaw or even multimodal distribution, arising as tradeo s between structural properties of the regular expression and the weight/probabilities associated with its transitions/letters. However these cases only partially cover the full diversity of behaviors induced within regular expressions, and a characterization of attainable distributions remained to be provided. In this article, we constructively show that the limiting distribution of the simplest foresee able motif (a single letter!) may already follow an arbitrarily complex continuous distribution (or cadlag process). We also give applications in random generation (Boltzmann sampling) and bioinformatics (parsimonious segmentation of DNA). 
Proceedings of WABI  12th Workshop on Algorithms in Bioinformatics  2012, Slovenia, tba, 2012 [hal]Résumé (cliquer pour lire). Nous présentons un cadre général pour la comparaison structure/séquence d'une très large classe de structures d'ARN, qui généralise de nombreux travaux récents consacrés à des familles spécifiques. Notre approche, basée sur une décomposition arborescente des structures, permet d'obtenir un algorithme de complexité paramétrée, dont la complexité asymptotique, exponentielle dans le cas général, dépend de la famille de structures considérée. Pour chacune des familles considérées par les travaux antérieurs, notre algorithme se spécialise automatiquement, et permet d'obtenir une complexité égale à celle obtenue jusqu'alors.

 Book chapters & Editorials

Mieux comprendre certaines molécules biologiques grâce à l’informatiqueInterstices INRIA, 2012 [hal]Résumé (cliquer pour lire). Yann Ponty s’intéresse à l’algorithmique du repliement d’ARN. Il nous en parle dans cet épisode du podcast audio.

 Conferences without proceedings and/or unrefereed

Can Probabilistic Model Checking Explore RiboNucleic Acid Folding Space?Proceedings of IWBDA  4th International Workshop on BioDesign Automation  2012, United States, 2012 [hal]Résumé (cliquer pour lire). The folding path of a ribonucleic acid from its free form to its complete structure is of significant interest to structural biologists. There are algorithms for simulating kinetics of the ribonucleic acid from its unfolded state to its stable structure (minimum freeenergy structure). These computational techniques are expensive as the total number of structures in the folding space is exponentially large. We propose to use timeefficient algorithms from the field of probabilistic model checking for verifying certain hypothesis concerning ribonucleic acid folding landscape. First, we explain how thermodynamic models of ribonucleic acid can be used to generate a Markov chain of structures, whose transitions within the chain are based on the energy difference w.r.t to their neighbours. Then we present a process algebra model to compactly represent the dynamics of ribonucleic acid folding. Both these approaches essentially generate input models for probabilistic model checking. Finally, we discuss if statistical model checking techniques can be applied for the problem of aligning ribonucleic acid sequences and structures.

 Invited talks

Visualizing 2D & 3D Structures of RNAProceedings of VIZBI  3rd international meeting on Visualizing Biological Data  2012, Germany, 2012 [hal]Résumé (cliquer pour lire). Broad overview of the existing visualization techniques/methods/tools and many challenges faced by the RNA community.

 Miscellaneous & Submitted

[hal]Résumé (cliquer pour lire). Two formalisms, both based on contextfree grammars, have recently been proposed as a basis for a nonuniform random generation of combinatorial objects. The former, introduced by Denise et al, associates weights with letters, while the latter, recently explored by Weinberg et al in the context of random generation, associates weights to transitions. In this short note, we use a simple modification of the Greibach Normal Form transformation algorithm, due to Blum and Koch, to show the equivalent expressivities, in term of their induced distributions, of these two formalisms.

 Peerreviewed journal articles

2011
 Peerreviewed journal articles

An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure. ^{*}Journal of Computational Biology, Mary Ann Liebert, 18(11):146579 pp, 2011 [doi] [hal] [pubmed]Résumé (cliquer pour lire). The analysis of the relationship between sequences and structures (i.e., how mutations affect structures and reciprocally how structures influence mutations) is essential to decipher the principles driving molecular evolution, to infer the origins of genetic diseases, and to develop bioengineering applications such as the design of artificial molecules. Because their structures can be predicted from the sequence data only, RNA molecules provide a good framework to study this sequencestructure relationship. We recently introduced a suite of algorithms called RNAmutants which allows a complete exploration of RNA sequencestructure maps in polynomial time and space. Formally, RNAmutants takes an input sequence (or seed) to compute the Boltzmannweighted ensembles of mutants with exactly k mutations, and sample mutations from these ensembles. However, this approach suffers from major limitations. Indeed, since the Boltzmann probabilities of the mutations depend of the free energy of the structures, RNAmutants has difficulties to sample mutant sequences with low G+Ccontents. In this article, we introduce an unbiased adaptive sampling algorithm that enables RNAmutants to sample regions of the mutational landscape poorly covered by classical algorithms. We applied these methods to sample mutations with low G+Ccontents. These adaptive sampling techniques can be easily adapted to explore other regions of the sequence and structural landscapes which are difficult to sample. Importantly, these algorithms come at a minimal computational cost. We demonstrate the insights offered by these techniques on studies of complete RNA sequence structures maps of sizes up to 40 nucleotides. Our results indicate that the G+Ccontent has a strong influence on the size and shape of the evolutionary accessible sequence and structural spaces. In particular, we show that low G+Ccontents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+Ccontents significantly reduce the size of the evolutionary accessible mutational landscapes.

 Conferences with proceedings

Proceedings of RECOMB  15th Annual International Conference on Research in Computational Molecular Biology  2011, Canada, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 6577:501515 pp, 2011 [doi] [hal]Résumé (cliquer pour lire). The analysis of the relationship between sequences and structures (i.e. how mutations aect structures and reciprocally how structures in uence mutations) is essential to decipher the principles driving molecular evolution, to infer the origins of genetic diseases or to develop bioengineering applications such as the design of articial molecules. Because their structures can be predicted from the sequence data only, RNA molecules provide a good framework to study this sequencestructure relationship. We recently introduced a suite of algorithms called RNAmutants which allows, for the rst time, a complete exploration of RNA sequencestructure maps in polynomial time and space. Formally, RNAmutants takes an input sequence (or seed) to compute the Boltzmann weighted ensembles of mutants with exactly k mutations, and sample mutations from these ensembles. However, this approach suers from major limitations. Indeed, since the Boltzmann probabilities of the mutations depend of the free energy of the structures, RNAmutants has diculties to sample mutant sequences with low G+Ccontents. In this paper we introduce a novel unbiased adaptive sampling algorithm that enables RNAmutants to sample regions of the mutational landscape poorly covered by classical algorithms. We applied these methods to sample mutations with low G+Ccontents. These adaptive sampling techniques can be easily adapted to explore other regions of the sequence and structural landscapes which are dif cult to sample. Importantly, these algorithms come at a minimal computational cost. We demonstrate the insights oered by these techniques on studies of complete RNA sequence structures maps of sizes up to 40 nucleotides. Our results indicate that the G+Ccontent has a strong in uence on the size and shape of the evolutionary accessible sequence and structural spaces. In particular, we show that low G+Ccontents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+Ccontents signicantly reduce the size of the evolutionary accessible mutational landscapes. 
Proceedings of WABI  11th Workshop on Algorithms in Bioinformatics  2011, Germany, 2011 [hal]Résumé (cliquer pour lire). We extend an hypergraph representation, introduced by Finkelstein and Roytberg, to unify dynamic programming algorithms in the context of RNA folding with pseudoknots. Classic applications of RNA dynamic programming energy minimization, partition function, basepair probabilities\ldots) are reformulated within this framework, giving rise to very simple algorithms. This reformulation allows one to conceptually detach the conformation space/energy model  captured by the hypergraph model  from the specific application, assuming unambiguity of the decomposition. To ensure the latter property, we propose a new combinatorial methodology based on generating functions. We extend the set of generic applications by proposing an exact algorithm for extracting generalized moments in weighted distribution, generalizing a prior contribution by Miklos and al. Finally, we illustrate our fullfledged programme on three exemplary conformation spaces (secondary structures, Akutsu's simple type pseudoknots and kissing hairpins). This readily gives sets of algorithms that are either novel or have complexity comparable to classic implementations for minimization and Boltzmann ensemble applications of dynamic programming.

 Conferences without proceedings and/or unrefereed

Proceedings of Fifth IndoFrench Bioinformatics Meeting, India, 2011 [hal]Résumé (cliquer pour lire). In this short note, we investigate the responsibility of pseudoknotted (PK) foldings in the observed incapacity of an MFE folding method (RNAfold) to predict the structure of certain families of RNA within RFam. We considered the difference Delta in predicted freeenergy obtained by respectively considering and omitting PK conformations, which we showed could be reliably used as an indicator for the presence of pseudoknots (84.5% AUC, while 88.3% of PK families have positive values). We furthered our analysis, investigating the top 15 families associated with positive values of Delta associated with nonPK consensus structures in RFAM, and found evidence of the presence of PK in the literature for at least 11 of them. However a large proportion of poorly predicted families remain associated with low Delta values, and additional explanations need be explored for their poor predictions.

 Peerreviewed journal articles

2010
 Peerreviewed journal articles

Theoretical Computer Science, Elsevier, 411(4042):35273552 pp, 2010 [doi] [hal]Résumé (cliquer pour lire). Consider a class of decomposable combinatorial structures, using different types of atoms ${\cal Z} = \{z_1,\ldots ,z_{{\cal Z}}\}$. We address the random generation of such structures with respect to a size $n$ and a targeted distribution in $k$ of its \emph{distinguished} atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by $k$ real numbers $\mu_1, \ldots, \mu_k$ such that $0 < \mu_i < 1$ for all $i$ and $\mu_1+\cdots+\mu_k \leq 1$. We aim to generate random structures among the whole set of structures of a given size $n$, in such a way that the {\em expected} frequency of any distinguished atom $z_i$ equals $\mu_i$. We address this problem by weighting the atoms with a $k$tuple $\pi$ of realvalued weights, inducing a weighted distribution over the set of structures of size $n$. We first adapt the classical recursive random generation scheme into an algorithm taking ${\cal O}(n^{1+o(1)}+mn\log{n})$ arithmetic operations to draw $m$ structures from the $\pi$weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i. e. for large values of $n$. We derive systems of functional equations whose resolution gives an explicit relationship between $\pi$ and $\mu_1, \ldots, \mu_k$. Lastly, we give an algorithm in ${\cal O}(k n^4)$ for the inverse problem, {\it i.e.} computing the frequencies associated with a given $k$tuple $\pi$ of weights, and an optimized version in ${\cal O}(k n^2)$ in the case of contextfree languages. This allows for a heuristic resolution of the weights/frequencies relationship suitable for complex specifications. In the second alternative, the targeted distribution is given by a $k$ natural numbers $n_1, \ldots, n_k$ such that $n_1+\cdots+n_k+r=n$ where $r \geq 0$ is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size $n$ that contain {\em exactly} $n_i$ atoms $z_i$ ($1 \leq i \leq k$). We give a ${\cal O}(r^2\prod_{i=1}^k n_i^2 +m n k \log n)$ algorithm for generating $m$ structures, which simplifies into a ${\cal O}(r\prod_{i=1}^k n_i +m n)$ for regular specifications.

 Conferences with proceedings

Proceedings of GASCOM  8th conference on random generation of combinatorial structures  2010, Canada, 14pp pp, 2010 [hal]Résumé (cliquer pour lire). The present work analyzes the redundancy of sets of combinatorial objects produced by a weighted random generation algorithm proposed by Denise et al. This scheme associates weights to the terminals symbols of a weighted contextfree grammar, extends this weight definition multiplicatively on words, and draws words of length $n$ with probability proportional their weight. We investigate the level of redundancy within a sample of $k$ word, the proportion of the total probability covered by $k$ words (coverage), the time (number of generations) of the first collision, and the time of the full collection. For these four questions, we use an analytic urn analogy to derive asymptotic estimates and/or polynomially computable exact forms. We illustrate these tools by an analysis of an RNA secondary structure statistical sampling algorithm introduced by Ding et al. 
Proceedings of 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Austria, DMTCS Proceedings, DMTCS, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10):4964 pp, 2010 [hal]Résumé (cliquer pour lire). We address the uniform random generation of words from a contextfree language (over an alphabet of size $k$), while constraining every letter to a targeted frequency of occurrence. Our approach consists in a multidimensional extension of Boltzmann samplers. We show that, under mostly $\textit{strongconnectivity}$ hypotheses, our samplers return a word of size in $[(1 \epsilon)n, (1+ \epsilon)n]$ and exact frequency in $\mathcal{O}(n^{1+k/2})$ expected time. Moreover, if we accept tolerance intervals of width in $\Omega (\sqrt{n})$ for the number of occurrences of each letters, our samplers perform an approximatesize generation of words in expected $\mathcal{O}(n)$ time. We illustrate our approach on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.

 Peerreviewed journal articles

2009
 Peerreviewed journal articles

Bioinformatics, Oxford University Press (OUP), 25(15):19745 pp, 2009 [doi] [hal] [pubmed]Résumé (cliquer pour lire). DESCRIPTION: VARNA is a tool for the automated drawing, visualization and annotation of the secondary structure of RNA, designed as a companion software for web servers and databases. FEATURES: VARNA implements four drawing algorithms, supports input/output using the classic formats dbn, ct, bpseq and RNAML and exports the drawing as five picture formats, either pixelbased (JPEG, PNG) or vectorbased (SVG, EPS and XFIG). It also allows manual modification and structural annotation of the resulting drawing using either an interactive point and click approach, within a web server or through commandline arguments. AVAILABILITY: VARNA is a free software, released under the terms of the GPLv3.0 license and available at http://varna.lri.fr. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

 Peerreviewed journal articles

2008
 Peerreviewed journal articles

Efficient sampling of RNA secondary structures from the Boltzmann ensemble of lowenergy: The boustrophedon methodJournal of Mathematical Biology, Springer Verlag (Germany), 56(12):107127 pp, 2008 [doi] [hal]Résumé (cliquer pour lire). We adapt here a surprising technique, the boustrophedon method, to speed up the sampling of RNA secondary structures from the Boltzmann lowenergy ensemble. This technique is simple and its implementation straightforward, as it only requires a permutation in the order of some operations already performed in the stochastic traceback stage of these algorithms. It nevertheless greatly improves their worstcase complexity from O(n^2) to O(n log(n)), for n the size of the original sequence. Moreover the averagecase complexity of the generation is shown to be improved from O(n√n) to O(n log(n)) in an Boltzmannweighted homopolymer model based on the Nussinov–Jacobson freeenergy model. These results are extended to the more realistic Turner freeenergy model through experiments performed on both structured (Drosophilia melanogaster mRNA 5S) and hybrid (Staphylococcus aureus RNAIII) RNA sequences, using a boustrophedon modified version of the popular software UnaFold. This improvement allows for the sampling of greater and more significant sets of structures in a given time. 
Discrete Mathematics and Theoretical Computer Science, DMTCS, 10(2):125152 pp, 2008 [hal]Résumé (cliquer pour lire). Let a and b be two positive integers. A culminating path is a path of Z^2 that starts from (0,0), consists of steps (1,a) and (1,b), stays above the xaxis and ends at the highest ordinate it ever reaches. These paths were first encountered in bioinformatics, in the analysis of similarity search algorithms. They are also related to certain models of Lorentzian gravity in theoretical physics. We first show that the language on a two letter alphabet that naturally encodes culminating paths is not contextfree. Then, we focus on the enumeration of culminating paths. A step by step approach, combined with the kernel method, provides a closed form expression for the generating fucntion of culminating paths ending at a (generic) height k. In the case a=b, we derive from this expression the asymptotic behaviour of the number of culminating paths of length n. When a>b, we obtain the asymptotic behaviour by a simpler argument. When a= b, with no precomputation stage nor nonlinear storage required. The choice of the best algorithm is not as clear when a 
Asymptotics of RNA shapesJournal of Computational Biology, Mary Ann Liebert, 15(1):3163 pp, 2008 [doi] [hal]Résumé (cliquer pour lire). RNA shapes, introduced by Giegerich et al., provide a useful classification of the branching complexity for RNA secondary structures. In this paper, we derive an exact value for the asymptotic number of RNA shapes, by relying on an elegant relation between nonambiguous, contextfree grammars and generating functions. Our results provide a theoretical upper bound on the length of RNA sequences amenable to probabilistic shape analysis, under the assumption that any base can basepair with any other base. Since the relation between contextfree grammars and asymptotic enumeration is simple yet not wellknown in bioinformatics, we give a selfcontained presentation with illustrative examples. Additionally, we prove a surprising 1to1 correspondence between Pishapes and Motzkin numbers 
LocalMove: computing onlattice fits for biopolymersNucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 36(2):W216W222 pp, 2008 [doi] [hal]Résumé (cliquer pour lire). Given an input Protein Data Bank file (PDB) for a protein or RNA molecule, LocalMove is a web server that determines an onlattice representation for the input biomolecule. The web server implements a Markov Chain MonteCarlo algorithm with simulated annealing to compute an approximate fit for either the coarsegrain model or backbone model on either the cubic or facecentered cubic lattice. LocalMove returns a PDB file as output, as well as dynamic movie of 3D images of intermediate conformations during the computation. The LocalMove server is publicly available at http://bioinformatics.bc.edu/clotelab/localmove/.

 Conferences with proceedings

Proceedings of GASCOM  7th conference on random generation of combinatorial structures  2008, Italy, 12pp pp, 2008 [hal]Résumé (cliquer pour lire). We address the nonredundant random generation of k words of length n from a contextfree language. Additionally, we want to avoid a prede¯ned set of words. We study the limits of a rejectionbased approach, whose time complexity is shown to grow exponentially in k in some cases. We propose an alternative recursive algorithm, whose careful implementation allows for a nonredundant generation of k words of size n in O(kn log n) arithmetic operations after the precomputation of O(n) numbers. The overall complexity is therefore dominated by the generation of k words, and the nonredundancy comes at a negligible cost.

 Peerreviewed journal articles

2007
 Peerreviewed journal articles

DIAL: A web server for the pairwise alignment of two RNA 3dimensional structures using nucleotide, dihedral angle and base pairing similaritiesNucleic Acids Research, Oxford University Press (OUP): Policy C  Option B, 35(Web server issue):W659668 pp, 2007 [doi] [hal]Résumé (cliquer pour lire). DIAL (dihedral alignment) is a web server that provides public access to a new dynamic programming algorithm for pairwise 3D structural alignment of RNA. DIAL achieves quadratic time by performing an alignment that accounts for (i) pseudodihedral and/or dihedral angle similarity, (ii) nucleotide sequence similarity and (iii) nucleotide basepairing similarity. DIAL provides access to three alignment algorithms: global (Needleman–Wunsch), local (Smith–Waterman) and semiglobal modified to yield motif search). Suboptimal alignments are optionally returned, and also the Boltzmann pair probabilities for aligned positions within the optimal alignment. If a nonzero suboptimal alignment score ratio is entered, then the semiglobal alignment algorithm may be used to detect structurally similar occurrences of a userspecified 3D motif. The query motif may be contiguous in the linear chain or fragmented in a number of noncontiguous regions. The DIAL web server provides graphical output which allows the user to view, rotate and enlarge the 3D superposition for the optimal (and suboptimal) alignment of query to target. Although graphical output is available for all three algorithms, the semiglobal motif search may be of most interest in attempts to identify RNA motifs. DIAL is available at http://bioinformatics.bc.edu/clotelab/DIAL.

 Peerreviewed journal articles

2006
 Peerreviewed journal articles

Bioinformatics, Oxford University Press (OUP), 22(12):15341535 pp, 2006 [doi] [hal]Résumé (cliquer pour lire). GenRGenS is a software tool dedicated to randomly generating genomic sequences and structures. It handles several classes of models useful for sequence analysis, such as Markov chains, hidden Markov models, weighted contextfree grammars, regular expressions and PROSITE expressions. GenRGenS is the only program that can handle weighted contextfree grammars, thus allowing the user to model and to generate structured objects (such as RNA secondary structures) of any given desired size. GenRGenS also allows the user to combine several of these different models at the same time. Availability: Source and executable files of GenRGenS (in Java) and the complete user's manual are freely available at http://www.lri.fr/bio/GenRGenS

 Theses

2006 [hal]Résumé (cliquer pour lire). La mise en évidence des mécanismes de sélection agissant sur les données génomiques structurées (ARN, Protéines, ADN...) nécessite l'élaboration de modèles de séquences. Une fois un tel modèle élaboré, il est possible, au prix d'une analyse mathématique parfois complexe ou par le biais de la
génération aléatoire, d'évaluer la significativité d'un phénomène observé. Tout d'abord, nous nous intéressons aux propriétés des grammaires pondérées, un formalisme particulièrement adapté à la modélisation de la structure des ARN, dérivant des algorithmes de génération aléatoire efficaces implémentés au sein du prototype GenRGenS. Nous abordons le calcul automatique des pondérations réalisant des valeurs observées pour les paramètres du modèle, ainsi qu'une implémentation basée sur une approche optimisation. Dans un second temps, nous abordons la modélisation de la structure secondaire d'ARN. Après quelques rappels de biologie moléculaire, nous proposons plusieurs modèles basés sur des grammaires pondérées permettant la génération de structures d'ARN réalistes. L'utilisation d'un algorithme d'optimisation permet le calculer des pondérations correspondant à certaines familles d'ARN. Nous proposons enfin un algorithme d'extraction de structure secondaire maximale dans une structure générale, qui permet de profiter des données récentes issues de la cristallographie. Le dernier chapitre de cette thèse s'intéresse à l'analyse d'un algorithme de recherche de similarité heuristique, dont la sensibilité s'avère étroitement liée à la probabilité de présence d'un motif au sein de marches aléatoires particulières, les chemins culminants. Ces marches restent positives, et atteignent une altitude maximale en leur dernier pas. Nous proposons un algorithme récursif de génération aléatoire pour ces chemins. En combinant des techniques issues de la combinatoire énumérative, l'analyse asymptotique et la théorie des langages, nous dérivons des algorithmes de génération aléatoire par rejet linéaires dans de nombreux cas.

 Peerreviewed journal articles

2004
 Conferences with proceedings

Proceedings of 4th Symposium on Bioinformatics and bioengineering  BIBE'2004, Taiwan, Proceedings of the Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE'04), IEEE Computer Society, 387394 pp, 2004 [doi] [hal]Résumé (cliquer pour lire). We address the problem of estimating the sensitivity of seedbased similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.

 Conferences with proceedings

2003
 Miscellaneous & Submitted

[hal]Résumé (cliquer pour lire). Ce mémoire résume un travail opéré sous la direction d'Alain Denise de Mars à Juin 2003. Il consisteen une étude des propriétés combinatoires des structures secondaires d'ARN, en rapport avec le problème de la génération aléatoire de structures secondaires d'ARN réalistes.Dans une première partie, nous tenterons de familiariser le lecteur avec le contexte biologique sousjacent aux problèmes étudiés.Nous présenterons ensuite un état de l'art de l'étude combinatoire des structures secondaire d'ARN. Pour cela, nous introduirons brièvement une série d'outils théoriques, comme les séries génératrices, et leurs comportements asymptotiques ou les grammaires non contextuelles. Enfin, nous évoquerons divers mécanismes de génération aléatoire et présenterons une contribution à l'étude des paramètres des structures secondaires d'ARN.Nous proposerons en annexe une description d'un logiciel dédié à la génération aléatoire de séquences génomiques, GenRGenS, dont l'auteur assure le développement depuis la version 1.0. Nous présenterons aussi un algorithme polynomial de génération aléatoire de chemins culminants, structures combinatoires non algébriques qui apparaissent lors de l'étude d'algorithmes d'alignements de séquence. 
[hal]Résumé (cliquer pour lire). We address the problem of measuring the sensitivity of seedbased similarity search algorithms. In contrast to approaches based on Markov models, we study the measurement based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.

 Miscellaneous & Submitted