DNA Restriction Mapping from Random-Clone Data

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