CREx: inferring genomic rearrangements based on common intervals

SUMMARY: We present the web-based program CREx for heuristically determining pairwise rearrangement events in unichromosomal genomes. CREx considers transpositions, reverse transpositions, reversals and tandem-duplication-random-loss (TDRL) events. It supports the user in finding parsimonious rearrangement scenarios given a phylogenetic hypothesis. CREx is based on common intervals, which reflect genes that appear consecutively in several of the input gene orders. AVAILABILITY: CREx is freely available at http://pacosy.informatik.uni-leipzig.de/crex     

GENESIS: genome evolution scenarios

Summary: We implemented a software tool called GENESIS for threedifferent genome rearrangement problems: Sorting a unichromosomalgenome by weighted reversals and transpositions (SwRT), sortinga multichromosomal genome by reversals, translocations, fusionsand fissions (SRTl), and sorting a multichromosomal genome byweighted reversals, translocations, fusions, fissions and transpositions(SwRTTl). Availability: Source code can be obtained by the authors, oruse the web interface http://www.uni-ulm.de/in/theo/research/genesis.html Contact: simon.gog{at}uni-ulm.de Associate Editor: Chris Stoeckert     

Supercoiling and map stability in the bacterial chromosome

A major goal of comparative genomics is an understanding of the forces which control gene order. This assumes that gene order is important, a supposition backed by the existence of genomic colinearity between many related species. In the bacterial chromosome, a polarity in the order of genes has been suggested, influenced by distance and orientation relative to the origin of DNA replication. We propose a model of the bacterial chromosome in which gene order is maintained by the adaptation of gene expression to local superhelical context. This force acts not directly at the genomic level but rather at the local gene level. A full understanding of gene-order conservation must therefore come from the bottom up. Correspondence to: R.L. Charlebois     

Model of bacterial band formation in aerotaxis

Aerotaxis is a particular form of "energy taxis". It is based on a largely elusive signal transduction machinery. In aerotaxis, oxygen dissolved in water plays the role of both attractant (at moderate concentrations) and repellent (at high and low concentrations). Cells swimming from favorable oxygen concentrations into regions with unfavorable concentrations increase the frequency of reversals, turn back into the favorable domain, and become effectively trapped there. At the same time, bacteria consume oxygen, creating an oxygen gradient. This behavior leads to a pattern formation phenomenon: bacteria self-organize into a dense band at a certain distance from the air-water interface. We incorporate experimental observations of the aerotactic bacterium, Azospirillum brasilense, into a mathematical model. The model consists of a system of differential equations describing swimming bacterial cells and diffusing oxygen. The cells' frequency of reversals depends on the concentration of oxygen and its time derivative while oxygen is depleted by the bacteria. We suggest a hypothetical model of energy sensing mediated by aerotactic receptors Aer and Tsr. Computer simulations and analysis of the model equations allow comparisons of theoretical and experimental results and provide insight into the mechanisms of bacterial pattern formation and underlying signal transduction machinery. We make testable predictions about position and density of the bacterial band.     

Phylogenetic reconstruction from transpositions

Background

Because of the advent of high-throughput sequencing and the consequent reduction in the cost of sequencing, many organisms have been completely sequenced and most of their genes identified. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the rearrangement of these entities through computational means. As a result, genome rearrangement data has attracted increasing attentions from both biologists and computer scientists as a new type of data for phylogenetic analysis. The main events of genome rearrangements include inversions, transpositions and transversions. To date, GRAPPA and MGR are the most accurate methods for rearrangement phylogeny, both assuming inversion as the only event. However, due to the complexity of computing transposition distance, it is very difficult to analyze datasets when transpositions are dominant.

Results

We extend GRAPPA to handle transpositions. The new method is named GRAPPA-TP, with two major extensions: a heuristic method to estimate transposition distance, and a new transposition median solver for three genomes. Although GRAPPA-TP uses a greedy approach to compute the transposition distance, it is very accurate when genomes are relatively close. The new GRAPPA-TP is available from http://phylo.cse.sc.edu/.

Conclusion

Our extensive testing using simulated datasets shows that GRAPPA-TP is very accurate in terms of ancestor genome inference and phylogenetic reconstruction. Simulation results also suggest that model match is critical in genome rearrangement analysis: it is not accurate to simulate transpositions with other events including inversions.

     

Motility patterns of filamentous sulfur bacteria, Beggiatoa spp

The large sulfur bacteria, Beggiatoa spp., live on the oxidation of sulfide with oxygen or nitrate, but avoid high concentrations of both sulfide and oxygen. As gliding filaments, they rely on reversals in the gliding direction to find their preferred environment, the oxygen-sulfide interface. We observed the chemotactic patterns of single filaments in a transparent agar medium and scored their reversals and the glided distances between reversals. Filaments within the preferred microenvironment glided distances shorter than their own length between reversals that anchored them in their position as a microbial mat. Filaments in the oxic region above the mat or in the sulfidic, anoxic region below the mat glided distances longer than the filament length between reversals. This reversal behavior resulted in a diffusion-like spreading of the filaments. A numerical model of such gliding filaments was constructed based on our observations. The model was applied to virtual filaments in the oxygen- and sulfide-free zone of the sediment, which is a main habitat of Beggiatoa in the natural environment. The model predicts a long residence time of the virtual filament in the suboxic zone and explains why Beggiatoa accumulate high nitrate concentrations in internal vacuoles as an alternative electron acceptor to oxygen.     

Genome rearrangement with gene families

MOTIVATION: The theory and practice of genome rearrangement analysis breaks down in the biologically widespread contexts where each gene may be present in a number of copies, not necessarily contiguous. In some of these contexts it is, however, appropriate to ask which members of each gene family in two genomes G and H, lengths lG and lH, are its true exemplars, i.e. which best reflect the original position of the ancestral gene in the common ancestor genome. This entails a search for the two exemplar strings of same length n (= number of gene families, including singletons), having the smallest possible rearrangement distance: the exemplar distance. RESULTS: A branch and bound algorithm calculates these distances efficiently when based on easily calculated traditional rearrangement distances, such as signed reversals distance or breakpoint distance, which also satisfy a property of monotonicity in the number of genes. Simulations show that in two random genomes, the expected exemplar distance/n is sensitive to the number and size of gene families, but approaches 1 as the number of singleton families increases. When the basic rearrangement distance is just the number of breakpoints, the expected cost of computing the exemplar breakpoints distance (EBD), as measured by total calls to the underlying breakpoint distance routine, is highly dependent on both n and the configuration of gene families. On the other hand, basing exemplar distance on exemplar reversals distance (ERD), the expected computing cost depends on the configuration of gene families but is not sensitive to n. AVAILABILITY: Code for EBD and ERD is available from the author or may be accessed at http://www.crm.umontreal.ca/viart/exemplar_di s. html CONTACT: sankoff@ere.umontreal.ca.     

Sorting by weighted reversals, transpositions, and inverted transpositions.

During evolution, genomes are subject to genome rearrangements that alter the ordering and orientation of genes on the chromosomes. If a genome consists of a single chromosome (like mitochondrial, chloroplast, or bacterial genomes), the biologically relevant genome rearrangements are (1) inversions--also called reversals--where a section of the genome is excised, reversed in orientation, and reinserted and (2) transpositions, where a section of the genome is excised and reinserted at a new position in the genome; if this also involves an inversion, one speaks of an inverted transposition. To reconstruct ancient events in the evolutionary history of organisms, one is interested in finding an optimal sequence of genome rearrangements that transforms a given genome into another genome. It is well known that this problem is equivalent to the problem of "sorting" a signed permutation into the identity permutation. In this paper, we provide a 1.5-approximation algorithm for sorting by weighted reversals, transpositions and inverted transpositions for biologically realistic weights.     

Distance-Based Genome Rearrangement Phylogeny

Evolution operates on whole genomes through direct rearrangements of genes, such as inversions, transpositions, and inverted transpositions, as well as through operations, such as duplications, losses, and transfers, that also affect the gene content of the genomes. Because these events are rare relative to nucleotide substitutions, gene order data offer the possibility of resolving ancient branches in the tree of life; the combination of gene order data with sequence data also has the potential to provide more robust phylogenetic reconstructions, since each can elucidate evolution at different time scales. Distance corrections greatly improve the accuracy of phylogeny reconstructions from DNA sequences, enabling distance-based methods to approach the accuracy of the more elaborate methods based on parsimony or likelihood at a fraction of the computational cost. This paper focuses on developing distance correction methods for phylogeny reconstruction from whole genomes. The main question we investigate is how to estimate evolutionary histories from whole genomes with equal gene content, and we present a technique, the empirically derived estimator (EDE), that we have developed for this purpose. We study the use of EDE on whole genomes with identical gene content, and we explore the accuracy of phylogenies inferred using EDE with the neighbor joining and minimum evolution methods under a wide range of model conditions. Our study shows that tree reconstruction under these two methods is much more accurate when based on EDE distances than when based on other distances previously suggested for whole genomes. Electronic Supplementary Material Electronic Supplementary material is available for this article at and accessible for authorised users. [Reviewing Editor: Dr. Martin Kreitman]     

Insertional Mutagenesis of the Maize P Gene by Intragenic Transposition of Ac

The P-rr allele of the maize P gene regulates the synthesis of pigments derived from flavan-4-ol in the pericarp, cob glumes and other floral organs. We characterized 21 P alleles derived by intragenic transposition of Ac from three known positions. Ac transpositions can occur in either direction in the P gene, and with no apparent minimum distance: in one case Ac transposed just 6 bp from its original insertion site. However, the distribution of transposed Ac elements was markedly nonrandom: of 19 transposed Ac elements derived from a single Ac donor, 15 were inserted in a 1.1-kb region at the 5' end of P, while none had inserted in an adjacent 3.2-kb intronic region. All of the Ac insertions affect both pericarp and cob glume pigmentation, providing further evidence that the P-rr allele contains a single gene required for both pericarp and cob glume pigmentation. The distribution of the inserted Ac elements and the phenotype conditioned by each allele suggests a structure of P-rr which is similar to that previously determined molecularly. Possible explanations for the nonrandom distribution of transposed Ac elements are discussed.     

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.     

Low occurrence of gene transposition events during the evolution of the genus Drosophila

Abstract.— The role played by gene transpositions during the evolution of eukaryotic genomes is still poorly understood and indeed has been analyzed in detail only in nematodes. In Drosophila , a limited number of transpositions have been detected by comparing the chromosomal location of genes between different species. The relative importance of gene transposition versus other types of chromosomal rearrangements, for example, inversions, has not yet been evaluated. Here, we use physical mapping to perform an extensive search for long-distance gene transpositions and assess their impact during the evolution of the Drosophila genome. We compare the relative order of 297 molecular markers that cover 60% of the euchromatic fraction of the genome between two related Drosophila species and conclude that the frequency of gene transpositions is very low, namely one order of magnitude lower than that of nematodes. In addition, gene transpositions seem to be events almost exclusively associated with genes of repetitive nature such as the Histone gene complex ( HIS-C ).     

Parametric genome rearrangement

Algorithms inspired by comparative genomics calculate an edit distance between two linear orders based on elementary edit operations such as inversion, transposition and reciprocal translocation. All operations are generally assigned the same weight, simply by default, because no systematic empirical studies exist verifying whether algorithmic outputs involve realistic proportion of each. Nor de we have data on how weights should vary with the length of the inverted or transposed segment of the chromosome. In this paper, we present a rapid algorithm that allows each operation to take on a range of weights, producing an relatively tight bound on the distance between single-chromosome genomes, by means of a greedy search with look-ahead. The efficiency of this algorithm allows us to test random genomes for each parameter setting, to detect gene order similarity and to infer the parameter values most appropriate to the phylogenetic domain under study. We apply this method to genome segments in which the sa me gene order is conserved in Escherichia coli and Bacillus subtilis, as well as to the gene order in human versus Drosophila mitochondrial genomes. In both cases, we conclude that it is most appropriate to assign somewhat more than twice the weight to transpositions and inverted transpositions than to inversions. We also explore segment-length weighting for fungal mitochondrial gene orders.     

ParIS Genome Rearrangement server

SUMMARY: ParIS Genome Rearrangement is a web server for a Bayesian analysis of unichromosomal genome pairs. The underlying model allows inversions, transpositions and inverted transpositions. The server generates a Markov chain using a Partial Importance Sampler technique, and samples trajectories of mutations from this chain. The user can specify several marginalizations to the posterior: the posterior distribution of number of mutations needed to transform one genome into another, length distribution of mutations, number of mutations that have occurred at a given site. Both text and graphical outputs are available. We provide a limited server, a downloadable unlimited server that can be installed locally on any linux/Unix operating system, and a database of mitochondrial gene orders.     

A gene-based genetic linkage map of the collared flycatcher (Ficedula albicollis) reveals extensive synteny and gene-order conservation during 100 million years of avian evolution

By taking advantage of a recently developed reference marker set for avian genome analysis we have constructed a gene-based genetic map of the collared flycatcher, an important "ecological model" for studies of life-history evolution, sexual selection, speciation, and quantitative genetics. A pedigree of 322 birds from a natural population was genotyped for 384 single nucleotide polymorphisms (SNPs) from 170 protein-coding genes and 71 microsatellites. Altogether, 147 gene markers and 64 microsatellites form 33 linkage groups with a total genetic distance of 1787 cM. Male recombination rates are, on average, 22% higher than female rates (total distance 1982 vs. 1627 cM). The ability to anchor the collared flycatcher map with the chicken genome via the gene-based SNPs revealed an extraordinary degree of both synteny and gene-order conservation during avian evolution. The great majority of chicken chromosomes correspond to a single linkage group in collared flycatchers, with only a few cases of inter- and intrachromosomal rearrangements. The rate of chromosomal diversification, fissions/fusions, and inversions combined is thus considerably lower in birds (0.05/MY) than in mammals (0.6-2.0/MY). A dearth of repeat elements, known to promote chromosomal breakage, in avian genomes may contribute to their stability. The degree of genome stability is likely to have important consequences for general evolutionary patterns and may explain, for example, the comparatively slow rate by which genetic incompatibility among lineages of birds evolves.     

Germinal Transpositions of the Maize Element Dissociation from T-DNA Loci in Tomato

We have analyzed the pattern of germinal transpositions of artificial Dissociation (Ds) transposons in tomato. T-DNA constructs carrying Ds were transformed into tomato, and the elements were trans-activated by crossing to lines transformed with a stabilized Activator (sAc) that expressed the transposase gene. The sAc T-DNA carried a GUS gene to monitor its segregation. The Ds elements were inserted in a marker gene so that excision from the T-DNA could be monitored. The Ds elements also carried a genetic marker that was intended to be used for reinsertion selection of the elements after excision. Unfortunately, this gene was irreversibly inactivated on crossing to sAc. Germinal excision frequencies of Ds averaged 15-40%, but there was large variation between and within plants. Southern hybridization analysis of stable transposed Ds elements indicated that although unique transpositions predominate, early transposition events can lead to large clonal sectors in the germline of developing plants and to sibling offspring carrying the same transposition event. Multiple germinal transpositions from three different loci were examined for uniqueness, and 15 different transpositions were identified from each of three T-DNA loci that carried a single independent Ds. These were mapped relative to the donor T-DNA loci, and for each locus 70-80% of the transposed elements were closely linked to the donor site.     

Inferring Models of Bacterial Dynamics toward Point Sources

Experiments have shown that bacteria can be sensitive to small variations in chemoattractant (CA) concentrations. Motivated by these findings, our focus here is on a regime rarely studied in experiments: bacteria tracking point CA sources (such as food patches or even prey). In tracking point sources, the CA detected by bacteria may show very large spatiotemporal fluctuations which vary with distance from the source. We present a general statistical model to describe how bacteria locate point sources of food on the basis of stochastic event detection, rather than CA gradient information. We show how all model parameters can be directly inferred from single cell tracking data even in the limit of high detection noise. Once parameterized, our model recapitulates bacterial behavior around point sources such as the “volcano effect”. In addition, while the search by bacteria for point sources such as prey may appear random, our model identifies key statistical signatures of a targeted search for a point source given any arbitrary source configuration.     

Evolution under reversals: parsimony and conservation of common intervals

In comparative genomics, gene order data is often modeled as signed permutations. A classical problem for genome comparison is to detect common intervals in permutations, that is, genes that are colocalized in several species, indicating that they remained grouped during evolution. A second largely studied problem related to gene order is to compute a minimum scenario of reversals that transforms a signed permutation into another. Several studies began to mix the two problems and it was observed that their results are not always compatible: Often, parsimonious scenarios of reversals break common intervals. If a scenario does not break any common interval, it is called perfect. In two recent studies, Berard et al. defined a class of permutations for which building a perfect scenario of reversals sorting a permutation was achieved in polynomial time and stated as an open question whether it is possible to decide, given a permutation, if there exists a minimum scenario of reversals that is perfect. In this paper, we give a solution to this problem and prove that this widens the class of permutations addressed by the aforementioned studies. We implemented and tested this algorithm on gene order data of chromosomes from several mammal species and we compared it to other methods. The algorithm helps to choose among several possible scenarios of reversals and indicates that the minimum scenario of reversals is not always the most plausible     

Sorting signed circular permutations by super short operations

Background

One way to estimate the evolutionary distance between two given genomes is to determine the minimum number of large-scale mutations, or genome rearrangements, that are necessary to transform one into the other. In this context, genomes can be represented as ordered sequences of genes, each gene being represented by a signed integer. If no gene is repeated, genomes are thus modeled as signed permutations of the form \(\pi =(\pi _1 \pi _2 \ldots \pi _n)\), and in that case we can consider without loss of generality that one of them is the identity permutation \(\iota _n =(1 2 \ldots n)\), and that we just need to sort the other (i.e., transform it into \(\iota _n\)). The most studied genome rearrangement events are reversals, where a segment of the genome is reversed and reincorporated at the same location; and transpositions, where two consecutive segments are exchanged. Many variants, e.g., combining different types of (possibly constrained) rearrangements, have been proposed in the literature. One of them considers that the number of genes involved, in a reversal or a transposition, is never greater than two, which is known as the problem of sorting by super short operations (or SSOs).

Results and conclusions

All problems considering SSOs in permutations have been shown to be in \(\mathsf {P}\), except for one, namely sorting signed circular permutations by super short reversals and super short transpositions. Here we fill this gap by introducing a new graph structure called cyclic permutation graph and providing a series of intermediate results, which allows us to design a polynomial algorithm for sorting signed circular permutations by super short reversals and super short transpositions.