TY - CONF
T1 - Hardness of flip-cut problems from optical mapping [DNA molecules application]
T2 - Compression and Complexity of Sequences 1997. Proceedings
Y1 - 1997
A1 - Dancik,V.
A1 - Hannenhalli, Sridhar
A1 - Muthukrishnan,S.
KW - binary shift cut
KW - Biochemistry
KW - Bioinformatics
KW - biological techniques
KW - Biology
KW - biomedical optical imaging
KW - combinatorial mathematics
KW - combinatorial problem
KW - computational complexity
KW - computational problems
KW - DNA
KW - DNA molecule
KW - exclusive binary flip cut
KW - flip-cut problem hardness
KW - Genetic engineering
KW - Genomics
KW - MATHEMATICS
KW - molecular biology
KW - molecular biophysics
KW - molecule orientation
KW - multiple partial restriction maps
KW - NP-complete problem
KW - optical mapping
KW - polynomial time solutions
KW - Polynomials
KW - sequences
AB - 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 by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP
JA - Compression and Complexity of Sequences 1997. Proceedings
PB - IEEE
SN - 0-8186-8132-2
M3 - 10.1109/SEQUEN.1997.666922
ER -