Parida L
Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York 10012, USA.
J Comput Biol. 1998 Winter;5(4):725-39. doi: 10.1089/cmb.1998.5.725.
Optical Mapping is an emerging technology for constructing ordered restriction maps of DNA molecules. The underlying computational problems for this technology 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 present a uniform framework for the restriction map problems where each of these various models is a specific instance of the basic framework. We achieve this by identifying two "signature" functions f() and g() that characterize the models. We identify the constraints these two functions must satisfy, thus opening up the possibility of exploring other plausible models. We show that for all of the combinatorial models proposed in literature, the signature functions are semi-algebraic. We also analyze a proposed statistical method in this framework and show that the signature functions are transcendental for this model. We also believe that this framework would provide useful guidelines for dealing with other inferencing problems arising in practice. Finally, we indicate the open problems by including a survey of the best known results for these problems.
光学图谱是一种用于构建DNA分子有序限制图谱的新兴技术。针对该技术的潜在计算问题已开展研究，近期文献中也提出了若干模型。其中多数提出了组合模型；部分还给出了统计方法。然而，这些模型彼此之间以及与潜在问题的关联方式并非先验明确的。我们为限制图谱问题提出了一个统一框架，其中各种模型均为该基本框架的特定实例。我们通过识别两个表征模型的“签名”函数f()和g()来实现这一点。我们确定了这两个函数必须满足的约束条件，从而开启了探索其他合理模型的可能性。我们表明，对于文献中提出的所有组合模型，签名函数都是半代数的。我们还在此框架内分析了一种提出的统计方法，并表明该模型的签名函数是超越的。我们还认为，此框架将为处理实际中出现的其他推理问题提供有用指导。最后，我们通过对这些问题最知名结果的综述指出了开放问题。
