Multiple solutions of DNA restriction mapping problems (Q1190148): Difference between revisions

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.