Search

Genome rearrangement distance problems allow to estimate the evolutionary distance between genomes. These problems aim to compute the minimum number of mutations called rearrangement events necessary to transform one genome into another. Two commonly studied rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which exchanges two consecutive sequences of genes. Seminal works on this topic focused on the sequence of genes and assumed that each gene occurs exactly once on each genome. More realistic models have been assuming that a gene may have multiple copies or may appear in only one of the genomes. Other models also take into account the nucleotides between consecutive pairs of genes, which are called intergenic regions. This work combines all these generalizations defining the signed intergenic reversal distance (SIRD), the signed intergenic reversal and transposition distance (SIRTD), the signed intergenic reversal and indels distance (SIRID), and the signed intergenic reversal, transposition, and indels distance (SIRTID) problems. We show a relation between these problems and the signed minimum common intergenic string partition (SMCISP) problem. From such relation, we derive Θ (k) -approximation algorithms for the SIRD and the SIRTD problems, where k is maximum number of copies of a gene in the genomes. These algorithms also work as heuristics for the SIRID and SIRTID problems. Additionally, we present some parametrized algorithms for SMCISP that ensure constant approximation factors for the distance problems. Our experimental tests on simulated genomes show an improvement on the rearrangement distances with the use of the partition algorithms. [ABSTRACT FROM AUTHOR]

Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-cut rearrangement which cuts a permutation (or a string) at k ≥ 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, and that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations. We also show a 1.5-approximation algorithm for the specific case k = 4 , as well as a generic approximation algorithm applicable for any k ≥ 5 , that always reaches constant ratio. The latter makes use of the cycle graph, a well-known structure in genome rearrangements. We implemented and tested the proposed algorithms on simulated data. [ABSTRACT FROM AUTHOR]

Nearest neighbors graphs have gained a lot of attention from the information retrieval community since they were demonstrated to outperform classical approaches in the task of approximate nearest neighbor search. These approaches, firstly, index feature vectors by using a graph-based data structure. Then, for a given query, the search is performed by traversing the graph in a greedy-way, moving in each step towards the neighbor of the current vertex that is closer to the query (based on a distance function). However, local topological properties of vertices could be also considered at the moment of deciding the next vertex to be explored. In this work, we introduce a Genetic Programming framework that combines topological properties along with the distance to the query, aiming to improve the selection of the next vertex in each step of graph traversal and, therefore, reduce the number of vertices explored (scan rate) to find the true nearest neighbors. Experimental results, conducted over three large collections of feature vectors and four different graph-based techniques, show significant gains of the proposed approach over classic graph-based search algorithms. [ABSTRACT FROM AUTHOR]

Comparative genomics is a field of biology that aims at comparing genomes of different species. One major question of this field is to find the evolutionary distance between two given genomes. One way to estimate such distance is to use the rearrangement distance, which consists in finding a minimum cost sequence of rearrangements that transforms one genome into another. We use permutations to model the genomes being compared and, in this way, we can treat this problem as the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the early works with rearrangement distance, it was considered that all rearrangements are equally likely to occur and, consequently, they use a unitary cost for all rearrangements. Some variations of the problem were motivated by the observation that rearrangements involving large segments of a genome rarely occur. One of these variants also uses a unitary cost, however it adds a constraint in the length of the operations allowed to estimate the distance. Another variant uses a cost function based on the rearrangement's length. In this work, we study problems that combine both variants, that is, problems with a constraint in the rearrangement's length and with a cost function based on the rearrangement's length. We present approximation algorithms for five such problems involving reversals and/or transpositions for sorting signed and unsigned permutations. We also analyze the problems for specific parameters of the length restriction and for when the cost function is equal to ℓ α , where ℓ is the rearrangement's length and α ≥ 1 is a real value parameter. [ABSTRACT FROM AUTHOR]

Image phylogeny is the problem of reconstructing the structure that represents the history of generation of semantically similar images (e.g., near-duplicate images). Typical image phylogeny approaches break the problem into two steps: (1) estimating the dissimilarity between each pair of images and (2) reconstructing the phylogeny structure. Given that the dissimilarity calculation directly impacts the phylogeny reconstruction, in this paper, we propose new approaches to the standard formulation of the dissimilarity measure employed in image phylogeny, aiming at improving the reconstruction of the tree structure that represents the generational relationships between semantically similar images. These new formulations exploit a different method of color adjustment, local gradients to estimate pixel differences and mutual information as a similarity measure. The results obtained with the proposed formulation remarkably outperform the existing counterparts in the literature, allowing a much better analysis of the kinship relationships in a set of images, allowing for more accurate deployment of phylogeny solutions to tackle traitor tracing, copyright enforcement and digital forensics problems. [ABSTRACT FROM AUTHOR]