Nucleic Acid Sequence Design via Efficient Ensemble Defect Optimization
Nucleic Acid Sequence Design via Efficient Ensemble Defect Optimization
复制标题
DOI：
10.1002/jcc.21633
复制
发表时间：
2011-02-01
影响因子：
3
通讯作者：
Pierce, Niles A.
中科院分区：
文献类型：
--
作者：
Zadeh, Joseph N.;Wolfe, Brian R.;Pierce, Niles A.
我们描述了一种用于设计一个或多个相互作用的核酸链的序列的算法，所述核酸链旨在在平衡时采用靶二级结构。序列设计被制定为一个优化问题，其目标是减少低于用户指定的停止条件的集成缺陷。对于候选序列和给定的靶二级结构，整体缺陷是在非假结二级结构的整体上评估的处于平衡的不正确配对的核苷酸的平均数。为了减少接受或拒绝随机初始序列的突变的计算成本，在目标结构的树分解的叶节点上评估候选突变。在叶优化过程中，使用缺陷加权突变采样来选择每个候选突变位置，其概率与其对叶的总体缺陷的贡献成比例。随着子序列在树中向上合并，通过从新的随机子序列开始在有缺陷的子树内进行重新优化，消除了由兄弟序列之间的串扰引起的新出现的结构缺陷。使用Theta（N-3）动态程序来评估具有N个核苷酸的靶结构的整体缺陷，这种分层方法意味着设计时间上的渐近最优性界限：对于足够大的N，序列设计的成本被限制在完整序列的整体缺陷的单个评估的成本的4/3以下。因此，设计算法具有时间复杂度Omega（N-3）。对于含有N是{100，200，400，800，1600，3200}核苷酸的元素和范围为1至30个碱基对的双链体茎的靶结构，在37 ℃下的RNA序列设计通常成功地满足具有小于N/100的整体缺陷的终止条件。从经验上看，序列设计算法具有渐近最优性，时间复杂度上界的指数是尖锐的。(C)2010 Wiley Periodicals，Inc. J Comput Chem 32：439-452，2011
We describe an algorithm for designing the sequence of one or more interacting nucleic acid strands intended to adopt a target secondary structure at equilibrium. Sequence design is formulated as an optimization problem with the goal of reducing the ensemble defect below a user-specified stop condition. For a candidate sequence and a given target secondary structure, the ensemble defect is the average number of incorrectly paired nucleotides at equilibrium evaluated over the ensemble of unpseudoknotted secondary structures. To reduce the computational cost of accepting or rejecting mutations to a random initial sequence, candidate mutations are evaluated on the leaf nodes of a tree-decomposition of the target structure. During leaf optimization, defect-weighted mutation sampling is used to select each candidate mutation position with probability proportional to its contribution to the ensemble defect of the leaf. As subsequences are merged moving up the tree, emergent structural defects resulting from crosstalk between sibling sequences are eliminated via reoptimization within the defective subtree starting from new random subsequences. Using a Theta(N-3) dynamic program to evaluate the ensemble defect of a target structure with N nucleotides, this hierarchical approach implies an asymptotic optimality bound on design time: for sufficiently large N, the cost of sequence design is bounded below by 4/3 the cost of a single evaluation of the ensemble defect for the full sequence. Hence, the design algorithm has time complexity Omega(N-3). For target structures containing N is an element of {100, 200, 400, 800, 1600, 3200} nucleotides and duplex stems ranging from 1 to 30 base pairs, RNA sequence designs at 37 degrees C typically succeed in satisfying a stop condition with ensemble defect less than N/100. Empirically, the sequence design algorithm exhibits asymptotic optimality and the exponent in the time complexity bound is sharp. (C) 2010 Wiley Periodicals, Inc. J Comput Chem 32:439-452, 2011