ALGORITHMS FOR LOOP MATCHINGS
ALGORITHMS FOR LOOP MATCHINGS
复制标题
DOI：
10.1137/0135006
复制
发表时间：
1978-01-01
影响因子：
1.9
通讯作者：
KLEITMAN, DJ
中科院分区：
文献类型：
--
作者：
NUSSINOV, R;PIECZENIK, G;KLEITMAN, DJ
长链平面折叠问题的一个简化（双基）版本（例如，RNA和DNA生物分子）被公式化为匹配问题。该链被规定为字母A和B的循环或环形序列，长度为n个单位。这里的匹配是指一组A-B基配对或匹配，它们服从平面性条件：如果在循环内部绘制，则没有两个匹配可以彼此交叉。此外，没有两个相邻的字母可以匹配。我们提出了一个动态规划算法，需要步骤和存储，计算的最大值的大小为给定的A-B基序列，这也允许重建一个特定的折叠形式的原始字符串，实现最大匹配大小。该算法可适用于处理较大的字母序列和加权匹配.还提出了一个算法的修改后的问题更接近感兴趣的生化问题：我们要求每个匹配必须相邻于另一个匹配，迫使两个或两个以上的平行匹配组.在预期的最大匹配大小的一些结果。作为，至少有80%的顶点可以匹配上平均anA-Bstring的sizen.We简要讨论的实际应用中使用的压缩版本的非常长的分子与初步块结构的算法。对X174 DNA病毒的J基因进行了最大匹配。最后，我们提出了一些需要进一步研究的问题。
A simplified (two-base) version of the problem of planar folding of long chains (e.g., RNA and DNA biomolecules) is formulated as a matching problem. The chain is prescribed as a loop or circular sequence of lettersAandB,nunits long. A matching here means a set ofA-Bbase pairings or matches obeying a planarity condition: no two matches may cross each other if drawn on the interior of the loop. Also, no two adjacent letters may be matched. We present a dynamic programming algorithm requiringsteps andstorage which computes the size of the maximum for the givenA-Bbase sequence and which also allows reconstructing a particular folded form of the original string which realizes the maximum matching size. The algorithm can be adapted to deal with sequences with larger alphabets and with weighted matchings.An algorithm is also presented for a modified problem closer to the biochemical problem of interest: We demand that every match must be adjacent to another match, forcing groups of two or more parallel matches.Some results on the expected maximum matching size are presented. As, at least 80% of the vertices can be matched on the average on anA-Bstring of sizen.We briefly discuss the practical application of the algorithm by using contracted versions of very long molecules with a preliminary block construction. A maximum matching is presented for the J-gene of theX174 DNA virus. We conclude by stating some problems requiring further study.