Automated design of dynamic programming schemes for RNA folding with pseudoknots.

Although RNA secondary structure prediction is a textbook application of dynamic programming (DP) and routine task in RNA structure analysis, it remains challenging whenever pseudoknots come into play. Since the prediction of pseudoknotted structures by minimizing (realistically modelled) energy is NP-hard, specialized algorithms have been proposed for restricted conformation classes that capture the most frequently observed configurations. To achieve good performance, these methods rely on specific and carefully hand-crafted DP schemes.

Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics.

Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the input graph. In order to extend their scope of applicability, we introduce the TREE-DIET problem, i.

Sorting Signed Permutations by Intergenic Reversals.

Genome rearrangements are mutations affecting large portions of a genome, and a reversal is one of the most studied genome rearrangements in the literature through the Sorting by Reversals (SbR) problem. SbR is solvable in polynomial time on signed permutations (i.e.

Genome rearrangements with indels in intergenes restrict the scenario space.

Background: Given two genomes that have diverged by a series of rearrangements, we infer minimum Double Cut-and-Join (DCJ) scenarios to explain their organization differences, coupled with indel scenarios to explain their intergene size distribution, where DCJs themselves also alter the sizes of broken intergenes.

Results: We give a polynomial-time algorithm that, given two genomes with arbitrary intergene size distributions, outputs a DCJ scenario which optimizes on the number of DCJs, and given this optimal number of DCJs, optimizes on the total sum of the sizes of the indels.

Conclusions: We show that there is a valuable information in the intergene sizes concerning the rearrangement scenario itself.

A Combinatorial Algorithm for Microbial Consortia Synthetic Design.

Synthetic biology has boomed since the early 2000s when it started being shown that it was possible to efficiently synthetize compounds of interest in a much more rapid and effective way by using other organisms than those naturally producing them. However, to thus engineer a single organism, often a microbe, to optimise one or a collection of metabolic tasks may lead to difficulties when attempting to obtain a production system that is efficient, or to avoid toxic effects for the recruited microorganism. The idea of using instead a microbial consortium has thus started being developed in the last decade.

Inapproximability of (1,2)-exemplar distance.

Given two genomes possibly with duplicate genes, the exemplar distance problem is that of removing all but one copy of each gene in each genome, so as to minimize the distance between the two reduced genomes according to some measure. Let $((s,t))$-exemplar distance denote the exemplar distance problem on two genomes $(G_1)$ and $(G_2)$, where each gene occurs at most $(s)$ times in $(G_1)$ and at most $(t)$ times in $(G_2)$. We show that the simplest nontrivial variant of the exemplar distance problem, $((1,2))$-Exemplar Distance, is already hard to approximate for a wide variety of distance measures, including both popular genome rearrangement measures such as adjacency disruptions, signed reversals, and signed double-cut-and-joins, and classic string edit distance measures such as Levenshtein and Hamming distances.