当前课程知识点：算法设计与分析 > 6 Dynamic Programming > 6.4 RNA Secondary Structure > RNA Secondary Structure
再来看一下RNA次级结构问题
RNA记录了生命的密码
它可以表达成
一个由碱基构成的字符串B=b_1b_2...b_n
碱基共有四种
记为{ A, C, G, U }
RNA是一个单股的结构
决定它特征的
首先是碱基的排列顺序
然后就是它的次级结构
RNA会回转回来
元素之间构成碱基对
RNA的这种结构
对于理解分子行为至关重要
比如 如下的RNA序列
通过碱基配对的方式形成如下的结构
下面我们给出次级结构的定义
它是RNA序列中碱基
按照某些规则进行配对的集合S
配对需要满足几条基本准则
第一条 称为Watson-Crick准则
A-U, U-A, C-G, G-C是可以进行配对的
第二个准则是没有急促的弯转
这里指的是任何的一个配对(b_i, b_j)∈S
它们之间至少间隔4个元素
也就是i 第三个准则是配对不能够有交叉 如果(b_i, b_j)和(b_k, b_l)是两组配对 那么它们的顺序不能够有交叉 不能够有i 生物学中一个通常的假设 RNA分子形成具有最优自由能的次级结构 自由能可以有配对的碱基对数量来近似 我们的目标就是给定一个RNA分子 B=b_1b_2...b_n 求一个次级结构S 最大化配对的碱基对数量 下面来看几个例子 用红色的虚线表示配对的碱基对 第一个例子是合法的次级结构 满足我们的三条准则 第二个例子是不合法的 因为这里我们注意到 G和C标示红色的这一对 它们中间只间隔了3个碱基 是急促的弯转 再来看第三个例子 它也不是一个合法的次级结构 因为这里出现了交叉的碱基对 按照动态规划的想法 我们尝试把问题分为n个阶段 在j这个阶段定义OPT(j) 是考虑碱基序列b_1b_2...b_j 所能得到的最大匹配数量 比如在这样一个例子中 如果最优解中碱基t和n匹配 因为碱基对不能够交叉的准则 那么问题被分为两个子问题 一个是要去求从1到t-1 对应的最优次级结构 另一个要求t+1到n的最优次级结构 第一个子问题对应的目标值就是OPT(t-1) 但是 对于第二个子问题来说 它不满足我们所定义的最优结构 我们可以把刚才的想法进一步细化 得到了下面的结构 定义OPT(i, j)是考虑序列 从b_ib_i+1...b_j时所对应的最优值 我们还是分几种情况来讨论 第一种情况 如果i≥j-4 根据不能够急促弯转的要求 在这个范围内没有任何的碱基配对 目标值为零 第二种情况 碱基bj没有获得配对 那么OPT(i, j)=OPT(i, j-1) 最后一种情况 最优解中碱基b_j和某一个碱基b_t配对 因为有碱基对不能够交叉的限制 那我们可以把问题分为两段 第一段从i到t-1这段 第二段从t+1到j-1这段 对应的目标值OPT(i, j)为 b_j和b_t匹配 得到了一个匹配 加上第一段对应的目标值OPT(i, t-1) 再加上第二段的目标值OPT(t+1, j-1) 那么到底j和哪个碱基配在一起呢 我们遍历所有的可能 最优解一定是其中的最大值 那么我们按照什么顺序来求解子问题呢 我们先去求最小区间对应的最优值 下面就可以给出 RNA次级结构问题的 动态规划算法的伪代码 它有两重循环构成 k从5到n-1 i从1到n-k 由动态规划基本方程 我们依次计算M[i,j] 最后返回M[1,n] 即为问题的最优值 循环的次数是O(n^2) 每次循环需要t从i到j-4 计算动态规划基本方程 因为按照区间从小到大的顺序计算 因此每次的运算时间都是O(1)的 总共的运行时间是O(n^3) 总结一下我们学习过的动态规划算法 首先我们要刻画问题的结构 把问题进行阶段的划分 定义最优解的结构 建立动态规划基本方程 然后递归求解问题的最优值 最后可以从求解的信息 返回问题的最优解 通过几个例子 我们给大家展示了 一些常用的技术 比如在加权的区间排序中 用变量是0-1选择的 在分段最小二乘问题中 变量是多元选择的 背包问题中增加了一个新的变量 在RNA次级结构问题中 我们对于一系列区间 建立动态规划基本方程 在动态规划算法的设计分析中 我们用两种方式 一种是从前向后 一种是从后向前 这两种方式没有优劣之分 可根据问题结构的不同 或个人的喜好 采用不同的方式
-1.1 Introduction
-1.2 A First Problem: Stable Matching
--A First Problem: Stable Matching
-1.3 Gale-Shapley Algorithm
-1.4 Understanding Gale-Shapley Algorithm
--Understanding Gale-Shapley Algorithm
-Homework1
-Lecture note 1
--Lecture note 1 Introduction of Algorithm
-2.1 Computational Tractability
-2.2 Asymptotic Order of Growth
-2.3 A Survey of Common Running Times
--A Survey of Common Running Times
-Homework2
-Lecture note 2
--Lecture note 2 Basics of Algorithm Analysis
-3.1 Basic Definitions and Applications
--Basic Definitions and Applications
-3.2 Graph Traversal
-3.3 Testing Bipartiteness
-3.4 Connectivity in Directed Graphs
--Connectivity in Directed Graphs
-3.5 DAG and Topological Ordering
--DAG and Topological Ordering
-Homework3
-Lecture note 3
-4.1 Coin Changing
-4.2 Interval Scheduling
-4.3 Interval Partitioning
-4.4 Scheduling to Minimize Lateness
--Scheduling to Minimize Lateness
-4.5 Optimal Caching
-4.6 Shortest Paths in a Graph
-4.7 Minimum Spanning Tree
-4.8 Correctness of Algorithms
-4.9 Clustering
-Homework4
-Lecture note 4
--Lecture note 4 Greedy Algorithms
-5.1 Mergesort
-5.2 Counting Inversions
-5.3 Closest Pair of Points
-5.4 Integer Multiplication
-5.5 Matrix Multiplication
--Video
-5.6 Convolution and FFT
-5.7 FFT
--FFT
-5.8 Inverse DFT
-Homework5
-Lecture note 5
--Lecture note 5 Divide and Conquer
-6.1 Weighted Interval Scheduling
--Weighted Interval Scheduling
-6.2 Segmented Least Squares
-6.3 Knapsack Problem
-6.4 RNA Secondary Structure
-6.5 Sequence Alignment
-6.6 Shortest Paths
-Homework6
-Lecture note 6
--Lecture note 6 Dynamic Programming
-7.1 Flows and Cuts
-7.2 Minimum Cut and Maximum Flow
--Minimum Cut and Maximum Flow
-7.3 Ford-Fulkerson Algorithm
-7.4 Choosing Good Augmenting Paths
--Choosing Good Augmenting Paths
-7.5 Bipartite Matching
-Homework7
-Lecture note 7
-8.1 Polynomial-Time Reductions
-8.2 Basic Reduction Strategies I
--Basic Reduction Strategies I
-8.3 Basic Reduction Strategies II
--Basic Reduction Strategies II
-8.4 Definition of NP
-8.5 Problems in NP
-8.6 NP-Completeness
-8.7 Sequencing Problems
-8.8 Numerical Problems
-8.9 co-NP and the Asymmetry of NP
--co-NP and the Asymmetry of NP
-Homework8
-Lecture note 8
--Lecture note 8 NP and Computational Intractability
-9.1 Load Balancing
-9.2 Center Selection
-9.3 The Pricing Method: Vertex Cover
--The Pricing Method: Vertex Cover
-9.4 LP Rounding: Vertex Cover
-9.5 Knapsack Problem
-Homework9
-Lecture note 9
--Lecture note 9 Approximation Algorithms
-10.1 Landscape of an Optimization Problem
--Landscape of an Optimization Problem
-10.2 Maximum Cut
-10.3 Nash Equilibria
-10.4 Price of Stability
-Homework10
-Lecture note 10
--Lecture note 10 Local Search
-11.1 Contention Resolution
-11.2 Linearity of Expectation
-11.3 MAX 3-SAT
-11.4 Chernoff Bounds
-Homework11
-Lecture note 11
--Lecture note 11 Randomized Algorithms
-Exam
