On the Sound Covering Cycle Problem in Paired de Bruijn Graphs

DOI10.1007/978-3-319-19647-3_14MaRDI QIDQ3452560zbMATH OpenOpenAlexFDO

Authors Christian Komusiewicz, Andreea Radulescu

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19647-3_14

zbMATH Keywords

NP-hard sound covering cycle problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Covering the de Bruijn graph
• Colouring of cycles in the de bruijn graphs
• scientific article; zbMATH DE number 6900646
• scientific article; zbMATH DE number 609926
• Covering pairs in directed acyclic graphs
• On the connectivity of the De Bruijn graph
• Particular cycles of a binary de Bruijn digraph
• Circulant matrices and the spectra of de Bruijn graphs

Cites work

• A fast and simple algorithm for the money changing problem
• An Eulerian path approach to DNA fragment assembly
• Matching, Euler tours and the Chinese postman

Cited in

(6)

• The complexity of approximate pattern matching on de Bruijn graphs
• Edge minimization in de Bruijn graphs
• Hypergraph covering problems motivated by genome assembly questions
• An efficient algorithm for Chinese postman walk on bi-directed de Bruijn graphs
• An efficient algorithm for chinese postman walk on bi-directed de Bruijn graphs
• Minimum interval cover and its application to genome sequencing

Describes a project that uses

Uses Software

• ExSPAnder
• GAGE
• SPAdes

This page was built for publication: On the Sound Covering Cycle Problem in Paired de Bruijn Graphs

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