An easy case of sorting by reversals.

We show that a special case of sorting by reversals can be performed in polynomial time, namely, when the number of breakpoints is twice the distance.     

Perfect sorting by reversals is not always difficult

We propose new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals. We describe a combinatorial framework for this problem that allows us to characterize classes of signed permutations for which one can compute, in polynomial time, a shortest reversal scenario that conserves all common intervals. In particular, we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse, and rat     

An algorithm to enumerate sorting reversals for signed permutations.

The rearrangement distance between single-chromosome genomes can be estimated as the minimum number of inversions required to transform the gene ordering observed in one into that observed in the other. This measure, known as "inversion distance," can be computed as the reversal distance between signed permutations. During the past decade, much progress has been made both on the problem of computing reversal distance and on the related problem of finding a minimum-length sequence of reversals, which is known as "sorting by reversals." For most problem instances, however, many minimum-length sequences of reversals exist, and in the absence of auxiliary information, no one is of greater value than the others. The problem of finding all minimum-length sequences of reversals is thus a natural generalization of sorting by reversals, yet it has received little attention. This problem reduces easily to the problem of finding all "sorting reversals" of one permutation with respect to another - that is, all reversals rho such that, if rho is applied to one permutation, then the reversal distance of that permutation from the other is decreased. In this paper, an efficient algorithm is derived to solve the problem of finding all sorting reversals, and experimental results are presented indicating that, while the new algorithm does not represent a significant improvement in asymptotic terms (it takes O(n(3)) time, for permutations of size n; the problem can now be solved by brute force in Theta(n(3)) time), it performs dramatically better in practice than the best known alternative. An implementation of the algorithm is available at www.cse.ucsc.edu/~acs.     

Common intervals and sorting by reversals: a marriage of necessity

This paper revisits the problem of sorting by reversals with tools developed in the context of detecting common intervals. Mixing the two approaches yields new definitions and algorithms for the reversal distance computations, that apply directly on the original permutation. Traditional constructions such as recasting the signed permutation as a positive permutation, or traversing the overlap graph to analyze its connected components, are replaced by elementary definitions in terms of intervals of the permutation. This yields simple linear time algorithms that identify the essential features in a single pass over the permutation and use only simple data structures like arrays and stacks.     

An asymmetric approach to preserve common intervals while sorting by reversals

Background  

The reversal distance and optimal sequences of reversals to transform a genome into another are useful tools to analyse evolutionary scenarios. However, the number of sequences is huge and some additional criteria should be used to obtain a more accurate analysis. One strategy is searching for sequences that respect constraints, such as the common intervals (clusters of co-localised genes). Another approach is to explore the whole space of sorting sequences, eventually grouping them into classes of equivalence. Recently both strategies started to be put together, to restrain the space to the sequences that respect constraints. In particular an algorithm has been proposed to list classes whose sorting sequences do not break the common intervals detected between the two inital genomes A and B. This approach may reduce the space of sequences and is symmetric (the result of the analysis sorting A into B can be obtained from the analysis sorting B into A).     

Listing all parsimonious reversal sequences: new algorithms and perspectives

In comparative genomics studies, finding a minimum length sequences of reversals, so-called sorting by reversals, has been the topic of a huge literature. Since there are many minimum length sequences, another important topic has been the problem of listing all parsimonious sequences between two genomes, called the All Sorting Sequences by Reversals (ASSR) problem. In this article, we revisit the ASSR problem for uni-chromosomal genomes when no duplications are allowed and when the relative order of the genes is known. We put the current body of work in perspective by illustrating the fundamental framework that is common for all of them, a perspective that allows us for the first time to theoretically compare their running times. The article also proposes an improved framework that empirically speeds up all known algorithms.     

The c-SMAC: sorting it all out (or in)

T cells integrate and transduce the key signals necessary to mount an appropriate immune response. To do this, they rely on both secreted factors as well as physical cell-cell contact. Much attention has focused on the organization of proteins at the contact area between a T cell and an antigen-presenting cell, known as the immunological synapse. It has been shown in vitro that proteins segregate into two distinct regions within this contact area, a central area referred to as the c-SMAC, where the T cell receptor and associated signaling molecules are enriched, and a peripheral region called the p-SMAC containing LFA-1 and the scaffolding protein talin. Whether or not these structures form in vivo and how they function in T cell activation remain issues of great interest. Here, we review recently published work and propose several possible functions for the role of the c-SMAC in T cell activation.     

Exploring the solution space of sorting by reversals, with experiments and an application to evolution

In comparative genomics, algorithms that sort permutations by reversals are often used to propose evolutionary scenarios of rearrangements between species. One of the main problems of such methods is that they give one solution while the number of optimal solutions is huge, with no criteria to discriminate among them. Bergeron et al. started to give some structure to the set of optimal solutions, in order to be able to deliver more presentable results than only one solution or a complete list of all solutions. However, no algorithm exists so far to compute this structure except through the enumeration of all solutions, which takes too much time even for small permutations. Bergeron et al. state as an open problem the design of such an algorithm. We propose in this paper an answer to this problem, that is, an algorithm which gives all the classes of solutions and counts the number of solutions in each class, with a better theoretical and practical complexity than the complete enumeration method. We give an example of how to reduce the number of classes obtained, using further constraints. Finally, we apply our algorithm to analyse the possible scenarios of rearrangement between mammalian sex chromosomes.     

Temperature-induced reversals of rotation in phycomyces

The steady state extension and rotation rates of the Phycomyces sporangiophore were measured as a function of temperature. Maximum growth occurred at 27°C; maximum rotation at 28°C. The rotation to extension ratio, a qualitative parameter of cell wall structure, is affected differently by high and low temperatures. Steady state counterclockwise rotation, as opposed to the normal clockwise rotation, was found at both high and low temperatures. The extensional and rotational responses to step changes in temperature were also measured. The conclusions are drawn that a relative decrease in the lysis rate of wall polymer is responsible for the decrease in growth rate at low temperatures, and that a relative increase in the rate of wall synthesis and cross-linking is responsible for the decrease in growth rate at high temperatures. It is suggested that reversals in rotation result from changes in the handedness of the wall's helical structure.     

Analysis of internal loops within the RNA secondary structure in almost quadratic time

MOTIVATION: Evaluating all possible internal loops is one of the key steps in predicting the optimal secondary structure of an RNA molecule. The best algorithm available runs in time O(L(3)), L is the length of the RNA. RESULTS: We propose a new algorithm for evaluating internal loops, its run-time is O(M(*)log(2)L), M < L(2) is a number of possible nucleotide pairings. We created a software tool Afold which predicts the optimal secondary structure of RNA molecules of lengths up to 28 000 nt, using a computer with 2 Gb RAM. We also propose algorithms constructing sets of conditionally optimal multi-branch loop free (MLF) structures, e.g. the set that for every possible pairing (x, y) contains an optimal MLF structure in which nucleotides x and y form a pair. All the algorithms have run-time O(M(*)log(2)L).     

Recovery from the most profound mass extinction of all time

The end-Permian mass extinction, 251 million years (Myr) ago, was the most devastating ecological event of all time, and it was exacerbated by two earlier events at the beginning and end of the Guadalupian, 270 and 260 Myr ago. Ecosystems were destroyed worldwide, communities were restructured and organisms were left struggling to recover. Disaster taxa, such as Lystrosaurus, insinuated themselves into almost every corner of the sparsely populated landscape in the earliest Triassic, and a quick taxonomic recovery apparently occurred on a global scale. However, close study of ecosystem evolution shows that true ecological recovery was slower. After the end-Guadalupian event, faunas began rebuilding complex trophic structures and refilling guilds, but were hit again by the end-Permian event. Taxonomic diversity at the alpha (community) level did not recover to pre-extinction levels; it reached only a low plateau after each pulse and continued low into the Late Triassic. Our data showed that though there was an initial rise in cosmopolitanism after the extinction pulses, large drops subsequently occurred and, counter-intuitively, a surprisingly low level of cosmopolitanism was sustained through the Early and Middle Triassic.     

Competitive reversals and environment-dependent resource partitioning in Erodium

Summary Effects of drought and varying plant density on the competitive coexistence of two winter annual Erodium species were studied using multiple regression analysis. Significant indications of resource partitioning were detected for interspecific mixtures under spring drought. Competitive superiority also was environment-dependent with E. botrys dominating with drought in autumn, while E. brachycarpum dominated with drought in spring. The results suggest that competitive coexistence in Erodium is promoted by processes both equilibrial (e.g., resource partitioning) and nonequilibrial (e.g. competitive reversals).     

STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time

MOTIVATION: Alignment of RNA has a wide range of applications, for example in phylogeny inference, consensus structure prediction and homology searches. Yet aligning structural or non-coding RNAs (ncRNAs) correctly is notoriously difficult as these RNA sequences may evolve by compensatory mutations, which maintain base pairing but destroy sequence homology. Ideally, alignment programs would take RNA structure into account. The Sankoff algorithm for the simultaneous solution of RNA structure prediction and RNA sequence alignment was proposed 20 years ago but suffers from its exponential complexity. A number of programs implement lightweight versions of the Sankoff algorithm by restricting its application to a limited type of structure and/or only pairwise alignment. Thus, despite recent advances, the proper alignment of multiple structural RNA sequences remains a problem. RESULTS: Here we present StrAl, a heuristic method for alignment of ncRNA that reduces sequence-structure alignment to a two-dimensional problem similar to standard multiple sequence alignment. The scoring function takes into account sequence similarity as well as up- and downstream pairing probability. To test the robustness of the algorithm and the performance of the program, we scored alignments produced by StrAl against a large set of published reference alignments. The quality of alignments predicted by StrAl is far better than that obtained by standard sequence alignment programs, especially when sequence homologies drop below approximately 65%; nevertheless StrAl's runtime is comparable to that of ClustalW.