Miller W, Barr J, Rudd K E
Department of Computer Science, Pennsylvania State University, University Park 16802.
Comput Appl Biosci. 1991 Oct;7(4):447-56. doi: 10.1093/bioinformatics/7.4.447.
We present algorithms for searching a DNA restriction enzyme map for a region that best matches a shorter 'probe' map. Our algorithms utilize a new model of map alignments, and extensive experiments prove our model superior to earlier approaches for certain applications. Let M be the number of map sites and P be the number of probe sites. Our first algorithm, which optimizes only over a restricted class of alignments, requires O(MP log P) worst-case time and O(M + P) space. Our second algorithm, which optimizes over all alignments, runs in O(MP3) time and O(M + P2) space, under reasonable assumptions about the distribution of restriction enzyme cleavage sites. Combining the algorithms gives a map-searching method that optimizes over all alignments in O(MP log P) time in practice. The algorithms' effectiveness is illustrated by searches involving a genomic restriction map of Escherichia coli.
我们提出了一些算法，用于在DNA限制酶图谱中搜索与较短“探针”图谱最匹配的区域。我们的算法采用了一种新的图谱比对模型，大量实验证明，在某些应用中，我们的模型优于早期方法。设M为图谱位点的数量，P为探针位点的数量。我们的第一种算法仅在受限的比对类别上进行优化，最坏情况下需要O(MP log P)时间和O(M + P)空间。我们的第二种算法在所有比对上进行优化，在关于限制酶切割位点分布的合理假设下，运行时间为O(MP3)，空间为O(M + P2)。将这两种算法结合起来，得到了一种在实际中能在O(MP log P)时间内对所有比对进行优化的图谱搜索方法。通过涉及大肠杆菌基因组限制图谱的搜索，说明了这些算法的有效性。
