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]

The genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I ′ , with respect to a complete reference genome G , such that the number of common/shared adjacencies between G and I ′ is maximized. The problem is NP-complete, and admits a constant-factor approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when a scaffold S is given, the missing genes can only be inserted in between the contigs, and the objective is to maximize the number of common adjacencies between G and the filled genome S ′ . For this problem, we present a simple NP-completeness proof, we then present a factor-2 approximation algorithm. [ABSTRACT FROM AUTHOR]

The scaffold filling problem aims to set up the whole genomes by filling those missing genes into the scaffolds to optimize a similarity measure of genomes. A typical and frequently used measure for the similarity of two genomes is the number of common adjacencies. One-sided scaffold filling is given by a scaffold and a whole genome, and asks to fill the missing genes into that scaffold to result in such a genome that the number of common adjacencies between it and the given genome is maximized. Two-sided scaffold filling is given by two scaffolds, and asks to fill the missing genes into those two scaffolds respectively to result in such two genomes that the number of common adjacencies between them is maximized. One-sided scaffold filling can be approximated to $$\frac{5}{4}$$ by now. However, the algorithmic progress for two-sided scaffold filling seems rare. What we know for two-sided scaffold filling is a 2-approximation algorithm by now. In this paper, we propose a new algorithm for two-sided scaffold filling which can achieve a performance ratio of $$\frac{3}{2}$$ in $$O(N^3)$$ time, where $$N$$ is the number of genes in an output genome. An example can be given to show that the performance ratio $$\frac{3}{2}$$ for this algorithm is actually tight. [ABSTRACT FROM AUTHOR]

The exemplar breakpoint distance problem is motivated by finding conserved sets of genes between two genomes. It asks to find respective exemplars in two genomes to minimize the breakpoint distance between them. If one genome has no repeated gene (called trivial genome) and the other has genes repeating at most twice, it is referred to as the (1, 2)-exemplar breakpoint distance problem, EBD(1, 2) for short. Little has been done on algorithm design for this problem by now. In this article, we propose a parameter to describe the maximum physical span between two copies of a gene in a genome, and based on it, design a fixed-parameter algorithm for EBD(1, 2). Using a dynamic programming approach, our algorithm can take O(4 s n2) time and O(4 s n) space to solve an EBD(1, 2) instance that has two genomes of n genes where the second genome has each two copies of a gene spanning at most s copies of the genes. Our algorithm can also be used to compute the maximum adjacencies between two genomes. The algorithm has been implemented in C++. Simulations on randomly generated data have verified the effectiveness of our algorithm. The software package is available from the authors. [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]

Motivation: The double cut and join operation (abbreviated as DCJ) has been extensively used for genomic rearrangement. Although the DCJ distance between signed genomes with both linear and circular (uni- and multi-) chromosomes is well studied, the only known result for the NP-complete unsigned DCJ distance problem is an approximation algorithm for unsigned linear unichromosomal genomes. In this article, we study the problem of computing the DCJ distance on two unsigned linear multichromosomal genomes (abbreviated as UDCJ).Results: We devise a 1.5-approximation algorithm for UDCJ by exploiting the distance formula for signed genomes. In addition, we show that UDCJ admits a weak kernel of size 2k and hence an FPT algorithm running in O(22kn) time.Contact: bhz@cs.montana.edu [ABSTRACT FROM AUTHOR]

Abstract: Translocation is one of the basic operations for genome rearrangement. Translocation distance is the minimum number of translocations required to transform one genome into the other. In this paper, we show that computing the translocation distance for unsigned genomes is NP-hard. Moreover, we show that approximating the translocation distance for unsigned genomes within ratio 1.00017 is NP-hard. [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]

Abstract: The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a 1.75-approximation algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [J. Kececioglu, R. Ravi, Of mice and men: Algorithms for evolutionary distances between genomes with translocation, in: 6th ACM–SIAM Symposium on Discrete Algorithms, 1995, pp. 604–613]. [Copyright &y& Elsevier]

Genome structural variants (SVs) have great impacts on human phenotype and diversity, and have been linked to numerous diseases. Long-read sequencing technologies arise to make it possible to find SVs of as long as 10,000 nucleotides. Thus, long read-based SV detection has been drawing attention of many recent research projects, and many tools have been developed for long reads to detect SVs recently. In this article, we present a new method, called SVLR, to detect SVs based on long-read sequencing data. Comparing with existing methods, SVLR can detect three new kinds of SVs: block replacements, block interchanges, and translocations. Although these new SVs are structurally more complicated, SVLR achieves accuracies that are comparable with those of the classic SVs. Moreover, for the classic SVs that can be detected by state-of-the-art methods (e.g., SVIM and Sniffles), our experiments demonstrate recall improvements of up to 38% without harming the precisions (i.e., >78%). We also point out three directions to further improve SV detection in the future. Source codes: https://github.com/GWYSDU/SVLR [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]