Multiple solutions of DNA restriction mapping problems

DOI10.1016/0196-8858(91)90028-HMaRDI QIDQ1190148zbMATH OpenOpenAlexFDO

Authors Michael S. Waterman, William R. Schmitt

Publication date 27 September 1992

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

Full work available at URL https://doi.org/10.1016/0196-8858(91)90028-h

zbMATH Keywords

DDPDNA restriction mappingDNA sequencesdouble digest-problemenzymesequivalence of solutionsfragment lengthhierarchy of equivalence relationsNP-hard

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Review text

If an (unknown) DNA-sequence is cut into fragments of measurable lengths by first applying an enzyme \(A\), then applying a different enzyme \(B\) and finally applying \(A\) and \(B\) together, the problem arises to find permutations of the \(A\)- and the \(B\)-fragments such that the obtained orders lead to the set of lengths of the fragments which are obtained, when \(A\) and \(B\) are applied together (double digest-problem). The DDP is NP-hard and the number of its solutions exponentially increases with the length of the DNA-molecule. However, the set of solutions can be divided into different classes of solutions that are equivalent in respect to various concepts of equivalence, such as symmetries of arrangements of fragments and the property that the fragments have the same overlap data. Thus a hierarchy of equivalence relations is established, the classes of the relations are characterized and their numbers are determined.

Recommendations

• scientific article; zbMATH DE number 4147905
• scientific article; zbMATH DE number 4087485
• Mapping DNA by stochastic relaxation
• The restriction mapping problem revisited.
• Double digest revisited: complexity and approximability in the presence of noisy data

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Interval graphs and maps of DNA
• Mapping DNA by stochastic relaxation

Cited in

(16)

• A lower bound on the number of solutions to the probed partial digest problem
• Refining restriction enzyme genome maps
• The enhanced double digest problem for DNA physical mapping
• Exact solution for the boundary-crossing problem in genetic mapping experiment
• The restriction mapping problem revisited.
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• The number of clone orderings
• A new dynamic programming algorithm for the simplified partial digest problem
• scientific article; zbMATH DE number 1617274 (Why is no real title available?)
• Double digest revisited: complexity and approximability in the presence of noisy data
• scientific article; zbMATH DE number 4147905 (Why is no real title available?)
• scientific article; zbMATH DE number 4087485 (Why is no real title available?)
• scientific article; zbMATH DE number 4116361 (Why is no real title available?)
• Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem
• Constraint Databases
• Selected combinatorial problems of computational biology

This page was built for publication: Multiple solutions of DNA restriction mapping problems

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