On the Shortest Common Superstring of NGS Reads

DOI10.1007/978-3-319-55911-7_8zbMath1485.68318OpenAlexW2599130894MaRDI QIDQ2988815

Raluca Uricaru, Marie Gasparoux, Mathieu Raffinot, Tristan Braquelaire

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_8

zbMATH Keywords

approximation algorithmsnext-generation sequencingshortest superstring problem

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• The greedy algorithm for shortest superstrings
• On the greedy algorithm for the shortest common superstring problem with reversals
• Why greed works for shortest common superstring problem
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Periods in strings
• A \(2_3^2\) superstring approximation algorithm
• Sequential and Parallel Approximation of Shortest Superstrings
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Linear approximation of shortest superstrings
• Approximating Shortest Superstrings
• Rotations of Periodic Strings and Short Superstrings
• Periods and borders of random words
• Approximating Shortest Superstring Problem Using de Bruijn Graphs
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Shortest Common Superstring of NGS Reads