RNAiFOLD: A CONSTRAINT PROGRAMMING ALGORITHM FOR RNA INVERSE FOLDING AND MOLECULAR DESIGN
RNAiFOLD: A CONSTRAINT PROGRAMMING ALGORITHM FOR RNA INVERSE FOLDING AND MOLECULAR DESIGN
复制标题
DOI：
10.1142/s0219720013500017
复制
发表时间：
2013-04-01
影响因子：
1
通讯作者：
Dotu, Ivan
中科院分区：
文献类型：
--
作者：
Antonio Garcia-Martin, Juan;Clote, Peter;Dotu, Ivan
合成生物学是一门迅速崛起的学科，具有长期的影响，从细胞内的单分子检测到合成基因组和新的生命形式的创造。开拓性的团队已经取得了真正非凡的结果--例如，遗传网络的组合合成，使用BioBricks的基因组合成，以及杂交链式反应(HCR)，其中稳定的DNA单体只有在接触到目标DNA片段时才能组装，生物分子自组装途径等。这些工作强烈表明，纳米技术和合成生物学似乎共同构成了21世纪最具变革意义的发展。本文提出了一种求解RNA反向折叠问题的约束规划方法。在给定目标RNA二级结构的情况下，我们确定折叠到目标结构中的RNA序列，即其最小自由能结构是目标结构。我们的方法代表着RNA设计向前迈进了一步--我们产生了第一个完整的RNA反向折叠方法，该方法允许指定广泛的设计约束。我们还引入了一种大型邻域搜索方法，它允许我们以丢失完整性为代价来处理更大的实例，同时保留满足设计约束(Motif、GC-Content等)的优势。结果表明，我们的软件RNAiFold的性能与所有最先进的方法一样好，甚至更好；然而，我们的方法在完备性、灵活性和对各种设计约束的支持方面是独一无二的。本文提出的算法可通过交互式Web服务器http://bioinformatics.bc.edu/clotelab/RNAiFold；公开获取。此外，还可以从该站点下载源代码。
Synthetic biology is a rapidly emerging discipline with long-term ramifications that range from single-molecule detection within cells to the creation of synthetic genomes and novel life forms. Truly phenomenal results have been obtained by pioneering groups - for instance, the combinatorial synthesis of genetic networks, genome synthesis using BioBricks, and hybridization chain reaction (HCR), in which stable DNA monomers assemble only upon exposure to a target DNA fragment, biomolecular self-assembly pathways, etc. Such work strongly suggests that nanotechnology and synthetic biology together seem poised to constitute the most transformative development of the 21st century. In this paper, we present a Constraint Programming (CP) approach to solve the RNA inverse folding problem. Given a target RNA secondary structure, we determine an RNA sequence which folds into the target structure; i.e. whose minimum free energy structure is the target structure. Our approach represents a step forward in RNA design - we produce the first complete RNA inverse folding approach which allows for the specification of a wide range of design constraints. We also introduce a Large Neighborhood Search approach which allows us to tackle larger instances at the cost of losing completeness, while retaining the advantages of meeting design constraints (motif, GC-content, etc.). Results demonstrate that our software, RNAiFold, performs as well or better than all state-of-the-art approaches; nevertheless, our approach is unique in terms of completeness, flexibility, and the support of various design constraints. The algorithms presented in this paper are publicly available via the interactive webserver http://bioinformatics.bc.edu/clotelab/RNAiFold; additionally, the source code can be downloaded from that site.