Approximating shortest superstring problem using de Bruijn graphs

DOI10.1007/978-3-642-38905-4_13MaRDI QIDQ4928566zbMATH OpenOpenAlexFDO

Authors Alexander Golovnev, Ivan Mihajlin, Alexander S. Kulikov

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38905-4_13

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• A 2_3² superstring approximation algorithm
• Linear approximation of shortest superstrings
• Approximating Shortest Superstrings
• Improved length bounds for the shortest superstring problem
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring

Cites work

• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• A greedy approximation algorithm for constructing shortest common superstrings
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• An algorithm for the Rural Postman problem on a directed graph
• An Eulerian path approach to DNA fragment assembly
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for the shortest common superstring problem
• Arc Routing Problems, Part II: The Rural Postman Problem
• scientific article; zbMATH DE number 595499 (Why is no real title available?)
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• Improved length bounds for the shortest superstring problem
• Lyndon words and short superstrings
• Mathematical Foundations of Computer Science 2005
• On finding minimal length superstrings
• P-Complete Approximation Problems
• Parallel and sequential approximation of shortest superstrings
• Rotations of Periodic Strings and Short Superstrings
• Simpler approximation of the maximum asymmetric traveling salesman problem
• The greedy algorithm for shortest superstrings

Cited in

(10)

• Relationship between superstring and compression measures: new insights on the greedy conjecture
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• A linear time algorithm for shortest cyclic cover of strings
• Construction of a de Bruijn graph for assembly from a truncated suffix tree
• Superstring graph: a new approach for genome assembly
• On the shortest common superstring of NGS reads
• Sequential and Parallel Approximation of Shortest Superstrings
• scientific article; zbMATH DE number 5074400 (Why is no real title available?)
• Practical lower and upper bounds for the shortest linear superstring
• Collapsing Superstring Conjecture

This page was built for publication: Approximating shortest superstring problem using de Bruijn graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928566)