A uniform framework for ordered restriction map problems

Optical Mapping is an emerging technology for constructing ordered restrict ion maps of DNA molecules. The underlying computational problems for this t echnology have been studied and several models have been proposed in recent literature. Most of these propose combinatorial models; some of them also present statistical approaches, However, it is not a priori clear as to how these models relate to one another and to the underlying problem. We prese nt a uniform framework for the restriction map problems where each of these various models is a specific instance of the basic framework. We achieve t his by identifying two "signature" functions f() and g() that characterize the models. We identify the constraints these two functions must satisfy, t hus opening up the possibility of exploring other plausible models. We show that for all of the combinatorial models proposed in literature, the signa ture functions are semi-algebraic. We also analyze a proposed statistical m ethod in this framework and show that the signature functions are transcend ental for this model. We also believe that this framework would provide use ful guidelines for dealing with other inferencing problems arising in pract ice, Finally, we indicate the open problems by including a survey of the be st known results for these problems.