Superstring graph: a new approach for genome assembly

DOI10.1007/978-3-319-41168-2_4MaRDI QIDQ2830057zbMATH OpenOpenAlexFDO

Authors Bastien Cazaux, Gustavo Sacomoto, Eric Rivals

Publication date 9 November 2016

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-01446428/file/Cazaux-etal-assembly-superstring-AAIM-2016.pdf

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10)

Recommendations

• scientific article; zbMATH DE number 6403120
• Hierarchical overlap graph
• Two approaches to the common superstring problem
• Approximating shortest superstring problem using de Bruijn graphs
• From indexing data structures to de Bruijn graphs

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• A linear time algorithm for shortest cyclic cover of strings
• An efficient algorithm for the all pairs suffix-prefix problem
• From indexing data structures to de Bruijn graphs
• Greedy in Approximation Algorithms
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• On finding minimal length superstrings
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings

Cited in

(9)

• Graph algorithms for DNA sequencing -- origins, current models and the future
• MULKSG: \textit{MUL}tiple \textit{K} \textit{S}imultaneous \textit{G}raph assembly
• Safe and complete contig assembly via omnitigs
• Next generation sequencing under de novo genome assembly
• Synteny paths for assembly graphs comparison
• scientific article; zbMATH DE number 6403120 (Why is no real title available?)
• Economic genome assembly from low coverage illumina and nanopore data
• Extended strings and graphs for simple gene assembly
• Linear-time superbubble identification algorithm for genome assembly

Describes a project that uses

Uses Software

• IDBA
• SPAdes

This page was built for publication: Superstring graph: a new approach for genome assembly

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