Soderlund C, Burks C
Theoretical Biology and Biophysics Group, Los Alamos National Laboratory, NM 87545.
Comput Appl Biosci. 1994 Jun;10(3):349-58. doi: 10.1093/bioinformatics/10.3.349.
GRAM (Genomic Restriction map AsseMbly) takes as input single-digest restriction fragments for a set of overlapping clones and outputs one or more plausible partially ordered restriction maps. For each restriction map, GRAM shows the corresponding alignment of the input clone fragments. Due to the error and uncertainty in experimental data, this problem is computationally difficult to solve; therefore, the principle objective in the design of GRAM is to facilitate man-machine collaborative problem solving. GRAM quickly approximates a solution, as follows. (i) A clustering algorithm determines a probable set of restriction fragments. (ii) An assembly algorithm permutes the set of restriction fragments such that the maximal number of clone fragments are contiguous. The output of the GRAM algorithm is displayed for the user to query and edit. This paper describes the stochastic assembly algorithm and shows how it works with the interactive graphics to support man-machine problem solving. In order to test and verify the performance of GRAM, we have developed a program called genfragII to simulate the digestion of clones and fragments; this program is described and results are presented. GRAM is also being used for a number of genome mapping projects.
GRAM（基因组限制图谱组装）将一组重叠克隆的单酶切限制片段作为输入，并输出一个或多个合理的部分有序限制图谱。对于每个限制图谱，GRAM会显示输入克隆片段的相应比对情况。由于实验数据存在误差和不确定性，这个问题在计算上难以解决；因此，GRAM设计的主要目标是促进人机协作解决问题。GRAM通过以下方式快速逼近一个解决方案。（i）一种聚类算法确定可能的限制片段集。（ii）一种组装算法对限制片段集进行排列，以使最大数量的克隆片段相邻。GRAM算法的输出会显示给用户进行查询和编辑。本文描述了随机组装算法，并展示了它如何与交互式图形配合以支持人机问题解决。为了测试和验证GRAM的性能，我们开发了一个名为genfragII的程序来模拟克隆和片段的消化；本文对该程序进行了描述并展示了结果。GRAM也正被用于多个基因组图谱绘制项目。
