We developed a dynamic programming approach of computing common sequence/structure patterns between two RNAs given by their sequence and secondary structures. Common patterns between two RNAs are meant to share the same local sequential and structural properties. Nucleotides which are part of an RNA are linked together due to their phosphodiester or hydrogen bonds. These bonds describe the way how nucleotides are involved in patterns and thus delivers a bond-preserving matching definition. Based on this definition, we are able to compute all patterns between two RNAs in time O(nm) and space O(nm), where n and m are the lengths of the RNAs, respectively. Our method is useful for describing and detecting local motifs and for detecting local regions of large RNAs although they do not share global similarities. An implementation is available in C++ and can be obtained by contacting one of the authors.
展开▼
机译：我们开发了一种动态编程方法，可以通过它们的序列和二次结构给出的两个RNA之间计算公共序列/结构模式。两个RNA之间的常见模式是分享相同的局部顺序和结构性。由于其磷酸二酯或氢键，是RNA的一部分的核苷酸。这些键描述了核苷酸涉及模式的方式，从而提供粘合保留匹配定义。基于该定义，我们能够在时间O（nm）和空间O（nm）中的两个RNA之间的所有模式分别计算，其中n和m分别是RNA的长度。我们的方法对于描述和检测本地图案和检测大RNA的当地区域的方法非常有用，尽管它们不共享全局相似之处。 C ++中有一个实现，可以通过联系其中一个作者来获得。
展开▼
