Search

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

Abstract: Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. A translocation is reciprocal if none of the exchanged ends is empty; otherwise, non-reciprocal. The problem of sorting by translocations asks to find a shortest sequence of translocations transforming one genome into another. The problem of sorting by reciprocal translocations can be solved in polynomial-time. Several algorithms have been developed for reciprocal translocation sorting. They can only be applied to a pair of genomes having the same set of chromosome ends. Such a restriction can be removed if non-reciprocal translocations are also allowed. In this paper, we show how to extend the algorithm for sorting by reciprocal translocations to include non-reciprocal translocations, allowing us to compare genomes containing different chromosome ends. We call this problem sorting by generalized translocations. We present a polynomial algorithm for this problem. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by Hannenhalli which is used to sort genomes by reversals and translocations. [Copyright &y& Elsevier]

Abstract: Genome rearrangement is an important area in computational biology. There are three basic operations, reversal, translocation and transposition. Here we study the translocation operations. Multi-chromosomal genomes frequently evolve by translocation events that exchange genetic material between two chromosomes. We focus on the signed case, where the direction of each gene is known. The signed translocation problem asks to find the minimum number of translocation operations as well as the sequence of translocation operations to transform one genome into the other. A linear-time algorithm that computes the minimum number of translocation operations was given in a linear-time algorithm for computing translocation distance between signed genomes [16]. However, that algorithm cannot give the optimum sequence of translocation operations. The best known algorithm that can give the optimum sequence of translocation operations for signed translocation problem runs in time. In this paper, we design an algorithm. [Copyright &y& Elsevier]

Breakpoint graph has been widely used as a key data structure in algorithm design for genome rearrangements. The problem of breakpoint graph cycle decomposition, which asks for a largest collection of edge-disjoint cycles, is crucial in computing rearrangement distances between genomes. This problem is NP-hard, and can be approximated to 1.4193 + ϵ . It is still open for deciding whether a breakpoint graph can admit a cycle decomposition with none other than 2-cycles. In this paper, we present a linear time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles. [ABSTRACT FROM AUTHOR]

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1.5 + ε . In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1.408 + ε , where ε = O ( 1 / log ⁡ n ) . [ABSTRACT FROM AUTHOR]