《生物信息学 第5章 算法基础.ppt》由会员分享，可在线阅读，更多相关《生物信息学 第5章 算法基础.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章算法与数学基础,算法是解决一个问题的方法的明确而有限的步骤。算法的空间复杂度与算法的时间复杂性。有效算法与无效算法。,图论,欧拉与Knigsberg七桥问题。,图论,许多实际的问题都可以转化为寻找最短路的问题。荷兰计算机科学家Dijkstra发现了一个寻找标有权值的连通的简单图最短路的有效算法（教材例5.1与例5.2）。欧拉图（Euler图）是含有欧拉回的图，而欧拉回指经过图中所有边的回。Flewry在1921年得出一种在欧拉图中寻找一个欧拉回的有效算法（教材例5.3）。图论中的树（Tree）是无圈的连通图。,图论,图论在生物信息学中具有较普遍的应用，如在研究生物亲缘关系时会用到的进化树
2、是一个每个顶点的出度为0或2的树，在基因组测序时采用图论的方法成功研制出片断组装软件，等等。,动态规划,动态规划（Dynamicprogramming）是综合运用分级决策方法和最优化原理而形成的数学方法，它将一个复杂问题划分为若干个关联的子问题，找出子问题的最优解，进而得出原来复杂问题的最优解。算法过程（教材例5.5）,动态规划,在生物信息学中，动态规划方法是很多常用序列分析算法的基础。如在两序列比对时，Needleman-Wunch以及Smith-Waterman等算法应用了动态规划解决问题。另外，用其他算法进行运算时，有时也会用动态规划的方法以求快速有效得到结果。,贝叶斯统计,贝叶斯统计（
3、Bayesianstatistics）是研究当存在不确定性时应如何进行推理的学问，它认为统计就是研究不确定性，并认为不确定性要用概率语言去描述。贝叶斯统计的观点认为概率代表一种相信程度，即根据已有的证据，人们有多大程度相信某事是真的。算法过程（教材例5.6）,贝叶斯统计,贝叶斯统计方法能利用主观知识，用它构建的生物信息学数学模型会随知识的积累不断提高预测准确度。另外，生物大分子序列模型基本上是概率模型，存在很多不确定性，而度量不确定性是正是贝叶斯统计方法的优势。,马尔可夫模型,马尔可夫模型又叫马尔可夫过程、马尔可夫链（Markovchain）。如果有一事件，它按着时间顺序不断发生变化，它将来的
4、状态是完全由现在的状态推导出来，而与过去状态无关，那么这样的发生过程称为马尔可夫过程。算法过程（教材例5.7）,马尔可夫模型,马尔可夫模型是生物信息学中的重要智能算法。生物信息学中通常会用马尔可夫模型寻找具有特定排列特征的序列，如基因中的启动子、外显子序列。,隐马尔可夫模型,隐马尔可夫模型是一种关于时间顺序的概率模型，含有状态集合，字符集合。状态转换的过程取马尔可夫模型，状态通过转移概率矩阵相连接；每一个状态又通过字符生成概率矩阵与一个字符相联系，其中生成的字符序列是作为表观描述的观测结果，而状态集合则是在观测结果中看不到的。算法过程（教材例5.8）,隐马尔可夫模型,隐马尔可夫模型在生物信息学
5、中的应用极广泛，基因预测、蛋白质结构预测、多重序列比对等都会用到隐马尔可夫模型。随着生物序列数据的不断增多，隐马尔可夫模型这种有符号序列特征、包容性强的模型很有应用前景,神经网络模型,神经网络（NeuralNetworks，简称NN）模型是由功能类似神经细胞的处理单元构成，通过对神经细胞处理能力和连接特征等方面的模拟来进行计算的方法。1943年，W.S.Mculloch和W.A.Pitts提出了一个神经细胞数学模型，兴起了神经网络的研究。二十世纪80年代，神经网络建模及应用方面取得了重大进展，目前神经网络已成功应用在各个方面。,神经网络模型,根据不同的研究需要，神经网络可按处理信息的流向、学习
6、方式、连接权系数等方面进行分类。按处理信息的流向分为前向网络模型（见左上图）与反馈网络模型（见右上图）。算法过程（见教材例5.10）,神经网络模型,目前神经网络已成功应用在生物信息学的多个方面。其中一个非常广泛的应用方面是对蛋白质结构的预测：已有较多的论文报导用神经网络法预测蛋白质的二级结构，如PHD（ProfilenetworkfromHeidelberg）预测软件；而空间结构及蛋白质分类也是神经网络模型的一大应用对象。神经网络也用于基因预测中识别内含子、外显子、启动子、转录识别位点等，以及预测蛋白质特殊结构。,遗传算法,遗传算法（GeneticAlgorithms，简称GA）是基于生物自然
7、选择与遗传机理的模仿，完成对问题最优解的随机搜索过程的算法。遗传算法解决问题的过程是先随机产生一组初始解，然后这些解在不断发生变化，变化过程不断把最好的解保留而淘汰较差的解，经过若干次这样的过程后选择最好的解。算法过程（教材例5.12）,遗传算法,遗传算法在生物信息学领域也有较多的应用。多序列比对软件包SAGA就是基于遗传算法设计的。遗传算法在RNA结构预测也有应用，但只用遗传算法进行RNA二级结构预测时效果不一定理想，如果再结合其他的方法，会使结果更好。遗传算法进行蛋白质结构预测时会优于某些已用方法。,聚类分析,聚类分析是根据待分类的样本集的样本间的相似程度进行分类，相互间相似的样本被归为同一类。要进行分类的样本往往没有已知类别的样本可供借鉴，甚至分成几类也不知道。所以通过聚类分析可以获知隐含在数据中的类别特征，为进一步深入研究提供参考。算法过程（教材例5.13与例5.14）,聚类分析,在生物信息学中，生物芯片的结果分析常要用到聚类分析算法将数据分类，再进行深入研究。在病理样品基因表达谱中，聚类分析的结果将有助于找到致病基因或基因群。在分子系统发育分析也用到聚类分析，如UPGMA树的构建。,