Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models
Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models
复制标题
DOI：
10.1007/s00453-016-0196-x
复制
发表时间：
2017-11-01
期刊：
影响因子：
1.1
通讯作者：
Stacho, Ladislav
中科院分区：
文献类型：
--
作者：
Hales, Jozef;Heliou, Alice;Stacho, Ladislav
我们考虑组合RNA设计问题，RNA设计的最小实例，其中必须产生一个RNA序列，采用给定的二级结构作为其最小自由能结构。我们考虑两种自由能模型，其中碱基对的贡献是加性的和独立的：纯组合沃森-克里克模型，它只允许相等贡献的A-U和C-G碱基对，和实值Nussinov-Jacobson模型，它关联任意能量到A-U，C-G和G-U碱基对。我们首先提供了一个完整的表征设计的结构，使用限制的字母表，在四个字母的字母表，提供了一个完整的表征设计的结构，没有不成对的基地。当不成对的基地是允许的，我们刻画了广泛的类（非）可设计结构，并证明了封闭的可设计结构下的口吃操作。一个给定的结构到任何类的成员关系可以在Theta（n）时间内进行测试，包括为正实例生成一个解序列。最后，我们考虑了一个结构近似松弛的设计，并提供了一个Theta（n）算法，给定一个结构S，避免了两个平凡的非可设计的图案，转换S到一个可设计的结构建设性地增加了最多一个碱基对到它的每个茎。
We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the contributions of base pairs are additive and independent: the purely combinatorial Watson-Crick model, which only allows equally-contributing A-U and C-G base pairs, and the real-valued Nussinov-Jacobson model, which associates arbitrary energies to A-U, C-G and G-U base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the four-letter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-) designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in Theta(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating relaxation of the design, and provide a Theta(n) algorithm which, given a structure S that avoids two trivially non-designable motifs, transforms S into a designable structure constructively by adding at most one base-pair to each of its stems.