Search

Scaffold filling is a critical step in DNA assembly. Its basic task is to fill the missing genes (fragments) into an incomplete genome (scaffold) to make it similar to the reference genome. There have been a lot of work under distinct measurements in the literature of genome comparison. For genomes with gene duplications, common string partition reveals the similarity more precisely, since it constructs a one-to-one correspondence between the same segments in the two genomes. In this paper, we adopt duo-preservation as the measurement, which is the complement of common string partition, i.e., the number of duo-preservations added to the number of common strings is exactly the length of a genome. Towards a proper scaffold filling, we just focus on the increased duo-preservations. This problem is called scaffold filling to maximize increased duo-preservations (abbr. SF-MIDP). We show that SF-MIDP is solvable in linear time for a simple version where all the genes of the scaffold are matched in a block-matching, but MAX SNP-complete for the general version, and cannot be approximated within $\frac{16263}{16262}$ 16263 16262 . Moreover, we present a basic approximation algorithm of factor 2, by which the optimal solution can be described in a new way, and then, improve the approximation factor to $\frac{12}{7}$ 12 7 via a greedy method. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]

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: A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed. [Copyright &y& Elsevier]

Abstract: Given a graph with nonnegative costs defined on edges, a positive integer , and a collection of terminal sets , where each is a subset of , the Generalized -Multicut problem asks to find a set of edges at the minimum cost such that its removal from cuts at least terminal sets in . A terminal subset is cut by if all terminals in are disconnected from one another by removing from . This problem is a generalization of the -Multicut problem and the Multiway Cut problem. The famous Densest -Subgraph problem can be reduced to the Generalized -Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an -approximation algorithm for the Generalized -Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP-hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give -approximation for the Generalized -Multicut problem in undirected graphs and -approximation for the -Forest problem. [Copyright &y& Elsevier]

Sorting permutations by block moves is a fundamental combinatorial problem in genome rearrangements. The classic block move operation is called transposition, which switches two adjacent blocks, or equivalently, moves a block to some other position. But large blocks movement rarely occurs during real evolutionary events. A natural restriction of transposition is to bound the length of the blocks to be switched. In this paper, we investigate the problem called sorting by bounded singleton moves, where one of the switched blocks is exactly a singleton while the other is of length at most c. This problem generalizes the sorting by short block moves problem proposed by Heath and Vergara [11] , which requires the total length of blocks switched bounded by 3. When c = 3 , we devise a 9 5 -approximation algorithm for an arbitrary permutation, and a 12 7 -approximation algorithm for a woven double-strip permutation. Our algorithms can be slightly extended to solve the sorting by c -bounded singleton moves problem for any constant c ≥ 3 , guaranteeing an approximation factor of 3 c 5 and 4 c 7 for arbitrary permutations and woven double-strip permutations respectively, just by exploiting a new lower bound of sorting by c -bounded singleton moves. • Sorting a lone dome, mushroom or rainbow needs a 1-move and a 2-move. • Sorting a lone double-mushroom, right-mushroom, left-mushroom or bridge needs a 1-move and two 2-moves. • If no correcting 2-move can be performed, then there exist lone arcs or mushrooms. • A permutation is a woven double-strip permutation if and only if its longest decreasing subsequence has length at most 2. [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]

This paper investigates two combinatorial problems from RNA secondary structure prediction with arbitrary pseudoknots. Given a RNA sequence and a set of base pairs, two parallel and adjacent base pairs constitute a stacking. The Maximum Stacking Base Pairs problem (MSBP) aims at finding a maximum number of based pairs, all of which form stackings, while the Maximum Base Pair Stackings problem (MBPS) is to find a maximum number of stackings. Both problems are NP-hard. We present two new approximation algorithms for the two problems by local search methods. For MSBP, the approximation factor is improved from 5 2 to 7 3 ; as for the MBPS, the approximation factor is improved from 8 3 to 5 2. [ABSTRACT FROM AUTHOR]