Alexiou Athanasios, Vlamos Panayiotis
Department of Informatics, Ionian University, Plateia Tsirigoti 7, 49100 Corfu, Greece.
Bioinformation. 2011 May 7;6(4):162-3. doi: 10.6026/97320630006162.
In general RNA prediction problem includes genetic mapping, physical mapping and structure prediction. The ultimate goal of structure prediction is to obtain the three dimensional structure of bimolecules through computation. The key concept for solving the above mentioned problem is the appropriate representation of the biological structures. Even though, the problems that concern representations of certain biological structures like secondary structures either are characterized as NP-complete or with high complexity, few approximation algorithms and techniques had been constructed, mainly with polynomial complexity, concerning the prediction of RNA secondary structures. In this paper, a new class of Motzkin paths is introduced, the so-called semi-elevated inverse Motzkin peakless paths for the representation of two interacting RNA molecules. The basic combinatorial interpretations on single RNA secondary structures are extended via these new Motzkin paths on two RNA molecules and can be applied to the prediction methods of joint structures formed by interacting RNAs.
一般来说，RNA预测问题包括遗传图谱绘制、物理图谱绘制和结构预测。结构预测的最终目标是通过计算获得生物分子的三维结构。解决上述问题的关键概念是生物结构的适当表示。尽管涉及某些生物结构（如二级结构）表示的问题要么被表征为NP完全问题，要么具有高复杂性，但针对RNA二级结构预测构建的近似算法和技术很少，主要是具有多项式复杂性的算法和技术。本文引入了一类新的莫兹金路径，即所谓的半升高逆无峰莫兹金路径，用于表示两个相互作用的RNA分子。基于单个RNA二级结构的基本组合解释通过这些关于两个RNA分子的新莫兹金路径得到扩展，并可应用于由相互作用的RNA形成的联合结构的预测方法。
