Towards constructing physical maps by optical mapping: an effective, simple, combinatorial approach

S. Muthukrishnan, Laxmi Parida

    Research output: Contribution to conferencePaperpeer-review

    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 languageEnglish (US)
    Pages209-219
    Number of pages11
    StatePublished - 1997
    EventProceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB - Santa Fe, NM, USA
    Duration: Jan 20 1997Jan 23 1997

    Conference

    ConferenceProceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB
    CitySanta Fe, NM, USA
    Period1/20/971/23/97

    ASJC Scopus subject areas

    • General Engineering

    Fingerprint

    Dive into the research topics of 'Towards constructing physical maps by optical mapping: an effective, simple, combinatorial approach'. Together they form a unique fingerprint.

    Cite this