Hardness of flip-cut problems from optical mapping [DNA molecules application]
| Title | Hardness of flip-cut problems from optical mapping [DNA molecules application] |
| Publication Type | Conference Papers |
| Year of Publication | 1997 |
| Authors | Dancik V, Hannenhalli S, Muthukrishnan S |
| Conference Name | Compression and Complexity of Sequences 1997. Proceedings |
| Date Published | 1997/06/11/13 |
| Publisher | IEEE |
| ISBN Number | 0-8186-8132-2 |
| Keywords | binary shift cut, Biochemistry, Bioinformatics, biological techniques, Biology, biomedical optical imaging, combinatorial mathematics, combinatorial problem, computational complexity, computational problems, DNA, DNA molecule, exclusive binary flip cut, flip-cut problem hardness, Genetic engineering, Genomics, MATHEMATICS, molecular biology, molecular biophysics, molecule orientation, multiple partial restriction maps, NP-complete problem, optical mapping, polynomial time solutions, Polynomials, sequences |
| 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 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 |
| DOI | 10.1109/SEQUEN.1997.666922 |