Hardness of flip-cut problems from optical mapping.
Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single "consensus" restriction map, and determining the correct orientation of each molecule, which was formalized as the Exclusive Binary Flip Cut (EBFC) Problem in (Muthukrishnan and Parida, 1997). Here we prove that the EBFC problem, as well as a number of its variants, are NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P = NP.
Dancík
V
V
Department of Mathematics, University of Southern California, Los Angeles 90089-1113., USA. dancik@hto.usc.edu
Hannenhalli
S
S
Muthurkrishnan
S
S
D000465:Algorithms; D007091:Image Processing, Computer-Assisted; D008962:Models, Theoretical; D055095:Optics and Photonics; D015183:Restriction Mapping / Q000379:methods*