annealing algorithmbiochemistrycircular DNAcircular mapsDNA mappingDNA subsequencedouble digest problemenzyme cutsinexact experimental measurementsmolecular biologymultiple digest problemNP complete problemspartition problemrestriction enzymesstochastic relaxation algorithmsubadditive ergodic theoremsubadditive processes
With the widely-rumored advent of a human genome project, the problem of DNA mapping has received more attention. Consider two or more enzymes specific for a different DNA subsequence, and a particular strand of DNA. Given the lengths of DNA produced by single and multiple enzyme cuts, ``the mapping problem is the reconstruction of the order of the different enzyme cut sites along the DNA. This paper gives an annealing (stochastic relaxation) algorithm which performs the mapping. The theory of subadditive processes shows that the double digest problem admits an exponentially increasing number of solutions as a function of sequence length. By reducing the partition problem to a special case of the double digest problem, the double digest problem is also shown to be in the class of NP complete problems which are conjectured to have no polynomial time solution. Problems related to circular DNA and inexact experimental measurements are also discussed.
- On the complexity of DNA physical mapping
- Stochastic models for heterogeneous DNA sequences
- scientific article; zbMATH DE number 4087485
- Genome mapping by random anchoring: A discrete theoretical analysis
- DNA rearrangements through spatial graphs
- scientific article; zbMATH DE number 1959501
- Genome mapping by nonrandom anchoring: a discrete theoretical analysis.
- scientific article; zbMATH DE number 1617274
- The enhanced double digest problem for DNA physical mapping
- A representation of DNA primary sequences by random walk
- Computer Solutions of the Traveling Salesman Problem
- Cooling Schedules for Optimal Annealing
- Equation of state calculations by fast computing machines
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Interval graphs and maps of DNA
- Optimization by simulated annealing
- Renewal theory for several patterns
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Subadditive ergodic theory
- The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
- Mean square rates of convergence in the continuous time simulated annealing algorithm on \({\mathbb{R}}^ d\)
- Applications of coding theory to the design of somatic cell hybrid panels
- Multiple solutions of DNA restriction mapping problems
- A partial digest approach to restriction site mapping
- On the complexity of DNA physical mapping
- The enhanced double digest problem for DNA physical mapping
- The restriction mapping problem revisited.
- DNA physical mapping and alternating Eulerian cycles in colored graphs
- The number of clone orderings
- scientific article; zbMATH DE number 4147905 (Why is no real title available?)
- scientific article; zbMATH DE number 4087485 (Why is no real title available?)
- Neighborhood Size in the Simulated Annealing Algorithm
- A SCALABLE PARALLEL ALGORITHM FOR TURNPIKE PROBLEM
- Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem
- Constraint Databases
- Partial digest is hard to solve for erroneous input data
This page was built for publication: Mapping DNA by stochastic relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099802)
