Abstract
We initiate the complexity study of physical mapping with the emerging technology of Optical Mapping (OM) pioneered by the team lead by David Schwartz at the W. M. Keck Laboratory for Biomolecular Imaging, Dept of Chemistry, NYU. In currently popular electrophoretic approaches, information about the relative ordering of the fragments comprising the DNA molecule is lost, thus leading to difficult computational problems of composing the fragments in to a physical map depicting their relative order. In contrast, the relative ordering of the pieces is readily obtained in OM. However, OM faces serious technological challenges as it has low resolution and is fault-prone. We take a combinatorial approach to the problem of constructing physical maps from the erroneous data generated by OM. We identify two abstract problems in this context, namely, the Exclusive Binary Flip-Cut and Exclusive Weighted Flip-Cut problems. For both, we present polynomial time approximation schemes. However, our main contribution here is an extremely simple heuristic algorithm that rapidly and accurately (with in 3% error) constructs the physical map from input data with immense experimental errors and imprecision (even with only 10% expression of a restriction site in the molecules). Our strong experimental results, while being preliminary, seem to indicate that although OM has immense experimental imprecision, the errors appear to be 'local' and hence more easily manageable than the ones in other approaches where the errors appear 'global'. Also, although OM may not be suitable for producing physical maps at the resolution of few base pairs, our results indicate that it may be appropriate for rapidly generating accurate physical maps at the resolution of a few 100's of base pairs.
Original language | English (US) |
---|---|
Pages | 209-219 |
Number of pages | 11 |
State | Published - 1997 |
Event | Proceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB - Santa Fe, NM, USA Duration: Jan 20 1997 → Jan 23 1997 |
Conference
Conference | Proceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB |
---|---|
City | Santa Fe, NM, USA |
Period | 1/20/97 → 1/23/97 |
ASJC Scopus subject areas
- General Engineering