English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 Qo the problem of constructingphysical 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 con,tribution here is an extremely simple laeuristic 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 imprecisaon, the errors appear to

Towards constructing physical maps by optical mapping (extended abstract)