Recognizing DNA graphs is difficult.

DOI10.1016/S0166-218X(02)00287-1zbMath1037.92018MaRDI QIDQ1868714

Petra Schuurman, Gerhard J. Woeginger, Rudi A. Pendavingh

Publication date: 28 April 2003

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

zbMATH Keywords

DNA computingNP-hardnessComputational complexityHybridizationDNA graphsDe Bruijn graphRecognition algorithmDNA chain sequencing

Mathematics Subject Classification ID

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

Related Items (9)

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

Cites Work

• On some properties of DNA graphs
• The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI
• On the hardness of approximating the chromatic number
• Unnamed Item
• Unnamed Item
• Unnamed Item

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