Document Type

Technical Report

Publication Date

1993

Filename

WUCS-93-48.pdf

Technical Report Number

WUCS-93-48

Abstract

A technique called Synchronized Double Digest Mapping (SDDM) is presented; it combines classical Double Digest Mapping (DDM) and Multiple-Restriction-Enzyme Mapping (MREM). Classical DDM is a technique for determining the order of restriction fragments in a clone given three digestions of the clone: a digestion by enzyme1, a digestion by enzyme2, and a digestion by enzyme1 and enzyme2 combined. All algorithms for applying this technique are exponential (in the number of fragments present in the clone) in nature. MREM is an extension of classical high-resolution restriction-fragment mapping of a YAC or a genome, in which the overlaps among a set of clones are used to infer a partial order of the restriction fragments. The extension produces maps for several different restriction enzymes concurrently, using clone-end information as a synchronizing mechanism to guarantee consistent and precise clone placement in all maps. These two techniques can be combined if MREM is performed on clones digested in three ways: a digestion by enzyme1, a digestion by enzyme2, and a digestion by enzyme1 and enzyme2 combined. The three resulting maps contain groups of fragments (each group significantly smaller than a clone) to which classical DDM can be applied. Clone-end information is again used to synchronize the selection and extraction, from each map, of appropriate regions (corresponding to the same portion of the underlying genome) to which classical DDM can be applied. Fragment orderings determined for small regions are used as "seeds" for determining fragment orderings in other adjacent or overlapping regions. A technique for hypothesizing small missing unregistered fragments (i.e., undetected by the electrophoresis technology) is also presented. Such hypothesized fragments are retained only if their consistency with the remainder of the data can be verified. In essence, MREM supplies a divide-and-conquer mechanism for DDM. The computational complexity of SDDM across the entire YAC or genome is shown to be, in practice, polynomial in time instead of exponential in time.

Comments

Permanent URL: http://dx.doi.org/10.7936/K74M92WK

Download

Share

COinS