RESUMEN

The transposition distance problem is a classical problem in genome rearrangements, which seeks to determine the minimum number of transpositions needed to transform a linear chromosome into another represented by the permutations π and σ, respectively. This article focuses on the equivalent problem of sorting by transpositions (SBT), where σ is the identity permutation ι. Specifically, we investigate palisades, a family of permutations that are "hard" to sort, as they require numerous transpositions above the celebrated lower bound devised by Bafna and Pevzner. By determining the transposition distance of palisades, we were able to provide the exact transposition diameter for 3-permutations (TD3), a special subset of the symmetric group Sn, essential for the study of approximate solutions for SBT using the simplification technique. The exact value for TD3 has remained unknown since Elias and Hartman showed an upper bound for it. Another consequence of determining the transposition distance of palisades is that, using as lower bound the one by Bafna and Pevzner, it is impossible to guarantee approximation ratios lower than 1.375 when approximating SBT. This finding has significant implications for the study of SBT, as this problem has been the subject of intense research efforts for the past 25 years.

Asunto(s)

RESUMEN

The degree of dissimilarity between genome sequences of homologous species is a measure of the evolutionary distance between them. It serves as a metric in the construction of phylogenetic trees, which depict the evolutionary relationships and common ancestry among different species. Given two genome sequences, evolutionary distance is determined by estimating the number of global mutations that transform one sequence to the other. The computation of the evolutionary distance is done by modelling a genome with the corresponding permutation. Global rearrangement operations such as transposition that model a particular genomic mutation are studied by employing a combinatorial structure known as a cycle graph of the corresponding permutation. A cycle in a cycle graph that has odd length is called an odd cycle. In the context of the problem of sorting by transpositions (SBT), a valid 2-move is a transposition that increases the number of odd cycles in the cycle graph by two. A super oriented cycle (SOC) is an odd cycle C where C and one of the resultant cycles admit valid 2-moves. The minimum number of mutations required to transform a species S into a related species T is the distance from S to T under that mutation. Christie opined that characterizing SOCs will improve the lower bound of the transposition distance. We characterize super oriented cycles. Equivalent transformations on permutations like reduction and (g,b)-split preserve the transposition distance of a given permutation and map SBT to the corresponding SBT on a transformed simpler permutation. We introduce merge, a novel equivalent transformation. These results have applications in computing transposition and other distances between related species.

Asunto(s)

RESUMEN

The most common way to calculate the rearrangement distance between two genomes is to use the size of a minimum length sequence of rearrangements that transforms one of the two given genomes into the other, where the genomes are represented as permutations using only their gene order, based on the assumption that genomes have the same gene content. With the advance of research in genome rearrangements, new works extended the classical models by either considering genomes with different gene content (unbalanced genomes) or including more genomic characteristics to the mathematical representation of the genomes, such as the distribution of intergenic regions sizes. In this study, we study the Reversal, Transposition, and Indel (Insertion and Deletion) Distance using intergenic information, which allows comparing unbalanced genomes, because indels are included in the rearrangement model (i.e., the set of possible rearrangements allowed when we compute the distance). For the particular case of transpositions and indels on unbalanced genomes, we present a 4-approximation algorithm, improving a previous 4.5 approximation. This algorithm is extended so as to deal with gene orientation and to maintain the 4-approximation factor for the Reversal, Transposition, and Indel Distance on unbalanced genomes. Furthermore, we evaluate the proposed algorithms using experiments on simulated data.

Asunto(s)

RESUMEN

Mitochondrial gene order has contributed to the elucidation of evolutionary relationships in several animal groups. It generally has found its application as a phylogenetic marker for deep nodes. Yet, in Orthoptera limited research has been performed on the gene order, although the group represents one of the oldest insect orders. We performed a comprehensive study on mitochondrial genome rearrangements (MTRs) within Orthoptera in the context of mitogenomic sequence-based phylogeny. We used 280 published mitogenome sequences from 256 species, including three outgroup species, to reconstruct a molecular phylogeny. Using a heuristic approach, we assigned MTR scenarios to the edges of the phylogenetic tree and reconstructed ancestral gene orders to identify possible synapomorphies in Orthoptera. We found all types of MTRs in our dataset: inversions, transpositions, inverse transpositions, and tandem-duplication/random loss events (TDRL). Most of the suggested MTRs were in single and unrelated species. Out of five MTRs which were unique in subgroups of Orthoptera, we suggest four of them to be synapomorphies; those were in the infraorder Acrididea, in the tribe Holochlorini, in the subfamily Pseudophyllinae, and in the two families Phalangopsidae and Gryllidae or their common ancestor (leading to the relationship ((Phalangopsidae + Gryllidae) + Trigonidiidae)). However, similar MTRs have been found in distant insect lineages. Our findings suggest convergent evolution of specific mitochondrial gene orders in several species, deviant from the evolution of the mitogenome DNA sequence. As most MTRs were detected at terminal nodes, a phylogenetic inference of deeper nodes based on MTRs is not supported. Hence, the marker does not seem to aid resolving the phylogeny of Orthoptera, but adds further evidence for the complex evolution of the whole group, especially at the genetic and genomic levels. The results indicate a high demand for more research on patterns and underlying mechanisms of MTR events in Orthoptera.

Asunto(s)

RESUMEN

Transposable elements (TEs) are an important part of eukaryotic genomes. The role of somatic transposition in aging, carcinogenesis, and other age-related diseases has been determined. This review discusses the fundamental properties of TEs and their complex interactions with cellular processes, which are crucial for understanding the diverse effects of their activity on the genetics and epigenetics of the organism. The interactions of TEs with recombination, replication, repair, and chromosomal regulation; the ability of TEs to maintain a balance between their own activity and repression, the involvement of TEs in the creation of new or alternative genes, the expression of coding/non-coding RNA, and the role in DNA damage and modification of regulatory networks are reviewed. The contribution of the derepressed TEs to age-dependent effects in individual cells/tissues in different organisms was assessed. Conflicting information about TE activity under stress as well as theories of aging mechanisms related to TEs is discussed. On the one hand, transposition activity in response to stressors can lead to organisms acquiring adaptive innovations of great importance for evolution at the population level. On the other hand, the TE expression can cause decreased longevity and stress tolerance at the individual level. The specific features of TE effects on aging processes in germline and soma and the ways of their regulation in cells are highlighted. Recent results considering somatic mutations in normal human and animal tissues are indicated, with the emphasis on their possible functional consequences. In the context of aging, the correlation between somatic TE activation and age-related changes in the number of proteins required for heterochromatin maintenance and longevity regulation was analyzed. One of the original features of this review is a discussion of not only effects based on the TEs insertions and the associated consequences for the germline cell dynamics and somatic genome, but also the differences between transposon- and retrotransposon-mediated structural genome changes and possible phenotypic characteristics associated with aging and various age-related pathologies. Based on the analysis of published data, a hypothesis about the influence of the species-specific features of number, composition, and distribution of TEs on aging dynamics of different animal genomes was formulated.

Asunto(s)

RESUMEN

BACKGROUND: SORTING BY TRANSPOSITIONS (SBT) is a classical problem in genome rearrangements. In 2012, SBT was proven to be [Formula: see text]-hard and the best approximation algorithm with a 1.375 ratio was proposed in 2006 by Elias and Hartman (EH algorithm). Their algorithm employs simplification, a technique used to transform an input permutation [Formula: see text] into a simple permutation [Formula: see text], presumably easier to handle with. The permutation [Formula: see text] is obtained by inserting new symbols into [Formula: see text] in a way that the lower bound of the transposition distance of [Formula: see text] is kept on [Formula: see text]. The simplification is guaranteed to keep the lower bound, not the transposition distance. A sequence of operations sorting [Formula: see text] can be mimicked to sort [Formula: see text]. RESULTS AND CONCLUSIONS: First, using an algebraic approach, we propose a new upper bound for the transposition distance, which holds for all [Formula: see text]. Next, motivated by a problem identified in the EH algorithm, which causes it, in scenarios involving how the input permutation is simplified, to require one extra transposition above the 1.375-approximation ratio, we propose a new approximation algorithm to solve SBT ensuring the 1.375-approximation ratio for all [Formula: see text]. We implemented our algorithm and EH's. Regarding the implementation of the EH algorithm, two other issues were identified and needed to be fixed. We tested both algorithms against all permutations of size n, [Formula: see text]. The results show that the EH algorithm exceeds the approximation ratio of 1.375 for permutations with a size greater than 7. The percentage of computed distances that are equal to transposition distance, computed by the implemented algorithms are also compared with others available in the literature. Finally, we investigate the performance of both implementations on longer permutations of maximum length 500. From the experiments, we conclude that maximum and the average distances computed by our algorithm are a little better than the ones computed by the EH algorithm and the running times of both algorithms are similar, despite the time complexity of our algorithm being higher.

RESUMEN

In the comparative genomics field, one way to infer the evolutionary distance between two organisms of related species is by finding the minimum number of large-scale mutations, called genome rearrangements, that transform one genome into the other. This number is referred to as the rearrangement distance. Since problems in this area emerged in the mid-1990s, several genome rearrangements have been proposed. Rearrangements that do not alter the genome content are called conservative, and in this group we have the following: the reversal, which inverts a segment of the genome; the transposition, which exchanges two consecutive segments; and the double cut and join, which cuts two different pairs of adjacent blocks and joins them differently. Seminal works compared genomes sharing the same set of conserved blocks, but nowadays, researchers started looking at genomes with unequal gene content, by allowing the use of nonconservative rearrangements such as insertion and deletion (jointly called indel). The transposition distance and the transposition and indel distance are both NP-hard. We investigate the transposition and indel distance and present a structure called labeled cycle graph, representing an instance of rearrangement distance problems for genomes with unequal gene content. This structure is used to devise a lower bound and a 2-approximation algorithm for the transposition and indel distance.

Asunto(s)

RESUMEN

Problems in the genome rearrangement field are often formulated in terms of pairwise genome comparison: given two genomes [Formula: see text] and [Formula: see text], find the minimum number of genome rearrangements that may have occurred during the evolutionary process. This broad definition lacks at least two important considerations: the first being which features are extracted from genomes to create a useful mathematical model, and the second being which types of genome rearrangement events should be represented. Regarding the first consideration, seminal works in the genome rearrangement field solely used gene order to represent genomes as permutations of integer numbers, neglecting many important aspects like gene duplication, intergenic regions, and complex interactions between genes. Regarding the second consideration, some rearrangement events are widely studied such as reversals and transpositions. In this paper, we shed light on the first consideration and created a model that takes into account gene order and the number of nucleotides in intergenic regions. In addition, we consider events of reversals, transpositions, and indels (insertions and deletions) of genomic material. We present a 4-approximation algorithm for reversals and indels, a [Formula: see text]-approximation algorithm for transpositions and indels, and a 6-approximation for reversals, transpositions, and indels.

Asunto(s)

RESUMEN

The rearrangement distance is a well-known problem in the field of comparative genomics. Given two genomes, the rearrangement distance is the minimum number of rearrangements in a set of allowed rearrangements (rearrangement model), which transforms one genome into the other. In rearrangement distance problems, a genome is modeled as a string, where each element represents a conserved region within the two genomes. When the orientation of the genes is known, it is represented by (plus or minus) signs assigned to the elements of the string. Two of the most studied rearrangements are reversals, which invert a segment of the genome, and transpositions, which exchange the relative positions of two adjacent segments of the genome. The first works in genome rearrangements considered that the genomes being compared had the same genetic material and that rearrangement events were restricted to reversals, transpositions, or both. El-Mabrouk extended the reversal model on signed strings to include the operations of insertion and deletion of segments in the genome, which allowed the comparison of genomes with different genetic material. Other studies also addressed this problem and, recently, this problem was proved to be solvable in polynomial time by Willing et al. For unsigned strings, we still observe a lack of results. That said, in this study we prove that computing the rearrangement distance for the following models is NP-Hard: reversals and indels on unsigned strings; transpositions and indels on unsigned strings; and reversals, transpositions, and indels on signed and unsigned strings. Along with the NP-hardness proofs, we present a 2-approximation algorithm for reversals on unsigned strings and 3-approximation algorithms for the other models.

Asunto(s)

RESUMEN

The female-specific W chromosomes of most Neognathae birds are highly degenerated and gene-poor. Previous studies have demonstrated that the gene repertoires of the Neognathae bird W chromosomes, despite being in small numbers, are conserved across bird species, likely due to purifying selection maintaining the regulatory and dosage-sensitive genes. Here we report the discovery of DNA-based sequence duplications from the Z to the W chromosome in birds-of-paradise (Paradisaeidae, Passeriformes), through sequence transposition. The original transposition involved nine genes, but only two of them (ANXA1 and ALDH1A1) survived on the W chromosomes. Both ANXA1 and ALDH1A1 are predicted to be dosage-sensitive, and the expression of ANXA1 is restricted to ovaries in all the investigated birds. These analyses suggest the newly transposed gene onto the W chromosomes can be favored for their role in restoring dosage imbalance or through female-specific selection. After examining seven additional songbird genomes, we further identified five other transposed genes on the W chromosomes of Darwin's finches and one in the great tit, expanding the observation of the Z-to-W transpositions to a larger range of bird species, but not all transposed genes exhibit dosage-sensitivity or ovary-biased expression We demonstrate a new mechanism by which the highly degenerated W chromosomes of songbirds can acquire genes from the homologous Z chromosomes, but further functional investigations are needed to validate the evolutionary forces underlying the transpositions.

Asunto(s)

RESUMEN

Here we attempt to reconstruct the sequence of events that led to the formation of three regulatory piRNA clusters, namely, 20A, 38C and flamenco in the Drosophila melanogaster genome. Both the 38C and flamenco clusters include inverted sequences, which potentially form double-stranded RNA hairpins. We present evidence in favor of the well-known hypothesis of piRNA clusters as "transposon traps". According to this model, the presence of the only copy of the transposon in the genome indicates that its expression is suppressed by an RNA-interference mechanism immediately after the mobile element enters the piRNA cluster. We also discuss high the structural variability of piRNAs in Drosophila clusters and cases of horizontal transmobile elements between related species.

Asunto(s)

RESUMEN

One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species' genome. When we represent genomes as permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so, the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the cost of that sequence is minimum. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about the lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for five versions of this problem involving reversals and transpositions. We also give bounds for the diameters concerning these problems and provide an improved approximation factor for simple permutations considering transpositions.

Asunto(s)

RESUMEN

In comparative genomics, rearrangements are mutations that affect a stretch of DNA sequences. Reversals and transpositions are well-known rearrangements, and each has a vast literature. The reversal and transposition distance, that is, the minimum number of reversals and transpositions needed to transform one genome into another is a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations was proposed >20 years ago and received the name of sorting by reversals and transpositions problem. It has been the focus of a number of studies, but the computational complexity has remained open until now. We hereby solve this question and prove that it is NP-hard no matter whether genomes are represented by signed or unsigned permutations. In addition, we prove that a usual generalization of this problem, which assigns weights wρ for reversals and wτ for transpositions, is also NP-hard as long as wτ/wρ ≤ 1.5 for both signed and unsigned permutations.

Asunto(s)

RESUMEN

Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event, and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem on signed permutations. In this study, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present two algorithms with approximation factors of 5/3 and 3/2. We also developed a generic approximation algorithm to deal with different weights for reversals and transpositions, and we show the approximation factor reached in each scenario.

Asunto(s)

RESUMEN

Prior research points to efficient identification of embedded words as a key factor in facilitating the reading of text printed without spacing between words. Here we further tested the primary role of bottom-up word identification by altering this process with a letter transposition manipulation. In two experiments, we examined silent reading and reading aloud of normal sentences and sentences containing words with letter transpositions, in both normally spaced and unspaced conditions. We predicted that letter transpositions should be particularly harmful for reading unspaced text. In line with our prediction, the majority of our measures of reading fluency showed that unspaced text with letter transpositions was disproportionately difficult to read. These findings provide further support for the claim that reading text without between-word spacing relies principally on efficient bottom-up processing, enabling accurate word identification in the absence of visual cues to identify word boundaries.

Asunto(s)

RESUMEN

Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ([Formula: see text])-approximation algorithms for these problems, where [Formula: see text] is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.

Asunto(s)

RESUMEN

Genome rearrangements are large-scale evolutionary events that shuffle genomic architectures. The minimal number of such events between two genomes is often used in phylogenomic studies to measure the evolutionary distance between the genomes. Double-Cut-and-Join (DCJ) operations represent a convenient model of most common genome rearrangements (reversals, translocations, fissions, and fusions), while other genome rearrangements, such as transpositions, can be modeled by pairs of DCJs. Since the DCJ model does not directly account for transpositions, their impact on DCJ scenarios is unclear. In the present work, we study implicit appearance of transpositions (as pairs of DCJs) in DCJ scenarios. We consider shortest DCJ scenarios satisfying the maximum parsimony assumption, as well as more general DCJ scenarios based on some realistic but less restrictive assumptions. In both cases, we derive a uniform lower bound for the rate of implicit transpositions, which depends only on the genomes but not a particular DCJ scenario between them. Our results imply that implicit appearance of transpositions in DCJ scenarios may be unavoidable or even abundant for some pairs of genomes. We estimate that for mammalian genomes implicit transpositions constitute at least 6% of genome rearrangements.

RESUMEN

2-deoxyribose trinucleotides are essential units for storage and transfer of the genetic information. Nucleotide transpositions in trinucleotide sequences affect production of different amino acids. The study focuses on the mechanism of unpairing initially H-bonded trinucleotides. In living cells, the unpairing proceeds through DNA polymerase operating only in the presence of Mg cations. The DNA polymerase is a very complex system to be studied quantum chemically. In our simplistic approach, the polymerase is replaced by two Mg cations attached to both sides of the complementary trinucleotides. A distinguished feature of Mg in cell is in its easiness to accept and donate the electron density. In a particular molecular configuration, this makes Mg singly charged. As to the current case, we observe an unpaired electron on the Mg(+) and an unpaired electron on the trinucleotide - totally, a radical pair which coupling produces either triplet or singlet state. The study, based on the DFT B3LYP (6-311G** basis set) computations, shows that the singlet state energetically is less preferable than the triplet state. The latter is unstable and makes the trinucleotide strands unpair in the region where the singlet and triplet states cross.

Asunto(s)

RESUMEN

Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation [Formula: see text] algorithm, whose running time was improved to O(nlogn) by Feng and Zhu (2007) with a data structure they defined, the permutation tree. Elias and Hartman (2006) developed a 1.375-approximation O(n(2)) algorithm, and Firoz et al. (2011) claimed an improvement to the running time, from O(n(2)) to O(nlogn), by using the permutation tree. We provide counter-examples to the correctness of Firoz et al.'s strategy, showing that it is not possible to reach a component by sufficient extensions using the method proposed by them. In addition, we propose a 1.375-approximation algorithm, modifying Elias and Hartman's approach with the use of permutation trees and achieving O(nlogn) time.

Asunto(s)

RESUMEN

BACKGROUND: During evolution, global mutations may alter the order and the orientation of the genes in a genome. Such mutations are referred to as rearrangement events, or simply operations. In unichromosomal genomes, the most common operations are reversals, which are responsible for reversing the order and orientation of a sequence of genes, and transpositions, which are responsible for switching the location of two contiguous portions of a genome. The problem of computing the minimum sequence of operations that transforms one genome into another - which is equivalent to the problem of sorting a permutation into the identity permutation - is a well-studied problem that finds application in comparative genomics. There are a number of works concerning this problem in the literature, but they generally do not take into account the length of the operations (i.e. the number of genes affected by the operations). Since it has been observed that short operations are prevalent in the evolution of some species, algorithms that efficiently solve this problem in the special case of short operations are of interest. RESULTS: In this paper, we investigate the problem of sorting a signed permutation by short operations. More precisely, we study four flavors of this problem: (i) the problem of sorting a signed permutation by reversals of length at most 2; (ii) the problem of sorting a signed permutation by reversals of length at most 3; (iii) the problem of sorting a signed permutation by reversals and transpositions of length at most 2; and (iv) the problem of sorting a signed permutation by reversals and transpositions of length at most 3. We present polynomial-time solutions for problems (i) and (iii), a 5-approximation for problem (ii), and a 3-approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5-approximation algorithm is not greater than 3 for random signed permutations with more than 12 elements. Finally, we present experimental results that show that the approximation ratios of the approximation algorithms cannot be smaller than 3. In particular, this means that the approximation ratio of the 3-approximation algorithm is tight.