zbMATH — the first resource for mathematics

On the complexity of DNA physical mapping. (English) Zbl 0806.92007
Summary: The physical mapping problem is to reconstruct the relative position of fragments (clones) of DNA along the genome from information on their pairwise overlaps. We show that two simplified versions of the problem belong to the class of NP-complete problems, which are conjectured to be computationally intractable. In one version all clones have equal length, and in another clone lengths may be arbitrary. The proof uses tools from graph theory and complexity.

92C40 Biochemistry, molecular biology
68R10 Graph theory (including graph drawing) in computer science
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI