Recognizing DNA graphs is difficult.

DOI10.1016/S0166-218X(02)00287-1MaRDI QIDQ1868714zbMATH OpenFDO

Authors P. Schuurman, R. A. Pendavingh, Gerhard J. Woeginger

Publication date 28 April 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://research.utwente.nl/en/publications/47aff9e8-94af-4133-9f23-ccff3bbf2b18

zbMATH Keywords

Computational complexityDe Bruijn graphDNA chain sequencingDNA computingDNA graphsHybridizationNP-hardnessRecognition algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Applications of graph theory (05C90) Biochemistry, molecular biology (92C40)

Recommendations

• De Bruijn graphs and DNA graphs
• On the recognition of de Bruijn graphs and their induced subgraphs
• String graphs. II: Recognizing string graphs is NP-hard
• Characterizations for some types of DNA graphs
• DNA sequencing, Eulerian graphs, and the exact perfect matching problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• On some properties of DNA graphs
• On the hardness of approximating the chromatic number
• The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI

Cited in

(12)

• On the recognition of de Bruijn graphs and their induced subgraphs
• Graph algorithms for DNA sequencing -- origins, current models and the future
• Classification of de Bruijn-based labeled digraphs
• On the complexity of recognizing Wheeler graphs
• Embedding on alphabet overlap digraphs
• Characterizations for some types of DNA graphs
• On the readability of overlap digraphs
• On the Readability of Overlap Digraphs
• De Bruijn graphs and DNA graphs
• Bipartite graphs of small readability
• Selected combinatorial problems of computational biology
• DNA labelled graphs with DNA computing

This page was built for publication: Recognizing DNA graphs is difficult.

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