Greedy Shortest Common Superstring Approximation in Compact Space

2017/07/24 by Jarno Alanko, Alanko, Jarno, Tuukka Norri +1
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #DNA and Biological Computing #Network Packet Processing and Optimization

paper · pdf · doi:10.48550/arxiv.1707.07727

Abstract

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 σ) time and bits of space, where n is the total length of the input strings in characters, and σ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly 5 n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.

Related

• All instantiations of the greedy algorithm for the shortest superstring problem are equivalent
• Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
• Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings
• On improving the approximation ratio of the r-shortest common superstring problem
• Collapsing Superstring Conjecture