Hardness of flip-cut problems from optical mapping.

J Comput Biol
Authors
Keywords
Abstract

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.

Year of Publication
1997
Journal
J Comput Biol
Volume
4
Issue
2
Pages
119-25
Date Published
1997 Summer
ISSN
1066-5277
PubMed ID
9228611
Links
Grant list
1R01 HG00987 / HG / NHGRI NIH HHS / United States
GM36230 / GM / NIGMS NIH HHS / United States