Genome Rearrangement distance problems are used in Computational Biology to estimate the evolutionary distance between genomes. These problems consist of minimizing the number of rearrangement events necessary to transform one genome into another. Two commonly used rearrangement events are reversal and transposition. The first studied problems ignored nucleotides outside genes (called intergenic regions), or assumed that genomes have a single copy of each gene. Recent works made advancements in more general problems considering the number of nucleotides in intergenic regions, and replicated genes. Nevertheless, genomes tend to have wildly different quantities of nucleotides on their intergenic regions, which poses a problem when comparing these regions exactly. To overcome this limitation, our work considers some flexibility when matching intergenic regions that do not have the same number of nucleotides. We propose new problems seeking the minimum number of reversals, or reversals and transpositions, necessary to transform one genome into another, while considering flexible intergenic region information. We show approximations for these problems by exploring their relationship with the Signed Minimum Common Flexible Intergenic String Partition problem. We also present different heuristics for the partition problem, and conduct experimental tests on simulated genomes to assess the performance of our algorithms.

BACKGROUND: Although the development of sequencing technologies has provided a large number of protein sequences, the analysis of functions that each one plays is still difficult due to the efforts of laboratorial methods, making necessary the usage of computational methods to decrease this gap. As the main source of information available about proteins is their sequences, approaches that can use this information, such as classification based on the patterns of the amino acids and the inference based on sequence similarity using alignment tools, are able to predict a large collection of proteins. The methods available in the literature that use this type of feature can achieve good results, however, they present restrictions of protein length as input to their models. In this work, we present a new method, called TEMPROT, based on the fine-tuning and extraction of embeddings from an available architecture pre-trained on protein sequences. We also describe TEMPROT+, an ensemble between TEMPROT and BLASTp, a local alignment tool that analyzes sequence similarity, which improves the results of our former approach. RESULTS: The evaluation of our proposed classifiers with the literature approaches has been conducted on our dataset, which was derived from CAFA3 challenge database. Both TEMPROT and TEMPROT+ achieved competitive results on [Formula: see text], [Formula: see text], AuPRC and IAuPRC metrics on Biological Process (BP), Cellular Component (CC) and Molecular Function (MF) ontologies compared to state-of-the-art models, with the main results equal to 0.581, 0.692 and 0.662 of [Formula: see text] on BP, CC and MF, respectively. CONCLUSIONS: The comparison with the literature showed that our model presented competitive results compared the state-of-the-art approaches considering the amino acid sequence pattern recognition and homology analysis. Our model also presented improvements related to the input size that the model can use to train compared to the literature methods.

Recent works on genome rearrangements have shown that incorporating intergenic region information along with gene order in models provides better estimations for the rearrangement distance than using gene order alone. The reversal distance is one of the main problems in genome rearrangements. It has a polynomial time algorithm when only gene order is used to model genomes, assuming that repeated genes do not exist and that gene orientation is known, even when the genomes have distinct gene sets. The reversal distance is NP-hard and has a 2-approximation algorithm when incorporating intergenic regions. However, the problem has only been studied assuming genomes with the same set of genes. In this work, we consider the variation that incorporates intergenic regions and that allows genomes to have distinct sets of genes, a scenario that leads us to include indels operations (insertions and deletions). We present a 2.5-approximation algorithm using the labeled intergenic breakpoint graph, which is based on the well-known breakpoint graph structure. We also present an experimental analysis of the proposed algorithm using simulated data, which showed that the practical approximation factor is considerably less than 2.5. Furthermore, we used the algorithm in real genomes to construct a phylogenetic tree.

Most mathematical models for genome rearrangement problems have considered only gene order. In this way, the rearrangement distance considering some set of events, such as reversal and transposition events, is commonly defined as the minimum number of rearrangement events that transform the gene order from a genome$\mathcal {G}_{1}$into the gene order from a genome$\mathcal {G}_{2}$. Recent works initiate incorporating more information such as the sizes of the intergenic regions (i.e., number of nucleotides between pairs of consecutive genes), which yields good results for estimated distances on real data. In these models, besides transforming the gene order, the sequence of rearrangement events must transform the list of intergenic regions sizes from$\mathcal {G}_{1}$into the list of intergenic regions sizes from$\mathcal {G}_{2}$(target list). We study a new variation where the target list is flexible, in the sense that each target intergenic region size is in a range of acceptable values. This allows us to model scenarios where the main objective is still to transform the order of genes from the source genome into the target genome, allowing flexibility in the sizes of the intergenic regions, since the nucleotides in these regions tend to undergo more changes when compared to genes. We investigate the rearrangement distance considering three sets of events, two with the exclusive use of reversals or transpositions, and the other allowing both rearrangement events. We present approximation algorithms for the problems and an NP-hardness proof. Our results rely on the Flexible Weighted Cycle Graph, adapted from the breakpoint graph to deal with flexible intergenic regions sizes.

Biologists have proposed a vast list of problems heavily studied by mathematicians, computer scientists, and statisticians. From a theoretical point of view, biology can inspire exciting new problems when one is interested in estimating genetic modifications that occurred in the course of evolution. Structural modifications, such as genome rearrangements, are important for comparative genomics and they have led to many NP-hard problems. Reversal and Transposition are the most studied genome rearrangement events. To solve these problems, the gene order inside a genome is usually mapped into a permutation or a string. Permutations do not allow us to work with duplicate genes; in this case strings should be used. Problems with reversals and transpositions on permutations and strings are being studied since the 70s. Recently, studies start incorporating information regarding the size of the intergenic regions, which are genetic regions between each pair of consecutive genes inside the genome with a specific number of nucleotides. Problems can differ by changing the genetic information carried into the representation model, but all of them aim to transform a source genome into a target genome. In this work, we study the Sorting by Reversals with Flexible Intergenic Regions and Sorting by Reversals and Transpositions with Flexible Intergenic Regions problems on unsigned permutations. The goal is still to transform a source genome into the target genome, but turning the constraint less strict regarding the size of the intergenic regions on the target genome. We present a theoretical study showing that both problems are NP-hard and algorithms with constant approximation factor.

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., the gene orientation is known), and it is NP-hard on unsigned permutations. This problem (and many others considering genome rearrangements) models genome as a list of its genes in the order they appear, ignoring all other information present in the genome. Recent works claimed that the incorporation of the size of intergenic regions, i.e., sequences of nucleotides between genes, may result in better estimators for the real distance between genomes. Here we introduce the Sorting Signed Permutations by Intergenic Reversals problem, that sorts a signed permutation using reversals both on gene order and intergenic sizes. We show that this problem is NP-hard by a reduction from the 3-partition problem. Then, we propose a 2-approximation algorithm for it. Finally, we also incorporate intergenic indels (i.e., insertions or deletions of intergenic regions) to overcome a limitation of sorting by conservative events (such as reversals) and propose two approximation algorithms.

Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data.

In comparative genomics, one goal is to find similarities between genomes of different organisms. Comparisons using genome features like genes, gene order, and regulatory sequences are carried out with this purpose in mind. Genome rearrangements are mutational events that affect large extensions of the genome. They are responsible for creating extant species with conserved genes in different positions across genomes. Close species - from an evolutionary point of view - tend to have the same set of genes or share most of them. When we consider gene order to compare two genomes, it is possible to use a parsimony criterion to estimate how close the species are. We are interested in the shortest sequence of genome rearrangements capable of transforming one genome into the other, which is named rearrangement distance. Reversal is one of the most studied genome rearrangements events. This event acts in a segment of the genome, inverting the position and the orientation of genes in it. Transposition is another widely studied event. This event swaps the position of two consecutive segments of the genome. When the genome has no gene repetition, a common approach is to map it as a permutation such that each element represents a conserved block. When genomes have replicated genes, this mapping is usually performed using strings. The number of replicas depends on the organisms being compared, but in many scenarios, it tends to be small. In this work, we study the rearrangement distance between genomes with replicated genes considering that the orientation of genes is unknown. We present four heuristics for the problem of genome rearrangement distance with replicated genes. We carry out experiments considering the exclusive use of the reversals or transpositions events, as well as the version in which both events are allowed. We developed a database of simulated genomes and compared our results with other algorithms from the literature. The experiments showed that our heuristics with more sophisticated rules presented a better performance than the known algorithms to estimate the evolutionary distance between genomes with replicated genes. In order to validate the application of our algorithms in real data, we construct a phylogenetic tree based on the distance provided by our algorithm and compare it with a know tree from the literature.

Information coming from social media is vital to the understanding of the dynamics involved in multiple events such as terrorist attacks and natural disasters. With the spread and popularization of cameras and the means to share content through social networks, an event can be followed through many different lenses and vantage points. However, social media data present numerous challenges, and frequently it is necessary a great deal of data cleaning and filtering techniques to separate what is related to the depicted event from contents otherwise useless. In a previous effort of ours, we decomposed events into representative components aiming at describing vital details of an event to characterize its defining moments. However, the lack of minimal supervision to guide the combination of representative components somehow limited the performance of the method. In this paper, we extend upon our prior work and present a learning-from-data method for dynamically learning the contribution of different components for a more effective event representation. The method relies upon just a few training samples (few-shot learning), which can be easily provided by an investigator. The obtained results on real-world datasets show the effectiveness of the proposed ideas.

Effective tools for detection of violence are highly demanded, specially when dealing with video streams. Such tools have a wide range of applications, from forensics and law enforcement to parental control over the ever increasing amount of videos available online. Prior studies showed that deep learning has great potential in detecting violence, but focuses on detecting violence in general, or only specific cases of violent behavior. While the concept of violence is broad and highly subjective, simpler concepts such as fights, explosions, and gunshots, convey the idea of violence while being more objective. Even though different concepts relate to this same broader idea of violence, they differ widely in relation to whether or not they convey the idea of movement, the presence of a specific object, or even if they generate distinctive sounds. In this study, we propose to analyze different concepts related to violence and how to better describe these concepts exploring visual and auditory cues in order to reach a robust method to detect violence.

We present three heuristics-Sliding Window, Look Ahead, and Iterative Sliding Window-to improve solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem. We investigate the classical version of the problem as well as versions restricted to prefix and prefix or suffix operations. To assess the heuristics based on its improvement, we implemented algorithms described in the literature to provide initial solutions. Although we have a limited number of problems, these heuristics can be applied to many others within the area of genome rearrangement. When time is a crucial factor, Sliding Window is a better choice because it runs in linear time. If the quality of the solution is a priority, Look Ahead should be preferred. Iterative Sliding Window is the most flexible heuristic and allows us to find a trade-off for specific scenarios where running time and solution quality are relevant.

Violence detection in videos aims to identify whether a violent action occurred within a video stream. Effective tools for intelligent video analysis are highly demanded, specially to determine violence in video streams. Such solution could have applications in detecting inappropriate behaviors in video feeds, aiding law-enforcement in forensic cases, protecting children from accessing inappropriate online content and helping parents making informed decisions about what their kids should watch. Prior art on violence detection, particularly recently proposed deep learning based ones, seeks to identify violence in videos as a whole, without considering breaking down the subject into some of its underlying concepts. In this paper, we explore a different methodology of violence detection, which relies upon two deep neural network (DNNs) frameworks to learn spatial-temporal information on video clips under different scenarios - subjective- and conceptual-based. We leverage deep feature representations for each specific concept, and aggregate them by training a shallow neural network as a binary-classification problem to describe violence as a whole. Finally, we show that using more specific concepts is an intuitive and effective solution, besides being complementary to form a more robust definition of violence.

The use of nearest neighbors graphs has been leading to considerable gains over classic approaches (e.g., tree-indexing-based methods) in approximate nearest neighbor searches. Classical searches on these graphs are conduced in a greedy way by moving at each step to the neighbor (of current vertex) with the lowest distance to the query. In this work, we explore the combination of topological properties of graphs and the distance itself through a Genetic Programming framework to obtain a better indicator for selecting the next vertex in the search process. Our objective is to minimize the scan rate needed to reach the true nearest neighbors. Experimental results, conducted with three different graph-based methods over a large textual collection, show significant gains of the proposed approach over the classic search algorithm on graphs.

Detecting violence in videos through automatic means is significant for law enforcement and analysis of surveillance cameras with the intent of maintaining public safety. Moreover, it may be a great tool for protecting children from accessing inappropriate content and help parents make a better informed decision about what their kids should watch. However, this is a challenging problem since the very definition of violence is broad and highly subjective. Hence, detecting such nuances from videos with no human supervision is not only technical, but also a conceptual problem. With this in mind, we explore how to better describe the idea of violence for a convolutional neural network by breaking it into more objective and concrete parts. Initially, our method uses independent networks to learn features for more specific concepts related to violence, such as fights, explosions, blood, etc. Then we use these features to classify each concept and later fuse them in a meta-classification to describe violence. We also explore how to represent time-based events in still-images as network inputs; since many violent acts are described in terms of movement. We show that using more specific concepts is an intuitive and effective solution, besides being complementary to form a more robust definition of violence. When compared to other methods for violence detection, this approach holds better classification quality while using only automatic features.

Genome Rearrangements are large-scale mutational events that affect genomes during the evolutionary process. Therefore, these mutations differ from punctual mutations. They can move genes from one place to the other, change the orientation of some genes, or even change the number of chromosomes. In this work, we deal with inversion events which occur when a segment of DNA sequence in the genome is reversed. In our model, each inversion costs the number of elements in the reversed segment. We present a new algorithm for this problem based on the metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) that has been routinely used to find solutions for combinatorial optimization problems. In essence, we implemented an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated. Our analysis shows that we outperform any other approach by significant margin. We also use our algorithm to build phylogenetic trees for a subset of species in the Yersinia genus and we compared our trees to other results in the literature.

We consider the problem of sorting a circular permutation by super short reversals (i.e., reversals of length at most 2), a problem that finds application in comparative genomics. Polynomial-time solutions to the unsigned version of this problem are known, but the signed version remained open. In this paper, we present the first polynomial-time solution to the signed version of this problem. Moreover, we perform experiments for inferring phylogenies of two different groups of bacterial species and compare our results with the phylogenies presented in previous works. Finally, to facilitate phylogenetic studies based on the methods studied in this paper, we present a web tool for rearrangement-based phylogenetic inference using short operations, such as super short reversals.

The ever-increasing number of gadgets being used to create digital content, as well as the easiness in sharing, editing, and republishing this content, brings the problem of dealing with a large amount of digital objects (e.g., images or videos) whose content is very similar. Some issues faced by investigators of digital crimes when analyzing this type of data include finding the original source of a suspect image, and the responsible for first publishing it. It is also challenging to determine how these objects are related to each other. Recent efforts in developing algorithms to find automatically the underlying relationship among groups of digital media objects with similar content have been explored in the multimedia phylogeny field. A tree structure is used to represent the relationship among these objects, inspired by the phylogenetic trees in biology. Discovering whether these objects came from the same source or from different sources is fundamentally a clustering problem: 1) related objects belong to the same cluster (tree) and 2) unrelated objects should fit in different clusters. In this paper, we address the problem of finding these clusters in sets of semantically similar images, prior to tree reconstruction. We propose the combination of manifold learning and spectral clustering approaches, which have been successfully used in different applications embedding the original data into a lower, but meaningful, dimensional space. Experiments with more than 40 000 test cases show that the proposed approach improves the accuracy in finding the correct number of trees in the set, as well as the reconstruction of the phylogeny trees.

Recently, several studies have been concerned with modeling the parenthood relationships between near duplicates in a set of images. Two images share a parenthood relationship if one is obtained by applying transformations to the other. However, this is not the only form of parenting that can exist among images. An image might be a composition created through the combination of the semantic information existent in two or more source images, establishing a relationship between the sources and the composite. The problem of identifying these relations in a set containing near-duplicate subsets of source and composition images is referred to as multiple parenting phylogeny. Thus far, researchers tackled this problem with a three-step solution: 1) separation of near-duplicate groups; 2) classification of the relations between the groups; and 3) identification of the images used to create the original composition. In this work, we extend upon this framework by introducing key improvements, such as better identification of when two images share content, and improved ways to compare this content. In addition, we also introduce a new realistic professionally created data set of compositions involving multiple parenting relationships. The method we present in this paper is properly evaluated through quantitative metrics, established for assessing the accuracy in finding multiple parenting relationships. Finally, we discuss some particularities of the framework, such as the importance of an accurate reconstruction of phylogenies and the method's behavior when dealing with more complex compositions.

In the last few years, the amount of videos distributed online has dramatically increased due to the popularity of media sharing platforms (e.g., YouTube, Vimeo, etc.). However, distributed videos are often edited copies of original content, typically referred to as near duplicates. In this paper, we face the problem of reconstructing a video phylogeny tree, i.e., given a set of near-duplicate videos, we want to reconstruct the relationships between every pair of videos to detect which one generated the others and trace back their evolution history. Solving this problem is of paramount importance when the first published video within a set is sought, e.g., to solve copyright infringement cases or to pinpoint criminal impersonation online. The technique we propose exploits the same rationale of previous works in the field of image and video phylogeny. However, we embed in the commonly used pipeline of operations the possibility of dealing with temporally misaligned and encoded video sequences, thus making the method applicable to user-generated videos shared on online platforms. Results computed on a wide dataset of video sequences highlight the importance of taking care of both coding and misalignment in the reconstruction pipeline.

Large-scale mutational events that occur when stretches of DNA sequence move throughout genomes are called genome rearrangements. In bacteria, inversions are one of the most frequently observed rearrangements. In some bacterial families, inversions are biased in favor of symmetry as shown by recent research. In addition, several results suggest that short segment inversions are more frequent in the evolution of microbial genomes. Despite the fact that symmetry and length of the reversed segments seem very important, they have not been considered together in any problem in the genome rearrangement field. Here, we define the problem of sorting genomes (or permutations) using inversions whose costs are assigned based on their lengths and asymmetries. We consider two formulations of the same problem depending on whether we know the orientation of the genes. Several procedures are presented and we assess these procedure performances on a large set of more than 4.4 × 109 permutations. The ideas presented in this paper provide insights to solve the problem and set the stage for a proper theoretical analysis.

Image phylogeny deals with tracing back parent-child relationships among near duplicates, images that share the same semantic content. This approach results in a visual structure showing the inheritance of semantic content among images, called phylogeny tree. In this paper, we extend upon the image phylogeny's original formulation, which considers that an image may inherit content from only a single parent, to deal with situations whereby an image may inherit it from multiple different parents. Our objective is to find the multiple parenting relationships in a set of images, a problem which we refer to as multiple parenting phylogeny. The proposed solution works by first identifying near-duplicate groups and reconstructing their phylogenies; then among the found groups we determine the one(s) representing the composition images; finally, we detect the parenting relations between those compositions and the source images used to create them.

Today, a simple search for an image on the Web can return thousands of related images. Some results are exact copies, some are variants (or near-duplicates) of the same digital image, and others are unrelated. Although we can recognize some of these images as being semantically similar, it is not as straightforward to find which image is the original. It is not easy either to find the chain of transformations used to create each modified version. There are several approaches in the literature to identify near-duplicate images, as well as to reconstruct their relational structure. For the latter, a common representation uses the parent-child relationship, allowing us to visualize the evolution of modifications as a phylogeny tree. However, most of the approaches are restricted to the case of finding the tree of evolution of the near-duplicates, with few works dealing with sets of trees. Since one set of near-duplicates can contain n independent subsets, it is necessary to reconstruct not only one phylogeny tree, but several trees that will compose a phylogeny forest. In this paper, through the analysis of the state-of-the-art image phylogeny algorithms, we introduce a novel approach to deal with phylogeny forests, based on different combinations of these algorithms, aiming at improving their reconstruction accuracy. We analyze the effectiveness of each combination and evaluate our method with more than 40 000 testing cases, using quantitative metrics.

BACKGROUND: Decreasing costs of DNA sequencing have made prokaryotic draft genome sequences increasingly common. A contig scaffold is an ordering of contigs in the correct orientation. A scaffold can help genome comparisons and guide gap closure efforts. One popular technique for obtaining contig scaffolds is to map contigs onto a reference genome. However, rearrangements that may exist between the query and reference genomes may result in incorrect scaffolds, if these rearrangements are not taken into account. Large-scale inversions are common rearrangement events in prokaryotic genomes. Even in draft genomes it is possible to detect the presence of inversions given sufficient sequencing coverage and a sufficiently close reference genome. RESULTS: We present a linear-time algorithm that can generate a set of contig scaffolds for a draft genome sequence represented in contigs given a reference genome. The algorithm is aimed at prokaryotic genomes and relies on the presence of matching sequence patterns between the query and reference genomes that can be interpreted as the result of large-scale inversions; we call these patterns inversion signatures. Our algorithm is capable of correctly generating a scaffold if at least one member of every inversion signature pair is present in contigs and no inversion signatures have been overwritten in evolution. The algorithm is also capable of generating scaffolds in the presence of any kind of inversion, even though in this general case there is no guarantee that all scaffolds in the scaffold set will be correct. We compare the performance of sis, the program that implements the algorithm, to seven other scaffold-generating programs. The results of our tests show that sis has overall better performance. CONCLUSIONS: sis is a new easy-to-use tool to generate contig scaffolds, available both as stand-alone and as a web server. The good performance of sis in our tests adds evidence that large-scale inversions are widespread in prokaryotic genomes.

Nowadays, digital content is widespread and also easily redistributable, either lawfully or unlawfully. Images and other digital content can also mutate as they spread out. For example, after images are posted on the Internet, other users can copy, resize and/or re-encode them and then repost their versions, thereby generating similar but not identical copies. While it is straightforward to detect exact image duplicates, this is not the case for slightly modified versions. In the last decade, some researchers have successfully focused on the design and deployment of near-duplicate detection and recognition systems to identify the cohabiting versions of a given document in the wild. Those efforts notwithstanding, only recently have there been the first attempts to go beyond the detection of near-duplicates to find the structure of evolution within a set of images. In this paper, we tackle and formally define the problem of identifying these image relationships within a set of near-duplicate images, what we call Image Phylogeny Tree (IPT), due to its natural analogy with biological systems. The mechanism of building IPTs aims at finding the structure of transformations and their parameters if necessary, among a near-duplicate image set, and has immediate applications in security and law-enforcement, forensics, copyright enforcement, and news tracking services. We devise a method for calculating an asymmetric dissimilarity matrix from a set of near-duplicate images and formally introduce an efficient algorithm to build IPTs from such a matrix. We validate our approach with more than 625000 test cases, including both synthetic and real data, and show that when using an appropriate dissimilarity function we can obtain good IPT reconstruction even when some pieces of information are missing. We also evaluate our solution when there are more than one near-duplicate sets in the pool of analysis and compare to other recent related approaches in the literature.

SUMMARY: Genomes undergo large structural changes that alter their organization. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are called synteny blocks. Lemaitre et al. presented a new method to precisely delimit rearrangement breakpoints in a genome by comparison with the genome of a related species. Receiving as input a list of one2one orthologous genes found in the genomes of two species, the method builds a set of reliable and non-overlapping synteny blocks and refines the regions that are not contained into them. Through the alignment of each breakpoint sequence against its specific orthologous sequences in the other species, we can look for weak similarities inside the breakpoint, thus extending the synteny blocks and narrowing the breakpoints. The identification of the narrowed breakpoints relies on a segmentation algorithm and is statistically assessed. Here, we present the package Cassis that implements this method of precise detection of genomic rearrangement breakpoints. AVAILABILITY: Perl and R scripts are freely available for download at http://pbil.univ-lyon1.fr/software/Cassis/. Documentation with methodological background, technical aspects, download and setup instructions, as well as examples of applications are available together with the package. The package was tested on Linux and Mac OS environments and is distributed under the GNU GPL License.

Given two genomes represented as circularly ordered sequences of genes, we show a polynomial time algorithm for the minimum weight series of fusion, jissions, and transpositions (with transpositions weighing twice as much as fusions and$ssions) that transforms one genome into the other. The algorithm is based on classical results ofpermutation group theory and is the jirst polynomial result for a genome rearrangement problem involving transpositions. It has been observed in real biological instances that transpositions occur with about ha&- the frequency of reversals. Although we are not using reversals in this study, this observation motivated the double weight assigned to transpositions.

One of the proposed ways to compare genomes or other large DNA molecules is by computing a rearrangement distance, defined as the minimum number of rearrangement events necessary to transform one molecule into another taking into account only the relative order of similar genes. In this work, we study the problem of computing the transposition distance between two linear gene orders, represented by permutations. To help solve it, we present a very simple structure, the breakpoint diagram, and a 2.25-approximation algorithm for the problem based on this structure. While there are better approximation algorithms, they are based on more complex data structures. Our algorithm was implemented in the C programming language and we show experimental results obtained with it on all permutations of up to 11 genes, plus selected permutations of higher size.

In recent years we are seeing increasing interest in research on mutational events acting on large portions of chromosomes. Among these events, a reversal acts on a fragment of a chromosome, reversing the order and orientation of the genes, and a transposition moves fragments from one region to another within a chromosome. We analyze genomes evolving by reversals and transpositions. We present approximation algorithms to compute the reversal and transposition distance for linear permutations, and a lower bound on the reversal and transposition diameter of signed linear permutations.