Allali Julien, Sagot Marie-France
Institut Gaspard-Monge, Université de Marne-la-Vallée, Cité Descartes, Champs-sur-Marne, 77454, Marne-la-Vallée 2, France.
IEEE/ACM Trans Comput Biol Bioinform. 2005 Jan-Mar;2(1):3-14. doi: 10.1109/TCBB.2005.2.
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations of deletion, insertion, and relabeling classically used in the literature. This allows us to address some serious limitations of the more traditional tree edit operations when the trees represent RNAs and what is searched for is a common structural core of two RNAs. Although the algorithm complexity has an exponential term, this term depends only on the number of successive fusions that may be applied to a same node, not on the total number of fusions. The algorithm remains therefore efficient in practice and is used for illustrative purposes on ribosomal as well as on other types of RNAs.
我们描述了一种用于比较以树的形式编码的两个RNA二级结构的算法，该算法除了文献中经典使用的删除、插入和重新标记的树编辑操作外，还引入了两个新操作，称为节点融合和边融合。当树表示RNA且要寻找的是两个RNA的共同结构核心时，这使我们能够解决更传统的树编辑操作的一些严重局限性。尽管算法复杂度有一个指数项，但该项仅取决于可应用于同一节点的连续融合次数，而不取决于融合的总数。因此，该算法在实践中仍然高效，并用于核糖体RNA以及其他类型RNA的示例。
