Inverse folding is a classic problem in RNA bioinformatics, crucial for designing functional synthetic RNAs, which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. In a simple base pair maximization (maxBPs) model, Bonnet et al. showed that a mildly constrained version of inverse folding is NP-hard. By contrast, a linear-time exact algorithm was proposed for maxBPs inverse folding, when restricted to input structures where each helix, i.e. each set of consecutive base pairs, has size at least 3. However, the maxBPs model artificially induces drastic limitations on the set of designable structures, forbidding the design of many well-known RNA families. In this work, we adopt a more realistic energy model based on stacked base pairs and study the inverse folding under a stack maximization (maxStacks) energy model, motivated by the major contribution of stacks to RNA stability. We propose an exact 𝒪(n)-time algorithm for maxStacks inverse folding, restricted to structures having minimum helix length ⌈log_{3.56}(Δ) + 6.2⌉ base pairs, where Δ is the largest degree of a loop in the target structure. Our approach hinges on the introduction of the locked property, a sufficient condition for a sequence to be a maxStacks design. Our algorithm enables the design of loops with arbitrary degree Δ in the maxStacks model, contrasting with the maxBPs model where inverse folding is unsolvable beyond Δ = 4. Interestingly, the locked property can also be utilized to partially solve maxStacks inverse folding when crossing base pairs, aka general pseudoknots, are allowed in the target structure and possible competitors. In this setting, we obtain an exact 𝒪(n)-time algorithm for maxStacks inverse folding restricted to (pseudoknotted) targets having minimum helix length ⌈log_{3.56}(m)+6.2⌉, m now being the number of helices. This result is surprising since checking the validity of a candidate sequence requires solving RNA folding with general pseudoknots, a problem known to be NP-hard in the maxStacks model. We empirically evaluate the potential of maxStacks solutions by designing candidate sequences for synthetic structures, uniformly generated at random to be non-pseudoknotted for diverse minimal helix lengths. We consider a natural generalization of our exact algorithm, heuristically addressing cases where the minimum helix length condition fails, and compare it to a baseline assignment of random compatible nucleotides. Our results show that satisfying the maxStacks criterion discriminates sequences that are likely to represent solutions to the expressive Turner energy model. Moreover, sequences produced by our (generalized) algorithm are more distant, energy-wise, to their competitors than uniform compatible sequences, suggesting the potential of maxStacks designs towards complex use cases.

RNA structure modeling greatly benefits from the availability of structural homologs, associated with the presence of coevolving positions in multiple alignments. Direct Coupling Analysis (DCA) is a statistical framework for inferring significant covariations as Potts models, in a way that corrects for the transitive nature of mutual information. Various instances of DCA have been proposed over time with demonstrated ability to infer molecular contacts, yet were shown to be associated with inference algorithms that are invariably data hungry, prone to overfitting, and hindered by numerical instability. Recently, edge-activated DCA (eaDCA) has emerged as an alternative which iteratively infers couplings in a greedy manner and explicitly targets sparsity. In this work, we revisit the inference of eaDCA models in a rigorous algorithmic setting. We circumvent the #P-hardness of computing the most promising addition/update of coupling and provide exact fixed-parameter tractable algorithms for the treewidth parameter of the coupling-induced graph. We empirically show that eaDCA models are typically associated with moderate treewidth values, and validate the practical feasibility of the method by producing, in a matter of minutes, the models associated with 41 RFAM families associated with structured non-coding families. Our results reveal good recovery rates for couplings associated with conserved base pairs from the family consensus, and enable a more systematic and robust assessment of the potential of eaDCA.

MOTIVATION: Biologically relevant RNA secondary structures are routinely predicted by efficient dynamic programming algorithms that minimize their free energy. Starting from such algorithms, one can devise partition function algorithms, which enable stochastic perspectives on RNA structure ensembles. As the most prominent example, McCaskill's partition function algorithm is derived from pseudoknot-free energy minimization. While this algorithm became hugely successful for the analysis of pseudoknot-free RNA structure ensembles, as of yet there exists only one pseudoknotted partition function implementation, which covers only simple pseudoknots and comes with a borderline-prohibitive complexity of O(n5) in the RNA length n. RESULTS: Here, we develop a partition function algorithm corresponding to the hierarchical pseudoknot prediction of HFold, which performs exact optimization in a realistic pseudoknot energy model. In consequence, our algorithm CParty carries over HFold's advantages over classical pseudoknot prediction in characterizing the Boltzmann ensemble at equilibrium. Given an RNA sequence S and a pseudoknot-free structure G, CParty computes the partition function over all possibly pseudoknotted density-2 structures G∪G' of S that extend the fixed G by a disjoint pseudoknot-free structure G'. Thus, CParty follows the common hypothesis of hierarchical pseudoknot formation, where pseudoknots form as tertiary contacts only after a first pseudoknot-free "core" G and we call the computed partition function hierarchically constrained (by G). Like HFold, the dynamic programming algorithm CParty is very efficient, achieving the low complexity of the pseudoknot-free algorithm, i.e. cubic time and quadratic space. Finally, by computing pseudoknotted ensemble energies, we unveil kinetics features of a therapeutic target in SARS-CoV-2. AVAILABILITY AND IMPLEMENTATION: CParty is available at https://github.com/HosnaJabbari/CParty.

MOTIVATION: Recent viral outbreaks motivate the systematic collection of pathogenic genomes in order to accelerate their study and monitor the apparition/spread of variants. Due to their limited length and temporal proximity of their sequencing, viral genomes are usually organized, and analyzed as oversized Multiple Sequence Alignments (MSAs). Such MSAs are largely ungapped, and mostly homogeneous on a column-wise level but not at a sequential level due to local variations, hindering the performances of sequential compression algorithms. RESULTS: In order to enable an efficient handling of MSAs, including subsequent statistical analyses, we introduce CREMSA (Column-wise Run-length Encoding for MSAs), a new index that builds on sparse bitvector representations to compress an existing or streamed MSA, all the while allowing for an expressive set of accelerated requests to query the alignment without prior decompression. Using CREMSA, a 65 GB MSA consisting of 1.9M SARS-CoV 2 genomes could be compressed into 22 MB using less than half a gigabyte of main memory, while executing access requests in the order of 100 ns. Such a speed up enables a comprehensive analysis of covariation over this very large MSA. We further assess the impact of the sequence ordering on the compressibility of MSAs and propose a resorting strategy that, despite the proven NP-hardness of an optimal sort, induces greatly increased compression ratios at a marginal computational cost. AVAILABILITY AND IMPLEMENTATION: CREMSA is freely accessible at https://gitlab.univ-lille.fr/cremsa/cremsa. The Snakemake workflow for the benchmarks is available at: https://gitlab.univ-lille.fr/cremsa/bench. The data used in the paper is on Zenodo at https://zenodo.org/records/14698859 and https://zenodo.org/records/15100011.

This editorial describes the selection process and the collection of articles selected for presentation for the Proceedings Track of the ISMB 2024 conference.

Motivation. Recurrent substructures in RNA, known as 3D motifs, consist of networks of base pair interactions and are critical to understanding the relationship between structure and function. Their structure is naturally expressed as a graph which has led to many graph-based algorithms to automatically catalog identical motifs found in 3D structures. Yet, due to the complexity of the problem, state-of-the-art methods are often optimized to find exact matches, limiting the search to a subset of potential solutions, or do not allow explicit control over the desired variability. Results. We developed FuzzTree, a method able to efficiently sample approximate instances of an RNA motif, abstracted as a subgraph within a target RNA structure. It is the first method that allows explicit control over (1) the admissible geometric variability in the interactions; (2) the number of missing edges; and (3) the introduction of discontinuities in the backbone given close distances in the 3D structure. Our tool relies on a multidimensional Boltzmann sampling, having complexity parameterized by the treewidth of the requested motif. We applied our method to the well-known internal loop Kink-Turn motif, which can be divided into 12 subgroups. Given only the graph representing the main Kink-Turn subgroup, FuzzTree retrieved over 3/4 of all kink-turns. We also highlighted two occurrences of new sampled patterns. Our tool is available as free software and can be customized for different parameters and types of graphs.

This special issue of Bioinformatics serves as the proceedings of the 31st annual conference on Intelligent Systems for Molecular Biology (ISMB) co-organized with the 22nd European Conference on Computational Biology (ECCB). This conference took place on 23–27 July 2023, in Lyon, France. ISMB is the leading international forum for presenting new research results, disseminating methods and techniques, and facilitating discussions among leading researchers, practitioners, and students in the field. In addition, ISMB is the flagship conference of the International Society for Computational Biology (ISCB). Joining forces with ECCB, ISMB/ECCB2023 is the largest event of the computational biology community. Due to ongoing issues related to the COVID-19 pandemic, the ISMB/ECCB 2023 meeting was run as a hybrid conference, with online participants from all around the world complementing the on-site participants. The papers published in this volume were selected from 336 submitted full length papers, featuring original research. The submitted papers were thoroughly reviewed with each paper receiving 4.04 reviews on average, for a total of 1358 reports. For the review purpose, the submitted manuscripts were assigned to one of 11 scientific areas according to authors’ preference and research topic, allowing for minor adjustments to avoid conflicts of interest. In addition to selecting an area, the authors could also designate a particular Community of Special Interest (COSI; Table 1) that would provide the best forum for presentation of their paper. The research areas covered a broad spectrum of topics (Table 2) and also included a special General Computational Biology area intended for submissions on emerging topics or for those manuscripts that did not fit well in other reviewing areas. COSI distribution of accepted ISMB 2023 Proceedings papers. Thematic areas of ISMB/ECCB 2023 proceedings talks. The table lists the Area Chairs for each theme, the number of reviewed papers, the number of accepted papers, and the acceptance rate for each area. The reviewing of the submissions was overseen by the Senior Program Committee (SPC), which included the Proceedings Chairs (this editorial’s authors) and Area Chairs (AC, listed in Table 2). Several of the ACs were nominated by COSIs or by the ISMB Steering Committee. Members of the SPC were responsible for recruiting the Program Committee. Reviewers (Program Committee Members and subreviewers) judged the papers based on the novelty of computational approaches, relevance of biological questions, importance of biological insights, clarity of presentations, expected impact, compatibility with the conference format and, most importantly, correctness, completeness, and reproducibility of the studies. After submitting their reviews, the reviewers had the opportunity to discuss the papers and refine the scores. The ACs facilitated these discussions, oversaw the review process and made sure reviews were detailed and consistent with the overall decision. Final acceptance decisions were made in agreement with the entire SPC. Throughout the reviewing process, we followed a stringent policy of guarding conflicts of interest. Submissions that had any association to an Area Chair were reassigned to a different area. Care was taken not to assign papers to reviewers with a perceived conflict either (e.g. co-authorship or same institution). The definition of conflict was defined as broadly as possible—including collaborators (present and past few years), same institution (present, past few years, planned future moves), family relations, advisees/advisors, as well as any personal conflicts that could cause the appearance of conflict of interest, or that could genuinely interfere with objective reviewing. Finally, as Proceedings Chairs, we refrained from submitting papers to the conference. Among the 336 submissions, 60 were accepted for presentation at ISMB/ECCB 2023 and publication in the proceedings, conditioned on revisions having properly addressed the comments of the reviewers. In a few cases, the authors had to be reminded to release their source code alongside their manuscript, or clarify some aspects of their evaluations. This year, all conditionally accepted papers were revised and subsequently judged to have properly addressed the concerns of the reviewers. They were subsequently accepted for the conference proceedings, resulting in a 17.9% acceptance rate overall. The acceptance rates for individual Areas are shown in Table 2. Accepted papers were assigned to COSIs based on the preferences of both authors and COSI organizers (Table 1). We are deeply grateful to the Area Chairs, the 317 members of the Program Committee and the 368 subreviewers for their outstanding efforts in conducting thorough and timely reviews. Their contribution is at the core of the scientific quality of the conference. We also thank Steven Leard, Diane Kovats, and Seth Munholland for their support, guidance, and handling logistical questions and all the other members of the ISMB Steering Committee for their expert advise and supervision. We also thank the team at Oxford University Press for producing this special proceedings volume. We finally thank all the authors for submitting their work. These proceedings would not be possible without the scientific ingenuity of the contributors of all the papers. We recognize that, despite our best efforts, the selection process is necessarily imperfect, and some outstanding work will have been missed. Nonetheless, we hope that all authors received helpful feedback on their work. Finally, we want to thank all the keynote speakers, presenters, and all conference participants. Thank you all for making this meeting possible and the entire ISMB/ECCB community to continue to thrive. None declared. S.R. was supported by the James McDonnell Foundation Scholar award (220020473). Y.P. was supported by French Agence Nationale de la Recherche through the Decrypted (ANR-19-CE30-0021), PaRNAssus (ANR-19-CE45-0023), and INSSANE (ANR-21-CE45-0034) grants.

BACKGROUND: RNA deleterious point mutation prediction was previously addressed with programs such as RNAmute and MultiRNAmute. The purpose of these programs is to predict a global conformational rearrangement of the secondary structure of a functional RNA molecule, thereby disrupting its function. RNAmute was designed to deal with only single point mutations in a brute force manner, while in MultiRNAmute an efficient approach to deal with multiple point mutations was developed. The approach used in MultiRNAmute is based on the stabilization of the suboptimal RNA folding prediction solutions and/or destabilization of the optimal folding prediction solution of the wild type RNA molecule. The MultiRNAmute algorithm is significantly more efficient than the brute force approach in RNAmute, but in the case of long sequences and large m-point mutation sets the MultiRNAmute becomes exponential in examining all possible stabilizing and destabilizing mutations. RESULTS: An inherent limitation in the RNAmute and MultiRNAmute programs is their ability to predict only substitution mutations, as these programs were not designed to work with deletion or insertion mutations. To address this limitation we herein develop a very fast algorithm, based on suboptimal folding solutions, to predict a predefined number of multiple point deleterious mutations as specified by the user. Depending on the user's choice, each such set of mutations may contain combinations of deletions, insertions and substitution mutations. Additionally, we prove the hardness of predicting the most deleterious set of point mutations in structural RNAs. CONCLUSIONS: We developed a method that extends our previous MultiRNAmute method to predict insertion and deletion mutations in addition to substitutions. The additional advantage of the new method is its efficiency to find a predefined number of deleterious mutations. Our new method may be exploited by biologists and virologists prior to site-directed mutagenesis experiments, which involve indel mutations along with substitutions. For example, our method may help to investigate the change of function in an RNA virus via mutations that disrupt important motifs in its secondary structure.

Budget Minimization is a scheduling problem with precedence constraints, i.e., a scheduling problem on a partially ordered set of jobs $(N, \unlhd)$. A job $j \in N$ is available for scheduling, if all jobs $i \in N$ with $i \unlhd j$ are completed. Further, each job $j \in N$ is assigned real valued costs $c_{j}$, which can be negative or positive. A schedule is an ordering $j_{1}, \dots, j_{\vert N \vert}$ of all jobs in $N$. The budget of a schedule is the external investment needed to complete all jobs, i.e., it is $\max_{l \in \{0, \dots, \vert N \vert \} } \sum_{1 \le k \le l} c_{j_{k}}$. The goal is to find a schedule with minimum budget. Rafiey et al. (2015) showed that Budget Minimization is NP-hard following from a reduction from a molecular folding problem. We extend this result and prove that it is NP-hard to $α(N)$-approximate the minimum budget even on bipartite partial orders. We present structural insights that lead to arguably simpler algorithms and extensions of the results by Rafiey et al. (2015). In particular, we show that there always exists an optimal solution that partitions the set of jobs and schedules each subset independently of the other jobs. We use this structural insight to derive polynomial-time algorithms that solve the problem to optimality on series-parallel and convex bipartite partial orders.

MOTIVATION: Predicting the folding dynamics of RNAs is a computationally difficult problem, first and foremost due to the combinatorial explosion of alternative structures in the folding space. Abstractions are therefore needed to simplify downstream analyses, and thus make them computationally tractable. This can be achieved by various structure sampling algorithms. However, current sampling methods are still time consuming and frequently fail to represent key elements of the folding space. METHOD: We introduce RNAxplorer, a novel adaptive sampling method to efficiently explore the structure space of RNAs. RNAxplorer uses dynamic programming to perform an efficient Boltzmann sampling in the presence of guiding potentials, which are accumulated into pseudo-energy terms and reflect similarity to already well-sampled structures. This way, we effectively steer sampling toward underrepresented or unexplored regions of the structure space. RESULTS: We developed and applied different measures to benchmark our sampling methods against its competitors. Most of the measures show that RNAxplorer produces more diverse structure samples, yields rare conformations that may be inaccessible to other sampling methods and is better at finding the most relevant kinetic traps in the landscape. Thus, it produces a more representative coarse graining of the landscape, which is well suited to subsequently compute better approximations of RNA folding kinetics. AVAILABILITYAND IMPLEMENTATION: https://github.com/ViennaRNA/RNAxplorer/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Molecular docking is a computational technique for predicting how a small molecule might bind a macromolecular target. Among docking programs, AutoDock Vina is particularly popular. Like many docking programs, Vina requires users to download/install an executable file and to run that file from a command-line interface. Choosing proper configuration parameters and analyzing Vina output is also sometimes challenging. These issues are particularly problematic for students and novice researchers. RESULTS: We created Webina, a new version of Vina, to address these challenges. Webina runs Vina entirely in a web browser, so users need only visit a Webina-enabled webpage. The docking calculations take place on the user's own computer rather than a remote server. AVAILABILITY AND IMPLEMENTATION: A working version of the open-source Webina app can be accessed free of charge from http://durrantlab.com/webina. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Hydrogen-deuterium mass spectrometry (HDX-MS) is a rapidly developing technique for monitoring dynamics and interactions of proteins. The development of new devices has to be followed with new software suites addressing emerging standards in data analysis. RESULTS: We propose HaDeX, a novel tool for processing, analysis and visualization of HDX-MS experiments. HaDeX supports a reproducible analytical process, including data exploration, quality control and generation of publication-quality figures. AVAILABILITY AND IMPLEMENTATION: HaDeX is available primarily as a web-server (http://mslab-ibb.pl/shiny/HaDeX/), but its all functionalities are also accessible as the R package (https://CRAN.R-project.org/package=HaDeX) and standalone software (https://sourceforge.net/projects/HaDeX/). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: RNA design has conceptually evolved from the inverse RNA folding problem. In the classical inverse RNA problem, the user inputs an RNA secondary structure and receives an output RNA sequence that folds into it. Although modern RNA design methods are based on the same principle, a finer control over the resulting sequences is sought. As an important example, a substantial number of non-coding RNA families show high preservation in specific regions, while being more flexible in others and this information should be utilized in the design. By using the additional information, RNA design tools can help solve problems of practical interest in the growing fields of synthetic biology and nanotechnology. incaRNAfbinv 2.0 utilizes a fragment-based approach, enabling a control of specific RNA secondary structure motifs. The new version allows significantly more control over the general RNA shape, and also allows to express specific restrictions over each motif separately, in addition to other advanced features. AVAILABILITY AND IMPLEMENTATION: incaRNAfbinv 2.0 is available through a standalone package and a web-server at https://www.cs.bgu.ac.il/incaRNAfbinv. Source code, command-line and GUI wrappers can be found at https://github.com/matandro/RNAsfbinv. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Accounting for biological and practical requirements in DNA sequence design often results in challenging optimization problems. Current software solutions are problem-specific and hard to combine. RESULTS: DNA Chisel is an easy-to-use, easy-to-extend sequence optimization framework allowing to freely define and combine optimization specifications via Python scripts or Genbank annotations. AVAILABILITY AND IMPLEMENTATION: The framework is available as a web application (https://cuba.genomefoundry.org/sculpt_a_sequence) or open-source Python library (see at https://github.com/Edinburgh-Genome-Foundry/DNAChisel for code and documentation). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We present a novel rotation invariant architecture operating directly on point cloud data. We demonstrate how rotation invariance can be injected into a recently proposed point-based PCNN architecture, on all layers of the network. This leads to invariance to both global shape transformations, and to local rotations on the level of patches or parts, useful when dealing with non-rigid objects. We achieve this by employing a spherical harmonics-based kernel at different layers of the network, which is guaranteed to be invariant to rigid motions. We also introduce a more efficient pooling operation for PCNN using space-partitioning data-structures. This results in a flexible, simple and efficient architecture that achieves accurate results on challenging shape analysis tasks, including classification and segmentation, without requiring data-augmentation typically employed by non-invariant approaches. Code and data are provided on the project page https://github.com/adrienPoulenard/SPHnet.

BACKGROUND: The design of multi-stable RNA molecules has important applications in biology, medicine, and biotechnology. Synthetic design approaches profit strongly from effective in-silico methods, which substantially reduce the need for costly wet-lab experiments. RESULTS: We devise a novel approach to a central ingredient of most in-silico design methods: the generation of sequences that fold well into multiple target structures. Based on constraint networks, our approach supports generic Boltzmann-weighted sampling, which enables the positive design of RNA sequences with specific free energies (for each of multiple, possibly pseudoknotted, target structures) and GC-content. Moreover, we study general properties of our approach empirically and generate biologically relevant multi-target Boltzmann-weighted designs for an established design benchmark. Our results demonstrate the efficacy and feasibility of the method in practice as well as the benefits of Boltzmann sampling over the previously best multi-target sampling strategy-even for the case of negative design of multi-stable RNAs. Besides empirically studies, we finally justify the algorithmic details due to a fundamental theoretic result about multi-stable RNA design, namely the #P-hardness of the counting of designs. CONCLUSION: introduces a novel, flexible, and effective approach to multi-target RNA design, which promises broad applicability and extensibility. Our free software is available at: https://github.com/yannponty/RNARedPrint Supplementary data are available online.

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 use distinct approaches, ranging from ant colony 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 toward the future of RNA design programs.

We present a new educational initiative called Meet-U that aims to train students for collaborative work in computational biology and to bridge the gap between education and research. Meet-U mimics the setup of collaborative research projects and takes advantage of the most popular tools for collaborative work and of cloud computing. Students are grouped in teams of 4-5 people and have to realize a project from A to Z that answers a challenging question in biology. Meet-U promotes "coopetition," as the students collaborate within and across the teams and are also in competition with each other to develop the best final product. Meet-U fosters interactions between different actors of education and research through the organization of a meeting day, open to everyone, where the students present their work to a jury of researchers and jury members give research seminars. This very unique combination of education and research is strongly motivating for the students and provides a formidable opportunity for a scientific community to unite and increase its visibility. We report on our experience with Meet-U in two French universities with master's students in bioinformatics and modeling, with protein-protein docking as the subject of the course. Meet-U is easy to implement and can be straightforwardly transferred to other fields and/or universities. All the information and data are available at www.meet-u.org.

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 so-called 'BRaliBase Dent'. In this article, we show this dent is owing to a bias in the composition of the BRaliBase benchmark, namely the inclusion of a disproportionate number of transfer RNAs, which exhibit a 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.

MOTIVATION: Kinetics is key to understand many phenomena involving RNAs, such as co-transcriptional folding and riboswitches. Exact out-of-equilibrium studies induce extreme computational demands, leading state-of-the-art methods to rely on approximated kinetics landscapes, obtained using sampling strategies that strive to generate the key landmarks of the landscape topology. However, such methods are impeded by a large level of redundancy within sampled sets. Such a redundancy is uninformative, and obfuscates important intermediate states, leading to an incomplete vision of RNA dynamics. RESULTS: We introduce RNANR, a new set of algorithms for the exploration of RNA kinetics landscapes at the secondary structure level. RNANR considers locally optimal structures, a reduced set of RNA conformations, in order to focus its sampling on basins in the kinetic landscape. Along with an exhaustive enumeration, RNANR implements a novel non-redundant stochastic sampling, and offers a rich array of structural parameters. Our tests on both real and random RNAs reveal that RNANR allows to generate more unique structures in a given time than its competitors, and allows a deeper exploration of kinetics landscapes. AVAILABILITY AND IMPLEMENTATION: RNANR is freely available at https://project.inria.fr/rnalands/rnanr . CONTACT: [email protected].

UNLABELLED: : A gene tree-species tree reconciliation explains the evolution of a gene tree within the species tree given a model of gene-family 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 species-tree aware gene trees using amalgamation. AVAILABILITY AND IMPLEMENTATION: ecceTERA is freely available under http://mbb.univ-montp2.fr/MBB/download_sources/16__ecceTERA and can be run online at http://mbb.univ-montp2.fr/MBB/subsection/softExec.php?soft=eccetera CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The reconstruction of evolutionary scenarios for whole genomes in terms of genome rearrangements is a fundamental problem in evolutionary and comparative genomics. The DeCo algorithm, recently introduced by Bérard et al ., computes parsimonious evolutionary scenarios for gene adjacencies, from pairs of reconciled gene trees. However, as for many combinatorial optimization algorithms, there can exist many co-optimal, or slightly sub-optimal, evolutionary scenarios that deserve to be considered. We extend the DeCo algorithm to sample evolutionary scenarios from the whole solution space under the Boltzmann distribution, and also to compute Boltzmann probabilities for specific ancestral adjacencies. We apply our algorithms to a dataset of mammalian gene trees and adjacencies, and observe a significant reduction of the number of syntenic conflicts observed in the resulting ancestral gene adjacencies.

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 GC-content in their sequences. However, the latter is an important criterion for large-scale 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 high-quality sequences (i.e. thermodynamically stable) for any GC-content. 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 GC-content and target structure. AVAILABILITY: IncaRNAtion is available at csb.cs.mcgill.ca/incarnation/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Large-scale analyses of protein-protein interactions based on coarse-grain molecular docking simulations and binding site predictions resulting from evolutionary sequence analysis, are possible and realizable on hundreds of proteins with variate structures and interfaces. We demonstrated this on the 168 proteins of the Mintseris Benchmark 2.0. On the one hand, we evaluated the quality of the interaction signal and the contribution of docking information compared to evolutionary information showing that the combination of the two improves partner identification. On the other hand, since protein interactions usually occur in crowded environments with several competing partners, we realized a thorough analysis of the interactions of proteins with true partners but also with non-partners to evaluate whether proteins in the environment, competing with the true partner, affect its identification. We found three populations of proteins: strongly competing, never competing, and interacting with different levels of strength. Populations and levels of strength are numerically characterized and provide a signature for the behavior of a protein in the crowded environment. We showed that partner identification, to some extent, does not depend on the competing partners present in the environment, that certain biochemical classes of proteins are intrinsically easier to analyze than others, and that small proteins are not more promiscuous than large ones. Our approach brings to light that the knowledge of the binding site can be used to reduce the high computational cost of docking simulations with no consequence in the quality of the results, demonstrating the possibility to apply coarse-grain docking to datasets made of thousands of proteins. Comparison with all available large-scale analyses aimed to partner predictions is realized. We release the complete decoys set issued by coarse-grain docking simulations of both true and false interacting partners, and their evolutionary sequence analysis leading to binding site predictions. Download site: http://www.lgm.upmc.fr/CCDMintseris/

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 pixel-based (JPEG, PNG) or vector-based (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 command-line 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.

Abstract Summary: 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 context-free grammars, regular expressions and PROSITE expressions. GenRGenS is the only program that can handle weighted context-free 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 Contact: [email protected]

We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models, 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.