A Note on Shortest Common Superstrings with Flipping

Résumé du livre

Abstract: "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 = [s1 ..., s[subscript m]], find a shortest superstring that contains either s[subscript i] or s[subscript i][superscript R] 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 4n approximation bound for it."