Technical Report Number
There are several basic approaches that can be used in attempting to produce high-resolution DNA restriction maps. A standard approach is the match/merge approach in which first the topology of the map units being mapped together is suppressed and lists of potential matches between fragments are generated, and second the topology is introduced to eliminate matchlists which are inconsistent with the topology. This technical report documents a different approach to DNA mapping, known as topological mapping. In topological mapping the precedence of the two criteria are reversed, i.e., the topology of the two map units is used as the primary search constraint and only those fragments within specific topologically constrained bounds are considered for a potential match. In this approach, the primary topological constraint reduces the number of fragment comparisons that must be considered, in comparison to the match/merge approach. The more topological structure is present in each map unit, the greater the reduction. The conceptual approach is discussed in general. Specific mechanisms for implementing the ideas are presented, and the structure of the software based in these mechanisms is described. Heuristic approaches which can be used for pre- and post-processing are suggested and analyzed. Execution results are given for the application of the software to a number of laboratory generated mapping problems, which were provided by the Olson laboratory.
Moorman, Kenneth; Poulosky, Paul; and Gillett, Will, "DNA Mapping Algorithms: Topological Mapping" Report Number: WUCS-91-23 (1991). All Computer Science and Engineering Research.