Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem

DOI10.1051/ro:2006007zbMath1169.90427DBLPjournals/rairo/BlazewiczK05OpenAlexW2152779034WikidataQ57387777 ScholiaQ57387777MaRDI QIDQ5439390

Marta Kasprzak, Jacek Błażewicz

Publication date: 11 February 2008

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2005__39_4_227_0

zbMATH Keywords

computational complexitycombinatorial optimizationpartial digestDNA restriction mapping

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (4)

The simplified partial digest problem: approximation and a graph-theoretic model ⋮ A new dynamic programming algorithm for the simplified partial digest problem ⋮ Genetic and Tabu search algorithms for peptide assembly problem ⋮ On the approximability of the simplified partial digest problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mapping DNA by stochastic relaxation
• Multiple solutions of DNA restriction mapping problems
• A lower bound on the number of solutions to the probed partial digest problem
• A partial digest approach to restriction site mapping
• Complexity of DNA sequencing by hybridization.
• The restriction mapping problem revisited.
• LATIN 2004: Theoretical Informatics
• The NP-completeness column: An ongoing guide

This page was built for publication: Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem