Search

In the Shortest Common Superstring problem (SCS), one needs to find the shortest superstring for a set of strings. While SCS is NP-hard and MAX-SNP-hard, the Greedy Algorithm “choose two strings with the largest overlap; merge them; repeat” achieves a constant factor approximation that is known to be at most 3.5 and conjectured to be equal to 2. The Greedy Algorithm is not deterministic, so its instantiations with different tie-breaking rules may have different approximation factors. In this paper, we show that it is not the case: all factors are equal. To prove this, we show how to transform a set of strings so that all overlaps are different whereas their ratios stay roughly the same.

DNA sequence assembly is a rich combinatorial problem that arose with the first DNA sequencing projects in the early 80's. Here we give a short history of the progression of algorithmic ideas used to solve the de novo problem of inferring a genome given a large sampling of substrings covering it. This classic inverse problem is compounded by a variety of experimental features and artifacts that must be considered in any realistic solution. While current methods produce very good results, the perfect assembler has yet to be built.

Given a set of strings, the shortest common superstring problem is to find the shortest possible string that contains all the input strings. The problem is NP-hard, but a lot of work has gone into designing approximation algorithms for solving the problem. We present the first time and space efficient implementation of the classic greedy heuristic which merges strings in decreasing order of overlap length. Our implementation works in $O(n \log \sigma)$ time and bits of space, where $n$ is the total length of the input strings in characters, and $\sigma$ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly $5 n \log \sigma$ bits of space and reasonable time for a real dataset that consists of DNA fragments., Comment: 13 Pages, 3 figures, accepted to the 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017)

It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O ⁎ ( 2 n ) time ( O ⁎ ( ⋅ ) suppresses polynomial factors of the input length). In this short note, we show that for any constant r, SCS for strings of length at most r can be solved in time O ⁎ ( 2 ( 1 − c ( r ) ) n ) where c ( r ) = ( 1 + 2 r 2 ) − 1 . For this, we introduce so-called hierarchical graphs that allow us to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k = ( 1 − c ( r ) ) n weakly connected components. One can then use a recent O ⁎ ( 2 k ) time algorithm by Gutin, Wahlstrom, and Yeo.

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al., who designed a greedy-like algorithm with length approximation ratio $4$. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio $\frac12$, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm., Published in Information Processing Letters

The shortest common superstring problem (SCS) has been extensively studied for its applications in string compression and DNA sequence assembly. Although the problem is known to be Max-SNP hard, the simple greedy algorithm performs extremely well in practice. To explain the good performance, previous researchers proved that the greedy algorithm is asymptotically optimal on random instances. Unfortunately, the practical instances in DNA sequence assembly are very different from the random instances. In this paper we explain the good performance of the greedy algorithm by using the smoothed analysis. We show that, for any given instance I of SCS, the average approximation ratio of the greedy algorithm on a small random perturbation of I is 1+o(1). The perturbation defined in the paper is small and naturally represents the mutations of the DNA sequence during evolution. Due to the existence of the uncertain nucleotides in the output of a DNA sequencing machine, we also proposed the shortest common superstring with wildcards problem (SCSW). We prove that in the worst case SCSW cannot be approximated within the ratio n^1^/^7^-^@e, while the greedy algorithm still has 1+o(1) smoothed approximation ratio.

In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set $$S$$S of strings and a multiset $$\mathcal {M}$$M of symbols, and we look for an ordering $$\mathcal {M}_o$$Mo of $$\mathcal {M}$$M such that the number of input strings which are substrings of $$\mathcal {M}_o$$Mo is maximized. In SRCS we are given a set $$S$$S of strings and a text $$\mathcal {T}$$T, and we look for a swap ordering $$\mathcal {T}_o$$To of $$\mathcal {T}$$T (an ordering of $$\mathcal {T}$$T obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of $$\mathcal {T}_o$$To is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter $$\ell $$l). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless $$NP \subseteq coNP/Poly$$NP⊆coNP/Poly. Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to $$10$$10) or are over a binary alphabet.

In this short note, we prove that the greedy conjecture for the shortest common superstring problem is true for strings of length 4.

We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring and an optimal cycle cover, provided the greedy algorithm happens to merge the strings in a particular way. Thus, when restricting inputs correspondingly, we verify the well-known greedy conjecture, namely, that the approximation ratio of the greedy algorithm is within a factor of two of the optimum, and actually extend the conjecture considerably. We achieve this bound by systematically combining known conditional inequalities about overlaps and period- and string-lengths with a new familiy of string inequalities. We show that conventional systems of conditional inequalities, including the Monge inequalities, are insufficient to obtain our result.

In general, a reoptimization gives us a possibility to obtain a solution for a larger instance from a solution for a smaller instance. In this paper, we consider a possibility of usage of a reoptimization to solve the shortest common superstring problem.

This paper proposes a DNA algorithm for solving an NP-complete problem (The Shortest Common Superstring Problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay.

In the first part of this paper we show that the Shortest Common Superstring problem is NP-complete even if all strings are of the simple form 10p10q, p, q gE oN. This result closes the gap left between the polynomial cases where all strings are of the form 0p10q or all strings are of the form 10p1 and NP-complete cases when strings have a more complicated structure. In the second part of the paper we use the above result to investigate the complexity of 2-machine flow-shop and open-shop problems with machines that have to coordinate their starting times, i.e. when one machine starts an operation the other machine also starts an operation or has to be idle at that time.

The shortest common superstring problem has important applications in computational biology (e.g. genome assembly) and data compression. This problem is NP-hard, but several heuristic algorithms proved to be efficient for this problem. For example, for the algorithm known as GREEDY it was shown that, if the optimal superstring has the length of N, it produces an answer with length not exceeding 3.5N. However, in practice, no test cases were found where the length of the answer is greater than or equal to 2N. For hard test case generation for such algorithms the traditional approach assumes creating such tests by hand. In this paper, we propose an evolutionary algorithm based framework for hard test case generation. We examine two approaches: single-objective and multi-objective. We introduce new test case quality measures and show that, according to these measures, automatically generated tests are better than any known ones.

The best known approximation ratio for the shortest superstring problem is \(2\frac{11}{23}\) (Mucha, 2012). In this note, we improve this bound for the case when the length of all input strings is equal to r, for r ≤ 7. E.g., for strings of length 3 we get a \(1\frac{1}{3}\)-approximation. An advantage of the algorithm is that it is extremely simple both to implement and to analyze. Another advantage is that it is based on de Bruijn graphs. Such graphs are widely used in genome assembly (one of the most important practical applications of the shortest common superstring problem). At the same time these graphs have only a few applications in theoretical investigations of the shortest superstring problem.

In laboratories the majority of large-scale DNA sequencing is done following theshotgun strategy, which is to sequence large amount of relatively short fragments randomly and then heuristically find a shortest common superstring of the fragments [26]. We study mathematical frameworks, under plausible assumptions, suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms. We model the DNA sequencing problem as learning a string from its randomly drawn substrings. Under certain restrictions, this may be viewed as string learning in Valiant's distribution-free learning model and in this case we give an efficient learning algorithm and a quantitative bound on how many examples suffice. One major obstacle to our approach turns out to be a quite well-known open question on how to approximate a shortest common superstring of a set of strings, raised by a number of authors in the last 10 years [9], [29], [30]. We give the firstprovably good algorithm which approximates a shortest superstring of lengthn by a superstring of lengthO(n logn). The algorithm works equally well even in the presence of negative examples, i.e., when merging of some strings is prohibited.

In several areas, in particular in bioinformatics and in AI planning, Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied. In this paper we consider two variants of SCS recently introduced (Restricted Common Superstring, $\ensuremath{\text{\textsc{RCS}}}$) and (Swapped Common Superstring, $\ensuremath{\text{\textsc{SWCS}}}$). In $\ensuremath{\text{\textsc{RCS}}}$ we are given a set S of strings and a multiset, and we look for an ordering $\mathcal{M}_o$ of $\mathcal{M}$ such that the number of input strings which are substrings of $\mathcal{M}_o$ is maximized. In $\ensuremath{\text{\textsc{SWCS}}}$ we are given a set S of strings and a text $\mathcal{T}$, and we look for a swap ordering $\mathcal{T}_o$ of $\mathcal{T}$ (an ordering of $\mathcal{T}$ obtained by swapping only some pairs of adjacent characters) such that the number of input strings which are substrings of $\mathcal{T}_o$ is maximized. In this paper we investigate the parameterized complexity of the two problems. We give two fixed-parameter algorithms, where the parameter is the size of the solution, for $\ensuremath{\text{\textsc{SWCS}}}$ and $\ensuremath{\text{\textsc{$\ell$-RCS}}} $ (the $\ensuremath{\text{\textsc{RCS}}}$ problem restricted to strings of length bounded by a parameter l). Furthermore, we complement these results by showing that $\ensuremath{\text{\textsc{SWCS}}}$ and $\ensuremath{\text{\textsc{$\ell$-RCS}}} $ do not admit a polynomial kernel.

A reoptimization problem describes the following scenario: given an instance of an optimization problem together with an optimal solution for it, we want to find a good solution for a locally modified instance. In this paper, we deal with reoptimization variants of the shortest common superstring problem (SCS) where the local modifications consist of adding or removing a single string. We show the NP-hardness of these reoptimization problems and design several approximation algorithms for them. First, we use a technique of iteratively using any SCS algorithm to design an approximation algorithm for the reoptimization variant of adding a string whose approximation ratio is arbitrarily close to 8/5 and another algorithm for deleting a string with a ratio tending to 13/7. Both algorithms significantly improve over the best currently known SCS approximation ratio of 2.5. Additionally, this iteration technique can be used to design an improved SCS approximation algorithm (without reoptimization) if the input instance contains a long string, which might be of independent interest. However, these iterative algorithms are relatively slow. Thus, we present another, faster approximation algorithm for inserting a string which is based on cutting the given optimal solution and achieves an approximation ratio of 11/6. Moreover, we give some lower bounds on the approximation ratio which can be achieved by algorithms that use such cutting strategies., Algorithmica, 61 (2), ISSN:0178-4617, ISSN:1432-0541

The Shortest Common Superstring (SCS) is a well studied problem, having a wide range of applications. In this paper we consider two problems closely related to it. First we define the Swapped Restricted Superstring(SRS) problem, where we are given a set S of n strings, s1, s2, . . . , sn, and a text T = t1t2 . . . tm, and our goal is to find a swap permutation π : {1, . . . ,m} → {1, . . . , m} to maximize the number of strings in S that are substrings of tπ(1)tπ(2) . . . tπ(m). We then show that the SRS problem is NP-Complete. Afterwards, we consider a similar variant denoted SRSR, where our goal is to find a swap permutation π : {1, . . . , m} → {1, . . . , m} to maximize the total number of times that the strings of S appear in tπ(1)tπ(2) . . . tπ(m) (we can count the same string si as a substring of tπ(1)tπ(2) . . . tπ(m) more than once). For this problem, we present a polynomial time exact algorithm.

Approximation algorithms for the shortest common superstring problem have been studied recently. This paper considers an interesting variation of the problem: For a given set of strings S ={ s 1 ,…, s m }, find a shortest superstring that contains either s i or s R i for each i . The problem may have applications in DNA sequencing practice when orientations of the fragments in the target DNA molecule are unknown. We give a simple greedy algorithm and prove a 4 n approximation bound for it.

A reoptimization problem describes the following scenario: Given an instance of an optimization problem together with an optimal solution for it, we want to find a good solution for a locally modified instance. In this paper, we deal with reoptimization variants of the shortest common superstring problem where the local modifications consist of adding or removing a single string. We show NP-hardness of these reoptimization problems and design several approximation algorithms for them.

We consider approximation algorithms for the shortest common superstring problem (SCS). It is well known that there is a constant f>1f>1 such that there is no efficient approximation algorithm for SCS achieving a factor of at most f in the worst case, unless P=NPP=NP. We study SCS on random inputs and present an approximation scheme that achieves, for every e>0e>0, a (1+e)(1+e)-approximation in expected polynomial time. We also show that the greedy algorithm achieves approximation ratio 1+e1+e with probability exponentially close to 1. These results apply not only if the letters are chosen independently at random, but also to the more realistic mixing model, which allows dependencies among the letters of the random strings. Our results are based on a sharp tail bound on the optimal compression, which improves a previous result by Frieze and Szpankowski (1998).

The shortest common superstring problem (SCS) has been widely studied for its applications in string compression and DNA sequence assembly. Although it is known to be Max-SNP hard, the simple greedy algorithm works extremely well in practice. Previous researchers have proved that the greedy algorithm is asymptotically optimal on random instances. Unfortunately, the practical instances in DNA sequence assembly are very different from random instances. In this paper we explain the good performance of greedy algorithm by using the smoothed analysis. We show that, for anygiven instance Iof SCS, the average approximation ratio of the greedy algorithm on a small random perturbation of Iis 1 + o(1). The perturbation defined in the paper is small and naturally represents the mutations of the DNA sequence during evolution. Due to the existence of the uncertain nucleotides in the output of a DNA sequencing machine, we also proposed the shortest common superstring with wildcards problem (SCSW). We prove that in worst case SCSW cannot be approximated within ratio n1/7 i¾? i¾?, while the greedy algorithm still has 1 + o(1) smoothed approximation ratio.

Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem, that is, we look for the shortest genome which still contains all genes. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is quite high and also very close to the one achieved by modern computers.

This paper presents a genetic algorithm for the shortest common superstring problem. The problem appears in the computational part of a deoxyribonucleic acid (DNA) sequencing procedure as well as in data compression. The proposed genetic algorithm is based on a recently proposed algorithm for the sequencing by hybridization (SBH) problem. The algorithm exploits the crossover operator and modifies the objective function to make the algorithm both more effective and more efficient. Experimental results on real data show the effectiveness of the proposed algorithm.

We investigate the greedy algorithm for the shortest common superstring problem. For a restricted class of orders in which strings are merged, we show that the length of the greedy superstring is upper-bounded by the sum of the length of an optimal superstring and an optimal cycle cover. Thus in this restricted setting we verify the well known conjecture, that the performance ratio of the greedy algorithm is within a factor of two of the optimum and actually extend the conjecture considerably.

This paper proposes a DNA algorithm for solving an NP-complete problem (the shortest common superstring problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay.

The shortest common superstring problem (SCS) is known to be NP-hard and APX-hard. The APX-hardness was proved for the SCS in [BJLTY94], but the reduction used in that paper produces instances with arbitrarily large alphabets. We show that the problem is APX-hard even if the size of the alphabet is 2. A lot of results concerning approximation algorithms have been published. We use our result to establish the first explicit inapproximability results for the SCS.

One method of sequencing DNA produces a linear list of bases, {A, C, G, T}, for many short overlapping fragments of the original DNA. To find the sequence of the original piece of DNA, the many fragments must be reassembled. While this problem of reassembly is similar to the NP-complete shortest common superstring problem [GMS80], we believe that biologists are actually trying to solve a simpler problem. Biologists assume that short overlaps between substrings are insignificant. Further, they assume that there is a unique string from which substrings could have been produced. We consider a reconstruction problem with these restrictions. We devise algorithms for this problem both when the overlaps must be exact and when there may be errors in the overlaps. Our algorithms are based on Rabin-Karp string matching, and on suffix arrays. We investigate the running times of our algorithms, and show that in expected case they have running times proportional to the length of the reconstructed sequence. We give the timings of some test runs and note that the suffix array algorithms seem to be faster.

A superstring of a set of strings {s1,…, sn} is a string s containing each si, 1 ⩽ i ⩽ n, as a substring. The superstring problem is: Given a set S of strings and a positive integer K, does S have a superstring of length K? The superstring problem has applications to data storage; specifically, data compression. We consider the complexity of the superstring problem. NP-completeness results dealing with sets of strings over both finite and infinite alphabets are presented. Also, for a restricted version of the superstring problem, a linear time algorithm is given.

An approximation algorithm for the shortest common superstring problem is developed, based on the Knuth-Morris-Pratt string-matching procedure and on the greedy heuristics for finding longest Hamiltonian paths in weighted graphs. Given a set R of strings, the algorithm constructs a common superstring for R in O(mn) steps where m is the number of strings in R and n is the total length of these strings. The performance of the algorithm is analysed in terms of the compression in the common superstrings constructed, that is, in terms of n−k where k is the length of the obtained superstring. We show that (n−k)⩾12(n−kmin) where kmin is the length of a shortest common superstring. Hence the compression achieved by the algorithm is at least half of the maximum compression. It also seems that the lengths always satisfy k⩽2·kmin but proving this remains open.

In this paper, we consider multiple occurrences shortest common superstring problem. In particular, we consider an approach to solve the problem. This approach is based on an explicit reduction from the problem to the satisfiability problem.

We consider the problem of the shortest common superstring. We describe an approach to solve the problem. This approach is based on an explicit reduction from the problem to the satisfiability problem. © 2013 Anna Gorbenko and Vladimir Popov.