Search

In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1.4 + ε. This is achieved through a deep investigation of the optimal solution structure of Two-Sided Scaffold Filling. We make use of a relevant graph aiming at a solution of a Two-Sided Scaffold Filling instance, and evaluate the optimal solution value by the number of connected components in this graph. We show that an arbitrary optimal solution can be transformed into one whose relevant graph admits connected components that are available to compare with the solution of our algorithm in terms of their values. The performance ratio 1.4 + ε is obtained by comparing the bound of such an optimal solution with the solution of our algorithm. [ABSTRACT FROM AUTHOR]

Although plenty of structural variant detecting approaches for human genomes can be looked up in the literatures, little has been acknowledged on the effectiveness of those structural variant softwares for plant genomes. Moreover, it has been demonstrated frequent occurrences for those structural variant detecting softwares to find too many false structural variants. In this paper, we devote to detect deletions, insertions, and inversions, in total of three kinds of structural variants occurring in Hedou12 genome in contrast to Williams82 genome. To find more potential structural variants, we try to develop new principles to detect discordant and split read map sets supporting structural variants. Aiming to enhance the precision of structural variant detections, we propose two new sequencing characteristic based probability models, which use the sequencing parameters of Hedou12 genome as well as the parameters for Hedou12 paired-end reads to be aligned onto Williams82, to evaluate the probability for a potential structural variant to occur in. To remove the false members from those potential structural variants, we propose a set cover problem model to describe formally on which potential structural variants it should accept to achieve as high as possible a probability summation. This will achieve a solution with more credible structural variants, which can be verified by comparing with DELLY version 0.5.8 and LUMPY version 0.2.2.3. Our algorithm has been verified to be able to find deletions, insertions, and inversions in Hedou12 in contrast to Williams82 DELLY as well as LUMPY fails to find. [ABSTRACT FROM AUTHOR]

The prediction of RNA structure with pseudoknots is a nondeterministic polynomial-time hard (NP-hard) problem; according to minimum free energy models and computational methods, we investigate the RNA-pseudoknotted structure. Our paper presents an efficient algorithm for predicting RNA structure with pseudoknots, and the algorithm takes O(n3) time and O(n2) space, the experimental tests in Rfam10.1 and PseudoBase indicate that the algorithm is more effective and precise. The predicting accuracy, the time complexity and space complexity outperform existing algorithms, such as Maximum Weight Matching (MWM) algorithm, PKNOTS algorithm and Inner Limiting Layer (ILM) algorithm, and the algorithm can predict arbitrary pseudoknots. And there exists a 1+ε (ε>0) polynomial time approximation scheme in searching maximum number of stackings, and we give the proof of the approximation scheme in RNA-pseudoknotted structure. We have improved several types of pseudoknots considered in RNA folding structure, and analyze their possible transitions between types of pseudoknots. [ABSTRACT FROM AUTHOR]

In order to run a dataflow with as low cost as possible, it is often faced with deciding which data-sets in a data-set sequence should be stored, with the rest regenerated. The Intermediate Data-set Storage problem arises from this situation. The current best algorithm for this problem takes O ( n 4 ) time. In this paper, we present two improved algorithms for this problem, the first of which can achieve a time complexity O ( n 2 ) , the second of which O ( r n ) , where n is the number of data-sets in a dataflow, r is a numerical number which indicates how large it is for the maximum storage cost to be divided by the minimum computation cost in the dataflow. [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]

Abstract: In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in -time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of of the optimum in -time, where is the minimum k such that there is a spanning tree of the graph with maximum degree k. [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]

A clause is not-all-equal satisfied if it has at least one literal assigned with true and one literal assigned with false . Max NAE-SAT is given by a boolean variable set U and a clause set C , asks to find an assignment of U , such that the number of not-all-equal satisfied clauses in C is maximized. Max NAE-SAT turns into Max NAE- k -SAT if each clause contains exactly k literals. Local search has long been used in various SAT solvers. However, little has been done on local search to approximate Max NAE- k -SAT. Moreover, it is still open for what a quantitative bound could Max NAE- k -SAT be approximated to, at best. In this paper, we propose a local search algorithm which can approximate Max NAE- k -SAT to 2 k − 1 2 k − 1 − 1 for each fixed k ≥ 2 . Then we show that Max NAE- k -SAT cannot be approximated within 2 k − 1 2 k − 1 − 1 in polynomial time, if P ≠ NP . The algorithm for Max NAE- k -SAT can be extended to approximate Max NAE-SAT where each clause contains at least k literals to 2 k − 1 2 k − 1 − 1 . Using the algorithm for Max NAE-SAT where each clause contains at least k literals, we present a new algorithm to approximate Max-SAT where each clause contains at least k literals to 2 k 2 k − 1 . [ABSTRACT FROM AUTHOR]