【RNA folding】RNA折叠算法与生物物理约束

文章目录

  • RNA折叠
    • RNA folding representation
    • 1 DP for simple folds
      • 1.1 Nussinov Algorithm objective
      • 1.2 energy constraints
      • 1.3 The key idea of the algorithm
    • 2 DP for stacking and complex folds
    • Stochastic context free grammars

来自Manolis Kellis教授(MIT计算生物学主任)的课
油管链接:6.047/6.878 Lecture 7 - RNA folding, RNA world, RNA structures (Fall 2020)
本节课分为三个部分,本篇笔记是第三部分RNA folding。
本课程探讨RNA的折叠过程及其预测方法。先了解了RNA的表示和Nussinov算法的应用。然后通过动态规划预测复杂的RNA叠加与折叠。最后介绍了随机上下文无关文法,为RNA结构提供了广泛的描述框架。

RNA折叠


RNA折叠是一个过程,其中RNA分子将自己折叠成特定的三维结构,这些结构对于其功能至关重要。

RNA folding representation

  1. 初级结构 (Primary)
  2. 二级结构 (Secondary): 二级结构展示了RNA分子如何在空间中折叠并通过氢键形成基对。tRNA和rRNA就是依赖其二级结构来发挥作用的。
    • 某些RNA的功能区域可能是由其特定的二级结构模式决定的。
  3. 三级结构 (Tertiary): 三级结构描述了RNA分子如何进一步在三维空间中折叠,以形成更复杂的结构。在这一级,分子的不同部分可能会通过疏水相互作用、范德华力和其他非共价相互作用来相互接触。

  1. 能量的覆盖: RNA二级结构占据了折叠过程中的大部分自由能。这意味着RNA的稳定性和形成方式在很大程度上取决于其二级结构。
  2. 生化粗粒化: RNA的二级结构为我们提供了一个粗略的、生化上有意义的3D结构表示。这使得研究人员可以更容易地理解RNA的空间排布和功能性质。
  3. 折叠的中间态: 在形成其完整的三维结构之前,RNA首先会形成一个稳定的二级结构。这是RNA折叠成其最终功能形态的关键步骤。
  4. 进化上的保守性: 在进化过程中,RNA的二级结构往往是保守的。这意味着相似的二级结构在不同的生物中可能具有相似的功能。
  5. 易于计算处理: 与RNA的完整三维结构相比,其二级结构相对简单,因此更容易在计算机上建模和分析。

这个图展示了RNA二级结构的不同表示方法。以下是每种表示方法的简要解释:

  1. 常规图(Conventional plot): 这种图形展示了RNA分子的实际形状和其碱基配对。

  2. 圆形图(Circle plot/outerplanar graph): 这是RNA二级结构的另一种表示方法,其中RNA序列被放置在一个圆上,碱基配对则由连接线表示。这种方法适用于显示复杂的或交叉的碱基配对关系

  3. 括号表示法(Parenthesis representation): 在这种表示法中,RNA序列从左到右写出,而碱基配对则通过括号表示。匹配的左括号和右括号表示一对碱基配对,而点表示未配对的碱基。这种表示法非常紧凑,适用于计算和算法处理。

  4. 点图(Dot-plot): 点图显示了RNA序列内部所有可能的碱基配对。图上的每个点代表一个特定的碱基配对。这种方法常用于预测RNA二级结构和比较不同结构的相似性。

  5. 山形图(Mountain-plot): 这种表示法通过高度变化来描绘RNA的二级结构。高度的变化反映了RNA结构中的堆叠区域。这提供了一个直观的方式来了解RNA的叠层结构和拓扑形态。

1 DP for simple folds

使用动态规划(Dynamic Programming)来解决RNA折叠问题。RNA折叠是预测RNA分子在三维空间中如何折叠成其稳定的结构的问题。

  • 当RNA分子折叠时,某些碱基对之间会形成氢键,形成了所谓的碱基配对。我们通常希望优化的是整个结构的稳定性,这可以通过计算配对得分来评估
  • 参考我们前面序列对比的动态规划,尝试应用在这里

1.1 Nussinov Algorithm objective

算法目标:预测RNA的二级结构

  • Objective function(目标函数):

    • Nussinov算法的目标是找到具有最大嵌套配对数的RNA结构。所谓的嵌套配对意味着这些配对不与其他配对交叉。
  • Recursive computation(递归计算):

    • Use dynamic programming?
    • How?:具体实施方式涉及建立一个得分矩阵,并通过考虑RNA序列中每个可能的碱基对来填充这个矩阵。每个位置的得分都是基于它可以形成的最佳配对,以及它与其他碱基之间的关系。
  • Similarities to sequence alignment(与序列比对的相似性):

    • 在序列比对中,我们试图找到两个或多个序列之间的最佳对齐方式。对于RNA结构预测,我们试图找到RNA序列内部的最佳对齐方式,即碱基配对方式。

1.2 energy constraints

RNA folding based on biophysical energy constraints(基于生物物理能量约束的RNA折叠)

  1. Scoring scheme(评分方案):

    • 为了决定RNA的最优结构,这里有一个评分系统。在物理上,结构的优化通常是基于最小自由能的。自由能在这里代表稳定性,较低的自由能意味着更稳定的结构。
      • "-1"表示G和U的配对,特殊
    • 为了简化模型,为每对碱基配对分配了一个能量值。例如,A与U的配对有-2的能量值,而C与G的配对有-3的能量值。这些值可能是基于实验数据的。
  2. Does DP apply?(动态规划是否适用?):

    • 考虑到能量分数是可加的。
    • 稍后可能会讨论更复杂的能量模型,但基本的思路是,通过排除某些结构(如伪节点),可以将问题分解为子问题,这使得动态规划变得可行。
  3. Define “matrix”: Eij:

    • 这定义了一个矩阵E,其中Eij表示子序列i到j之间的最小能量。
    • 这个矩阵用于动态规划算法,储存每个子序列的最优解,从而避免重复计算。
  4. Recursion formula(递归公式)Traversal order(遍历顺序)

通过为每对碱基配对分配能量分数,并使用动态规划来找到具有最低总自由能的结构,我们可以获得RNA的预测结构。

1.3 The key idea of the algorithm

右侧的图显示了一个填充了数字的大矩阵。这个矩阵的填充表示算法的动态规划过程。每个矩阵的单元格代表一个RNA子序列的得分。为了找到整个RNA序列的最优二级结构,算法会逐步填充这个矩阵。

  1. 矩阵的对角线:矩阵的对角线上的值都是0,因为一个单独的碱基不能与自己形成配对,所以得分为0。

  2. 填充顺序:可以看到图中的蓝色箭头,这表示填充矩阵的顺序。算法从对角线开始,然后向右上方移动,填充每一个子矩阵。

  3. 碱基配对:在图中,有些地方用线连接了两个点。这表示在那个特定的RNA子序列中,两个碱基形成了配对。

  4. 计算得分:当计算F(i, j)时,我们会查看以下两种情况:

    1. ij配对的得分(如果它们可以配对的话)加上子序列F(i+1, j-1)的得分。
    2. 不考虑ij的配对,而是查看从ij之间所有可能的分割点k,然后取F(i, k)F(k+1, j)的得分之和的最大值。
    3. 下一个遍历是往右上角遍历
  5. 该矩阵的填充反映了RNA序列的所有可能的二级结构。算法通过比较所有这些可能性来找到得分最高的结构。

  1. i , j i,j i,j配对:

    • 在这种情况下,位置 i i i的碱基与位置 j j j的碱基形成了配对,因此它们之间形成了一个碱基对。
    • 同时,子序列 x i + 1 x_{i+1} xi+1 x j − 1 x_{j-1} xj1 可能还有其他的最佳配对,记为 F ( i + 1 , j − 1 ) F(i+1, j-1) F(i+1,j1)
  2. i i i未配对:

    • 在这里,位置 i i i的碱基没有与任何其他碱基配对。
    • 子序列 x i + 1 x_{i+1} xi+1 x j x_j xj 继续寻找其他可能的最佳配对。
  3. j j j未配对:

    • 与“ i i i未配对”的情况类似,这里位置 j j j的碱基没有与任何其他碱基配对。
    • 子序列 x i x_i xi x j − 1 x_{j-1} xj1 继续寻找其他可能的最佳配对。
  4. 分叉:

    • 在这种情况中,序列在某个位置 k k k处被分成了两部分。
    • x i x_i xi x k x_k xk 的子序列和从 x k + 1 x_{k+1} xk+1 x j x_j xj 的子序列分别寻找自己的最佳配对。
    • 这是一个更复杂的情况,因为我们需要考虑从 i i i j j j之间的所有可能的 k k k值,并为每个 k k k值计算其得分 F ( i , k ) + F ( k + 1 , j ) F(i, k) + F(k+1, j) F(i,k)+F(k+1,j)。最后,我们选择使得 F ( i , j ) F(i, j) F(i,j) 得分最大的 k k k值。

2 DP for stacking and complex folds

Nussinov能量模型的局限性

  • 除了单个碱基对外,RNA碱基还倾向于在空间中堆叠,形成堆叠结构。这里显示了一个G-C配对和一个A-U配对的堆叠。堆叠交互是由于相邻碱基对之间的香族环的π-π交互。
  • 堆叠交互为RNA分子提供了额外的稳定性,因此它们对RNA分子的整体自由能有着重要的贡献。

  • 基于环(Loop)的能量模型
  1. 堆叠的碱基(Stacked bases)、发夹环(Hairpin loop)、内部环(Interior loop)、Bulge、以及多环(Multi loop)。这些是RNA二级结构的基本组成部分。

“任何二级结构 ( S ) 都可以被唯一地分解成多个环 ( L )”:这意味着任何RNA的二级结构都可以被唯一地分解为环。

  • “分子的自由能 ( $\Delta G $) 是其环的自由能之和”:整个RNA分子的自由能是由它的各个环的自由能组成的。
  • 这可以用以下公式表示:
    $
    \Delta G(S) = \sum_{L \in S} \Delta G(L)
    $
    这表示分子 ( S ) 的自由能是它包含的所有环 ( L ) 的自由能的总和。

扩展补充:

  • Structural ensemble and base-pairing probability

二维的点图,用于可视化RNA分子中可能的碱基配对的概率

在室温下,RNA不仅形成一个结构,而是存在为一系列可能的结构,称为集合(ensemble)

使用热力学理论来计算特定结构的概率

Stochastic context free grammars

上下文无关文法 (CFG),用于生成回文:
V = { S } , T = { a , b } , P = { S → a S a , S → b S b , S → ϵ } V = \{S\}, \quad T = \{a, b\}, \quad P = \{S \rightarrow aSa, S \rightarrow bSb, S \rightarrow \epsilon\} V={S},T={a,b},P={SaSa,SbSb,Sϵ}
这个CFG可以有效地描述字母表 ({a, b}) 上的所有回文。

RNA文法的例子。这是一个上下文无关文法,旨在模拟RNA的二级结构。RNA分子由四种碱基组成:A(腺苷)、C(鸟苷)、G(鸟嘌呤)和U(尿嘧啶)。
V = { S } , T = { a , c , g , u } , P = { S → a S u , S → c S g , … } V = \{S\}, \quad T = \{a, c, g, u\}, \quad P = \{S \rightarrow aSu, S \rightarrow cSg, \dots\} V={S},T={a,c,g,u},P={SaSu,ScSg,}

这里的产生规则模拟了RNA的碱基配对,例如A与U配对,C与G配对。

解析树 (Parse Tree) 描述了如何使用给定的文法来派生特定的RNA序列。在这个例子中,给定的RNA序列是 (ACAGGAACUGUACGCUGCACCGC),解析树展示了如何从初始非终结符 (S) 开始,通过多次应用产生规则来得到这个序列。

此外,RNA的二级结构图展示了该序列的配对模式,其中一些碱基通过氢键配对形成稳定的结构。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166890.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

进制转换(二进制、八进制、十进制、十六进制)

目录 一:十进制转换为二进制、八进制、十六进制 (1)整数转换 (2)小数转换 1)十进制转二进制 2)十进制转八进制 3)十进制转十六进制 二:二进制、八进制、十六进制转…

安装Sentinel

大家好今天来安装Sentinel . 安装Sentinel 下载 : 大家可以选择相应版本(最新版本1.8.6) 官网下载地址 : Release v1.8.6 alibaba/Sentinel GitHub 链接:Sentinel_免费高速下载|百度网盘-分享无限制 (baidu.com) 提取码:8eh9 运行 : 将jar包放到任…

redis怎么设计一个高性能hash表

问题 redis 怎么解决的hash冲突问题 ?redis 对于扩容rehash有什么优秀的设计? hash 目标是解决hash冲突,那什么是hash冲突呢? 实际上,一个最简单的 Hash 表就是一个数组,数组里的每个元素是一个哈希桶&…

EasyCVR视频汇聚平台显示有视频流但无法播放是什么原因?该如何解决?

视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理,实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等,视频智能分析平台EasyCVR融合性强、开放度…

【LeetCode 算法专题突破】滑动窗口(⭐)

文章目录 前言1. 长度最小的子数组题目描述代码 2. 无重复字符的最长子串题目描述代码 3. 最大连续1的个数 III题目描述代码 4. 将 x 减到 0 的最小操作数题目描述代码 5. 水果成篮题目描述代码 6. 找到字符串中所有字母异位词题目描述代码 7. 串联所有单词的子串题目描述代码 …

asp.net特色商品购物网站系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net特色商品购物网站系统 是一套完善的web设计管理系统,系统采用mvc模式(BLLDALENTITY)系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为 vs2010,数据库为sqlserver2008&a…

动手实现H5仿原生app前进后退切换效果

动手实现H5仿原生app前进后退切换效果 前言 最近在优化H5页面&#xff0c;我注意到当开发完成的移动端H5页面嵌入到微信小程序或者原生app中时&#xff0c;当触发页面路由切换会与原生app看上去有点格格不入&#xff0c;因为H5页面<router-view>切换路由时是直接替换了…

网站、小程序常见布局样式记录

文章目录 &#x1f380;前言&#xff1a;&#x1f415;网页样式展示小程序&#xff1a;《携程网》&#x1f380;持续更新... &#x1f380;前言&#xff1a; 本篇博客会收藏一些作者见到的网页、小程序页面&#xff0c;目的是用来寻找制作项目网页页面的灵感&#xff0c;有需要…

【最短路径算法】一文掌握Dijkstra算法,详解与应用示例+代码

目录 1 Dijkstra算法 2 Dijkstra算法的步骤 3 Dijkstra算法python实现 4 Dijkstra算法应用示例详解 1 Dijkstra算法 Dijkstra算法&#xff08;迪杰斯特拉算法&#xff09;是一种用于在加权图中查找从一个起始节点到所有其他节点的最短路径的算法。该算法最初由荷兰计算机科…

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac 问题描述 由于 macOS 系统限制&#xff0c;桌面音频被禁止&#xff0c;导致在使用 OBS 无法录制桌面音频&#xff0c;只能使用自带麦克风录制。 解决方法 Loopback 介绍 借助 Loopback 的强大功能&#xff0c;可以轻松地…

Arduino驱动BMA220三轴加速度传感器(惯性测量传感器篇)

目录 1、传感器特性 2、硬件原理图 3、驱动程序 BMA220的三轴加速度计是一款具有I2C接口的超小型三轴低g加速度传感器断路器,面向低功耗消费市场应用。它可以测量3个垂直轴的加速度,从而在手机、手持设备、计算机外围设备、人机界面、虚拟现实功能和游戏控制器中感知倾斜、…

CUDA学习笔记(八)Branch Divergence and Unrolling Loop

Avoiding Branch Divergence 有时&#xff0c;控制流依赖于thread索引。同一个warp中&#xff0c;一个条件分支可能导致很差的性能。通过重新组织数据获取模式可以减少或避免warp divergence&#xff08;该问题的解释请查看warp解析篇&#xff09;。 The Parallel Reduction …

Hook原理--逆向开发

今天我们将继续讲解逆向开发工程另一个重要内容--Hook原理讲解。Hook&#xff0c;可以中文译为“挂钩”或者“钩子”&#xff0c;逆向开发中改变程序运行的一种技术。按照如下过程进行讲解 Hook概述Hook技术方式fishhook原理及实例符号表查看函数名称总结 一、Hook概述 在逆…

平板有必要买触控笔吗?推荐的ipad手写笔

iPad之所以能吸引这么多人&#xff0c;主要是因为它的功能出色。用来画画、做笔记&#xff0c;也是一种不错的体验。但如果只是用来看电视和打游戏的话&#xff0c;那就真的有点大材小用了。如果你不需要昂贵的苹果电容笔&#xff0c;也不需要用来专业的绘图&#xff0c;那你可…

在软件测试行业这种情况下,凭什么他能拿25k?我却约面试都难?

在当今竞争激烈的软件测试行业中&#xff0c;近期的招聘市场确实面临一些挑战。大量的求职者争相涌入岗位&#xff0c;许多热衷于功能测试的人士甚至难以找到理想的工作机会。更不幸的是&#xff0c;连自动化测试和性能测试这些专业领域也受到了测试开发人员的竞争压力。然而&a…

【瑞吉外卖部分功能补充】

瑞吉外卖部分功能补充 菜品的启售和停售 在浏览器控制台点击对应功能后可以看到前端发送的请求是&#xff1a;http://localhost:9999/dish/status/1?ids1413342036832100354&#xff0c;请求方式为POST。 接收到前端参数后&#xff0c;进行controller层代码补全&#xff0c…

Spark简介

文章目录 一、简介二、安装1、简介2、本地部署(Local模式)2.1 安装2.2 官方WordCount实例 3、Standlong模式3.1 简介2.2 安装集群2.3 官方测试案例 4、Yarn模式3.1 安装3.2 配置历史服务器3.3 配置查看历史日志 5、Mesos模式6、几种模式对比7、常用端口 三、Yarn模式详解1、简介…

Leetcode—1726.同积元组【中等】

2023每日刷题&#xff08;六&#xff09; Leetcode—1726.同积元组 哈希表解题思路 实现代码 class Solution { public:int tupleSameProduct(vector<int>& nums) {unordered_map<int, int>count;int n nums.size();int i, j;for(i 0; i < n - 1; i) {f…

拓扑几何学

目录 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 2&#xff0c;单连通多面体 3&#xff0c;一般多面体 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 在一个联通无向图中&#xff0c;点数-边数面数 1 如&#xff1a; 7-126 1 如果把最外面的五边形外面也算…

机器学习终极指南:统计和统计建模03/3 — 第 -3 部分

系列上文&#xff1a;机器学习终极指南&#xff1a;特征工程&#xff08;02/2&#xff09; — 第 -2 部分 一、说明 在终极机器学习指南的第三部分中&#xff0c;我们将了解统计建模的基础知识以及如何在 Python 中实现它们&#xff0c;Python 是一种广泛用于数据分析和科学计…