生物信息学的算法市公开课一等奖百校联赛特等奖课件.pptx

生物信息学方法介绍生物信息学方法介绍（以下讲义来自北京大学生物信息中心）（以下讲义来自北京大学生物信息中心）第1页1生物信息学研究方法概述生物信息学研究方法概述1.1 生物信息学研究三个层面生物信息学研究三个层面初级层面初级层面中级层面中级层面高级层面高级层面第2页初级层面初级层面基于现有生物信息数据库和资源，利用成熟生物信息学工具基于现有生物信息数据库和资源，利用成熟生物信息学工具（专业网站、软件）处理生物信息学问题（专业网站、软件）处理生物信息学问题生物信息数据库生物信息数据库（NCBI、EBI等）等）基因组序列分析、序列比对软件基因组序列分析、序列比对软件（GCG、BLAST、CLUSTAL等）等）系统发育树结构软件系统发育树结构软件（PHYLIP、PALM、MEGA等）等）分子动力学模拟软件分子动力学模拟软件（GROMACS、NAMD等）等）搜集、整理有特色生物信息学数据集搜集、整理有特色生物信息学数据集第3页中级层面中级层面利用数值计算方法、数理统计方法和相关工具，硕士物信息学利用数值计算方法、数理统计方法和相关工具，硕士物信息学问题问题概率、数理统计基础概率、数理统计基础科学计算基础科学计算基础现有数理统计和科学计算工具现有数理统计和科学计算工具（EXCELEXCEL、SPSSSPSS、SASSAS、MATLAB MATLAB等）等）建立有特色生物信息学数据库建立有特色生物信息学数据库第4页高级层面高级层面提出有主要意义生物信息学问题；自主创新，发展新型方法，提出有主要意义生物信息学问题；自主创新，发展新型方法，开发新型工具，引领生物信息学领域研究方向。开发新型工具，引领生物信息学领域研究方向。面向生物学领域，处理生物学问题面向生物学领域，处理生物学问题数学、物理、化学、计算科学等思想和方法数学、物理、化学、计算科学等思想和方法建立模型，发展算法建立模型，发展算法自行编程，开发软件，建立网页自行编程，开发软件，建立网页（LinuxLinux系统、系统、C/C+C/C+、PERLPERL、数据库技术）数据库技术）第5页从事从事生物信息学研究生物信息学研究应具备多方面科学基础：应具备多方面科学基础：（1）、一定计算能力，包含对应软、硬设备。要有各种数据）、一定计算能力，包含对应软、硬设备。要有各种数据库或者能与国际、国内数据库系统进行有效交流。要有发达、库或者能与国际、国内数据库系统进行有效交流。要有发达、稳定互联网络系统；稳定互联网络系统；（2）、强有力创新算法和软件。没有算法创新，生物信息学）、强有力创新算法和软件。没有算法创新，生物信息学就无法取得连续发展；就无法取得连续发展；（3）、与试验科学，尤其是与自动化大规模高通量生物）、与试验科学，尤其是与自动化大规模高通量生物学研学研究方法究方法与平台技术建立广泛、紧密联络。这些技术，既是产与平台技术建立广泛、紧密联络。这些技术，既是产生生物信息数据主要方法，又是验证生生物信息数据主要方法，又是验证生物信息学研究生物信息学研究结果关结果关键伎俩。键伎俩。从事从事生物信息学研究生物信息学研究人员必须具备多学科交叉知识。人员必须具备多学科交叉知识。第6页1.2 生物信息学生物信息学“降龙十八掌降龙十八掌”第7页第一式第一式第一式第一式 见龙在田见龙在田见龙在田见龙在田 （1）要掌握生物信息数据库及要掌握生物信息数据库及其查询搜索方法其查询搜索方法(Database&searching)对分子生物信息数据库种类以及一些详细数据库掌握和了解对分子生物信息数据库种类以及一些详细数据库掌握和了解从现有数据库中熟练取得需要数据信息（尤其是二级数据库）从现有数据库中熟练取得需要数据信息（尤其是二级数据库）能熟练地进行数据库查询和数据库搜索（数据库查询系统能熟练地进行数据库查询和数据库搜索（数据库查询系统Entrez、SRS；搜索工具；搜索工具BLAST等）等）数据库技术、互联网技术数据库技术、互联网技术第8页第二式第二式第二式第二式 飞龙在天飞龙在天飞龙在天飞龙在天（2）要学会生物信息学软件和要学会生物信息学软件和工具应用工具应用(Software&application)利用成熟生物信息学工具（专业网站、软件）处理生物信息学问题利用成熟生物信息学工具（专业网站、软件）处理生物信息学问题基因组序列分析、序列比对软件（基因组序列分析、序列比对软件（GCG、BLAST、CLUSTAL等）等）系统发育树结构软件（系统发育树结构软件（PHYLIP、PALM等等）基因芯片检测分析软件（商业软件基因芯片检测分析软件（商业软件ScanArray、Array-Pro等等）分子动力学模拟软件（分子动力学模拟软件（GROMACS、NAMD等等）第9页第三式第三式第三式第三式 鸿渐于陆鸿渐于陆鸿渐于陆鸿渐于陆（3）概率论基础概率论基础(Probability theory)随机事件、概率随机事件、概率随机变量、概率分布随机变量、概率分布大数定律、中心极限定理大数定律、中心极限定理几乎用于生物信息学各个方面几乎用于生物信息学各个方面“Most of the problems in computational sequence analysis are essentially statistical.”“Biological sequence analysis”第10页第四式第四式第四式第四式 或跃在渊或跃在渊或跃在渊或跃在渊（4）数理统计基础数理统计基础(Statistical methods)样本和统计量（方差、均值样本和统计量（方差、均值）参数预计、假设检验参数预计、假设检验基本统计分析（方差分析、协方差分析、回归分析）基本统计分析（方差分析、协方差分析、回归分析）惯用统计软件利用（惯用统计软件利用（SPSS、SAS）几乎用于生物信息学各个方面几乎用于生物信息学各个方面第11页第五式第五式第五式第五式 羚羊触藩羚羊触藩羚羊触藩羚羊触藩 （5）基于频率组分分析方法和基于频率组分分析方法和权重矩阵方法权重矩阵方法(Composition analysis&weight matrix method)符号（如碱基）频率反应含有生物学意义序列特征，如内含子剪接位符号（如碱基）频率反应含有生物学意义序列特征，如内含子剪接位点发觉，点发觉，KOZAK规则发觉等规则发觉等核酸组分、氨基酸组分、密码子使用频率核酸组分、氨基酸组分、密码子使用频率主要用于含有特定生物学意义序列特征分析主要用于含有特定生物学意义序列特征分析第12页权重矩阵分析方法举例权重矩阵分析方法举例针对序列信号（一段核酸、蛋白），计算每一位点所使用词汇或叫符针对序列信号（一段核酸、蛋白），计算每一位点所使用词汇或叫符号（号（碱基、氨基酸碱基、氨基酸）频率，频率偏好性反应信号序列特征（）频率，频率偏好性反应信号序列特征（sequence pattern）。）。例：人类基例：人类基因内含子因内含子/外外显子剪接位显子剪接位点序列特征点序列特征分析分析R=A or GY=C or UN=A,G,C or U供体位点供体位点受体位点受体位点第13页Bayesian打分函数打分函数用于剪接位点预测公式用于剪接位点预测公式The likelihood that a property value v(of a new structure)is drawn from the splicing site is:Score for the overall likelihood of the query sequence being a site is:Say we have a sequence S=S1S2Sn.Then one need to calculateSo to look for a donor site in the sequence,we might calculate 第14页第六式第六式第六式第六式 潜龙勿用潜龙勿用潜龙勿用潜龙勿用 （6）信息论方法信息论方法(Information method)信息熵信息熵信息度量：是信息度量：是信息符号信息符号出现何种出现何种状态状态一个不确定性程度，信息取得要一个不确定性程度，信息取得要对不确定性进行否定。对不确定性进行否定。生物信息符号如生物信息符号如ACGT四种符号，状态空间即其全部可能排列四种符号，状态空间即其全部可能排列用于结构预测用于结构预测信息熵信息熵H刻画了由刻画了由pi表示随机试验结果先验不确定性，或观察到输表示随机试验结果先验不确定性，或观察到输出时所取得信息量。出时所取得信息量。第15页第七式第七式第七式第七式 利涉大川利涉大川利涉大川利涉大川 （7）期望最大化（期望最大化（EM）方法）方法(Expectation Maximization)EM算法是一个在不完全数据情况下计算极大似然预计或者后验分布迭代算法是一个在不完全数据情况下计算极大似然预计或者后验分布迭代算法。算法。适合用于含有隐变量模型和问题，适合用于含有隐变量模型和问题，用于结构识别，用于结构识别，如如Motif识别识别MEME方法、方法、HMM中中Baum-Welch算法算法第16页第八式第八式第八式第八式 神龙摆尾神龙摆尾神龙摆尾神龙摆尾 （8）动态规划方法动态规划方法(Dynamic Programming)一个惯用多阶段决议寻优算法一个惯用多阶段决议寻优算法动态规划动态规划用用得最多方面是得最多方面是DNA序列或者蛋白质序列比对序列或者蛋白质序列比对第17页第九式第九式第九式第九式 密云不雨密云不雨密云不雨密云不雨（9）迭代方法迭代方法(Iteration)迭代目标通常是在状态空间找到目标函数收敛稳定解迭代目标通常是在状态空间找到目标函数收敛稳定解在利用模式识别方法时，对系统参数学习通常要经过迭代来实现在利用模式识别方法时，对系统参数学习通常要经过迭代来实现迭代必须能够不停迫近稳定解迭代必须能够不停迫近稳定解用于上述一些方法方法用于上述一些方法方法第18页第十式第十式第十式第十式 突如其来突如其来突如其来突如其来（10）回归、拟合、相关性分析、回归、拟合、相关性分析、关联分析关联分析(Regression,fitting,correlation&association)经典统计分析方法经典统计分析方法主要目标：描述和预测自变量与因变量间关系主要目标：描述和预测自变量与因变量间关系用于上述一些方法方法用于上述一些方法方法第19页第十一式第十一式第十一式第十一式 双龙取水双龙取水双龙取水双龙取水 （11）判别分析方法判别分析方法(Discriminant analysis)用于判别样品所属类型统计分析方法用于判别样品所属类型统计分析方法 条件：已知研究对象总体类别数目及其特征（如：分布规律，或各类条件：已知研究对象总体类别数目及其特征（如：分布规律，或各类训练样本）训练样本）目标：判断未知类别样本归属类别目标：判断未知类别样本归属类别用于基因识别、医学诊疗、人类考古学用于基因识别、医学诊疗、人类考古学第20页第十二式第十二式第十二式第十二式 鱼跃于渊鱼跃于渊鱼跃于渊鱼跃于渊（12）聚类分析方法聚类分析方法(Clustering method)聚类分析（群分析）是实用多元统计分析一个新分支，正处于发展阶聚类分析（群分析）是实用多元统计分析一个新分支，正处于发展阶段。理论上还未完善，但应用十分广泛。实质上是一个分类问题，目标是段。理论上还未完善，但应用十分广泛。实质上是一个分类问题，目标是建立一个分类方法，将一批数据按照特征亲疏、相同程度进行分类。建立一个分类方法，将一批数据按照特征亲疏、相同程度进行分类。条件：研究对象总体类别数目未知，也不知总体样本详细分类情况条件：研究对象总体类别数目未知，也不知总体样本详细分类情况目标：经过分析，选定描述个体相同程度统计量、确定总体分类数目、目标：经过分析，选定描述个体相同程度统计量、确定总体分类数目、建立分类方法；对研究对象给出合理分类。建立分类方法；对研究对象给出合理分类。(“物以类聚物以类聚”是聚类分析基是聚类分析基本出发点本出发点)第21页定性、经验分类局限定性、经验分类局限 分类较粗、数据量小、凭借经验分类较粗、数据量小、凭借经验谱系聚类法（系统聚类法）、动态聚类法、含糊聚类法谱系聚类法（系统聚类法）、动态聚类法、含糊聚类法生物信息学中聚类分析问题：生物信息学中聚类分析问题：依据依据DNA芯片取得基因表示数据进行基因聚类（数据量庞大）芯片取得基因表示数据进行基因聚类（数据量庞大）蛋白质相互作用网络分类蛋白质相互作用网络分类 依据不一样物种大分子序列进行相同性比较并构建系统发育树依据不一样物种大分子序列进行相同性比较并构建系统发育树X(1)X(2)X(3)X(4)X(5)GibbonSymphalangusHumanGorillaChimpanzee黑猩猩猩猩猿猴第22页第十三式第十三式第十三式第十三式 震惊百里震惊百里震惊百里震惊百里（13）Markov模型应用模型应用(Markov model)Markov过程：从一个状态转移到另一个状态时，过程仅取决于前面过程：从一个状态转移到另一个状态时，过程仅取决于前面n种状态，是一个有序种状态，是一个有序n模型。模型。n是影响下一个状态选择状态数。是影响下一个状态选择状态数。最简单最简单Markov过程是一阶过程，状态选择完全取决于前一状态，这种过程是一阶过程，状态选择完全取决于前一状态，这种选择是依照概率来选择。选择是依照概率来选择。状态选择是概率，而非确定。故状态选择是概率，而非确定。故Markov过程本质上是一个随机过程。过程本质上是一个随机过程。第23页第十四式第十四式第十四式第十四式 损则有孚损则有孚损则有孚损则有孚（14）隐隐Markov模型方法模型方法(HMM method)将核苷酸序列看成一个随机序列，将核苷酸序列看成一个随机序列，DNA序列编码部分与非编码部分在序列编码部分与非编码部分在核苷酸选取频率上对应着不一样核苷酸选取频率上对应着不一样Markov模型。因为这些模型。因为这些MarkovC+C+GG+C CGGC CGGC C GG C+C+C C GG+GG B BE E0.130.130.120.120.0340.0340.0100.0100.0120.0120.0030.0030.00320.00320.00020.0002模型统计规律是未知，模型统计规律是未知，而而HMM能够自动寻找能够自动寻找出它们隐藏统计规律。出它们隐藏统计规律。对于高等生物这么复杂对于高等生物这么复杂DNA序列，序列，HMM必须必须学习不一样基因结构信学习不一样基因结构信号。号。第24页隐隐Markov模型模型(HMM)语音识别语音识别语音识别语音识别(Speech recognition)(Speech recognition)光字符识别光字符识别光字符识别光字符识别(Optical character (Optical character recognition)recognition)生物序列分析生物序列分析生物序列分析生物序列分析(Biological sequence(Biological sequence analysis)analysis)（1）序列比较与搜寻（尤其是多序列比对）序列比较与搜寻（尤其是多序列比对）（2）基因及信号识别、预测）基因及信号识别、预测（包含（包含DNA编码与非编码区识别、真核编码与非编码区识别、真核基因剪接位点信号识别、非编码区转录调控信号识别、信号肽识别基因剪接位点信号识别、非编码区转录调控信号识别、信号肽识别）（3）蛋白质二级结构、家族、超家族预测、分类等）蛋白质二级结构、家族、超家族预测、分类等生物特征识别生物特征识别生物特征识别生物特征识别(Biometrics)(Biometrics)第25页第十五式第十五式第十五式第十五式 时乘六龙时乘六龙时乘六龙时乘六龙（15）感知器与人工神经网络方感知器与人工神经网络方法法(Perceptron&ANN method)计算机人工神经网络是对大脑神经网络模拟，在生物信息学研究中，不论是计算机人工神经网络是对大脑神经网络模拟，在生物信息学研究中，不论是基因识别还是蛋白质结构预测，神经网络都取得了比其它方法更为准确结果。基因识别还是蛋白质结构预测，神经网络都取得了比其它方法更为准确结果。第26页第27页第十六式第十六式第十六式第十六式 龙战于野龙战于野龙战于野龙战于野（16）决议树、支持向量机及其决议树、支持向量机及其它模式识别方法它模式识别方法(Decision tree&SVM method)模式识别是在输入样本中寻找特征并识别对象一个方法。模式识别是在输入样本中寻找特征并识别对象一个方法。模式识别主要有两种方法，一个是依据统计特征进行识别，另一个是模式识别主要有两种方法，一个是依据统计特征进行识别，另一个是依据对象结构特征进行识别，而后者惯用方法为句法识别。依据对象结构特征进行识别，而后者惯用方法为句法识别。在基因识别中，对于在基因识别中，对于DNA序列上功效位点和特征信号识别都需要用到序列上功效位点和特征信号识别都需要用到模式识别。模式识别。第28页第十七式第十七式第十七式第十七式 履霜冰至履霜冰至履霜冰至履霜冰至（17）微分方程数值方法微分方程数值方法(Numerical methods)分子动力学模拟：硕士物大分子构象，主要还是用基于半经验势函数分子动力学模拟：硕士物大分子构象，主要还是用基于半经验势函数分子动力学方法，而量子力学则在确定势函数参数和研究局部性质时起作分子动力学方法，而量子力学则在确定势函数参数和研究局部性质时起作用。对蛋白质进行动力学研究是利用计算机进行模拟试验基础。用。对蛋白质进行动力学研究是利用计算机进行模拟试验基础。分子动力学得到一组动力学微分方程，要求得到初值问题解。分子动力学得到一组动力学微分方程，要求得到初值问题解。微分方程数值求解：有限差分法、有限元法微分方程数值求解：有限差分法、有限元法第29页十七式合一十七式合一十七式合一十七式合一 亢龙有悔亢龙有悔亢龙有悔亢龙有悔 （18）最终要诀：各类方法综合最终要诀：各类方法综合利用利用All in one!综合利用不一样研究方法综合利用不一样研究方法一直面向生物学问题一直面向生物学问题知识和技能学习方法知识和技能学习方法文件查阅和阅读方法文件查阅和阅读方法中、英文论文写作方法中、英文论文写作方法第30页