DNA sequencing, Eulerian graphs, and the exact perfect matching problem

DOI10.1007/3-540-36379-3_2MaRDI QIDQ4414481zbMATH OpenFDO

Authors Jacek Blazewicz, Piotr Formanowicz, Marta Kasprzak, Gerhard J. Woeginger, P. Schuurman

Publication date 25 July 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730013.htm, https://ris.utwente.nl/ws/files/42928373/B_a_ewicz2002_Chapter_DNASequencingEulerianGraphsAnd.pdf

zbMATH Keywords

computational biologycomputational complexityDNA computingDNA sequencinggraph theory

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15) Protein sequences, DNA sequences (92D20)

Recommendations

• A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
• Complexity of DNA sequencing by hybridization.
• scientific article; zbMATH DE number 2239908
• Computational complexity of isothermic DNA sequencing by hybridization
• Applications of graph theory in DNA sequencing by hybridization

Cited in

(15)

• Complexity of DNA sequencing by hybridization.
• Euler circuits and DNA sequencing by hybridization
• Recognizing DNA graphs is difficult.
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Edge-outer graph embedding and the complexity of the DNA reporter strand problem
• A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
• Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats
• On the readability of overlap digraphs
• Applications of graph theory in DNA sequencing by hybridization
• On the Readability of Overlap Digraphs
• De Bruijn graphs and DNA graphs
• scientific article; zbMATH DE number 6282157 (Why is no real title available?)
• scientific article; zbMATH DE number 2239908 (Why is no real title available?)
• Bipartite graphs of small readability
• DNA sequence assembly involving an acyclic graph model

This page was built for publication: DNA sequencing, Eulerian graphs, and the exact perfect matching problem

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