A polynomial time equivalence between DNA sequencing and the exact perfect matching problem

DOI10.1016/J.DISOPT.2006.07.004MaRDI QIDQ2467125zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 18 January 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.07.004

zbMATH Keywords

computational complexitygraph theorycomputational biologyDNA sequencing

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 1953078
• A DNA algorithm for the maximal matching problem
• Unimodular hypergraph for DNA sequencing: a polynomial time algorithm
• Poisson approximation and dna sequence matching
• Research in Computational Molecular Biology
• An integer programming approach to DNA sequence assembly

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Complexity of DNA sequencing by hybridization.
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• Maximum matching of given weight in complete and complete bipartite graphs
• On a linear diophantine problem of Frobenius
• On some properties of DNA graphs
• Optimizing over a slice of the bipartite matching polytope
• The complexity of restricted spanning tree problems

Cited in

(6)

• Deterministic polynomial-time algorithms for designing short DNA words
• Unimodular hypergraph for DNA sequencing: a polynomial time algorithm
• scientific article; zbMATH DE number 1953078 (Why is no real title available?)
• scientific article; zbMATH DE number 2239908 (Why is no real title available?)
• Complexity of DNA sequencing by hybridization.
• On generalized balanced optimization problems

This page was built for publication: A polynomial time equivalence between DNA sequencing 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 Q2467125)