Multiple solutions of DNA restriction mapping problems
type: Item
instance of: scholarly article
title: Multiple solutions of DNA restriction mapping problems
zbMATH Open document ID: 0760.92007
DOI: 10.1016/0196-8858(91)90028-H
author: Michael S. Waterman
author: William R. Schmitt
published in: Advances in Applied Mathematics
publication date: 1992-09-27T00:00:00Z
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.
reviewed by: Dietmar Dorninger
Mathematics Subject Classification ID: 92C40
Mathematics Subject Classification ID: 92D20
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 56902
zbMATH Keywords: equivalence of solutions
zbMATH Keywords: DNA restriction mapping
zbMATH Keywords: fragment length
zbMATH Keywords: enzymes
zbMATH Keywords: DNA sequences
zbMATH Keywords: double digest-problem
zbMATH Keywords: DDP
zbMATH Keywords: NP-hard
zbMATH Keywords: hierarchy of equivalence relations
MaRDI profile type: Publication
cites work: Q4198056
cites work: Mapping DNA by stochastic relaxation
cites work: Interval graphs and maps of DNA
full work available at URL: 0196-8858(91)90028-h
OpenAlex ID: W2007888399
description: scientific article; zbMATH DE number 56902