生物信息学的算法.pptx

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