Title

DNA Restriction Mapping from Random-Clone Data

Authors

Gwangsoo Rhee, Washington University in St. Louis

Document Type

Technical Report

Publication Date

1988-06-01

Filename

WUCS-88-18.pdf

DOI:

10.7936/K7HX1B2M

Technical Report Number

WUCS-88-18

Abstract

This report addresses the problem of constructing DNA restriction maps from random-close data produced by cutting the whole DNA structure with restriction enzyme and measuring possibly overlapping segments. Our approach to DNA mapping is based on the overlapping segments that occur between adjacent clones. The shortest common superstring problem (SCS) and the shortest common matching string problem (SCMS) are discussed as abstract computational models of DNA mapping. Since these string problems are NP-complete, we need efficient approximation algorithms to avoid excessive computational complexity. Some greedy algorithms to SCMS are presented along with performance data obtained through simulation.

Comments

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

Recommended Citation

Rhee, Gwangsoo, "DNA Restriction Mapping from Random-Clone Data" Report Number: WUCS-88-18 (1988). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/775