神经网络进化树.

§3.7神经网络法§3.7.1简化的神经元数学模型§3.7.2BP(BackPropagate)神经元网络模型问题：假设给定了N个样本：{xk,yk},(k=1,2,…,N)如何训练网络，使得当输入为xk时，输出尽可能接近yk？让我们考虑样板k:正向传播：结点j的输入应为：iliklijljkownet1而输出则由激活函数f决定：)(ljkljknetfo逆向回传(调节连接权重)：用t表征输出层的单元，将期望的输出(准确值)记为yk={ytk},对应的实际输(预报值)出记为ŷk={ŷtk}。逆向回传就是以期望输出和实际输出的差别(yk-ŷk)为依据，来修正网络的连接权重w，之后又进行新一轮的预报。这种迭代过程一遍遍进行，直到平方型误差函数：NkttktkyyE12)(的值已经很小，且在最近很多次的迭代中都基本保持不变或在一个很小的范围内波动（称为收敛），则说明网络已经完成了学习的过程。可以推导出连接权修正公式为：mljmlmkljkljkljkjkjkljklikNkljkijijwnetfjnetfyyjoww1111)(,)()(,0不是输出单元若为输出单元若一般地，随着一轮轮的学习，输出误差应该越来越小，直到达到稳定于一个很小的值要求(称为收敛)，学习过程就完成了。若总是不收敛，则可能是学习样板集不合适。§3.7.3人工神经元网络的基本特征1.分布存储和容错性；2.大规模并行处理；3.自学习、自组织、和自适应性；4.具有一般非线性动态系统的特征；5.适于处理一些环境信息复杂、知识背景不清楚和推理规则不明确的问题。§3.7.4实例:用BP网络预测蛋白质二级结构1.参考文献：J.Mol.Biol.202:865-884,1988PIVDTGSVAPLSAAEKTKIRSAWAPVYDILVKFFTAKVPIVDTGSVAPLSAAEKTKIRSAWAPVYDILVKFFTAKV-----hhhhhhhhhhhhhhh-------eeeeeeeee--网络设计:•在蛋白质中，一个氨基酸残基处于什么样的二级结构中，一般会受到它前后氨基酸的影响，一般地，离得越远，影响越弱。另一方面，要构成一段-helix或-sheet也需要一定长度的序列。•综合考虑这些因素，可以考虑序列长度为15个氨基酸。•为了便于计算，让输入层的神经元只处于两种状态：抑制或兴奋，用0和1来代表。•为了完全区别20种氨基酸，我们用20个连续的神经元来代表一个氨基酸，其中19个处于抑制状态，一个处于兴奋状态，见编码表。这样一来，输入层有15×20=300个神经元。•输出应能反映三种状态：-helix，-sheet，和coil(无规卷曲)，所以，可用100,010,001表示之，所以，输出层只需三个神经元。•隐蔽层可有可无。若引入隐蔽层，按经验，其神经元个数介于输入和输出层之间，并逐层减少。氨基酸编码Ala10000000000000000000Arg01000000000000000000Asn00100000000000000000Asp00010000000000000000Cys00001000000000000000Gln00000100000000000000Glu00000010000000000000Gly00000001000000000000His00000000100000000000Ile00000000010000000000Leu00000000001000000000Lys00000000000100000000Met00000000000010000000Phe00000000000001000000Pro00000000000000100000Ser00000000000000010000Thr00000000000000001000Trp00000000000000000100Tyr00000000000000000010Val00000000000000000001网络设计:神经元j的输入(Ej)输出模型(sj)：jEjjeEFs11)(ijiijjbswE选取训练学习集和测试集从PDB数据库获得的二级结构信息：PIVDTGSVAPLSAAEKTKIRSAWAPVYDILVKFFTAKV-----hhhhhhhhhhhhhhh-------eeeeeeeee--可取得的学习样板：PIVDTGSVAPLSAAEV处于-helix中；IVDTGSVAPLSAAEKA处于-helix中；…….EKTKIRSAWAPVYDIA处于coil中；…….WAPVYDILVKFFTAKL处于-sheet；…….预测过程：对要预测的序列，截取一段15个氨基酸残基的序列作为输入，按学习过程的同样算法可得出其输出，根据三个输出单元中那一个的值最大，来决定这段序列最中间的残基可能处于哪种二级结构中，例如，对于输入序列：DTGSVAPLSAAEKTK如果三个输出单元的值依次为0.92,0.05,0.21则我们预测其中的残基L处于-helix中。按这种方法，从N端到C端每次移动一个氨基酸残基不断进行，我们就可以预测出一个蛋白质的二级结构(两端的各7个残基除外)。对预测准确率的评价：以N代表被预测到的序列区域中残基总数，T，T，Tc分别代表其中实际属于-helix,-sheet和coil的数目(N=T+T+Tc)；用P代表实际为，也正确地预测为的数目，P和Pc的意义类似；定义预测成功率为：NPPPcQ3显然,10,,,3QTPTPTPccQ3这个指标有一个较大的缺陷，就是当三种结构的成分比例很不平衡时，不能客观地反映预测的质量。现在普遍使用的是一个称为“相关系数”的指标，计算时，用n代表实际不是，也正确地预测为不是的数目；u代表实际为，但没预测为的数目(遗漏)；o代表实际不是，但预测为的数目(过度)。预测结果的相关系数定义为：))()()(()()(onunoPuPounPC11,,,CTToTuTTncc显然C=1对应最高质量的预测：是否为的判断全部正确；C=-1正相反。按相同的方法算出C和Cc，就能较客观地反映预测质量。例：序列：PIVDTGSVAPLSAAEKTKIRSAWAPVYDILVKFFTAKV实际：-----hhhhhhhhhhhhhhh-------eeeeeeeee--预测：*******hhhhhhhhhhh------eeeeeee*******N=24，P=11，P=4，Pc=4,因此Q3=19/24=79%这种方法的实际成功率一般为60~70%n=11,u=2,o=0,因此：85.0143121)011)(211)(011)(211()0*2()11*11(C相关系数的值达到0.35就算是比较成功的预测。§3.8进化树的构建§3.8.1关于进化生物学§3.8.2生命史的三个阶段§3.8.3进化树的特征和术语§3.8.4分子进化树的构建方法§3.8.5分子进化的局限性§3.8.6进化树的可信度检验§3.8.7突破传统分子进化方法的尝试3.8.1关于进化生物学•进化生物学是研究生命的起源及进化的过程、原因、机制、速率和方向的科学。•进化生物学的基础理论就是进化论。•研究生物进化的三个途径：化石纪录，形态比较，大分子比较。3.8.2生命史的三个阶段§3.8.3进化树的特征和术语•N个物种的无根树，有[(2N-5)*(2N-7)*•••*1]种结构；•每种结构的树都有(2N-3)条分支，(N-2)个结点；•任何分支都可以看成是根;•连接两个物种的所有分枝长度之和为它们的距离。No.oftaxaNNo.ofrootedtrees(2N-3)*(2N-5)*(2N-7)*…*1No.ofunrootedtrees(2N-5)*(2N-7)*…*133141535105156945105710395945………§3.8.4分子进化§4.8.4.1生物大分子的进化特征§4.8.4.2分子进化树(phylogenetictree)的构建几个常见建树方法的介绍可靠性检验§4.8.4.3常用的免费软件包§3.8.4.1生物大分子的进化特征•如果以核酸或蛋白质的一级结构的改变(即分子序列中核苷酸或氨基酸的替换数)作为进化改变量的测度，那么生物大分子随时间的改变(即分子进化速率)是相当稳定的，其原因可能是“替换”是一个没有特殊驱动和控制的随机过程。•不同物种同源大分子的进化速率大体相同，如不同动物的血红蛋白分子的进化速率基本上都是k=10-9/aa•a,即每个氨基酸位点每年替换10-9次。•分子进化方法就是利用上述特点，通过不同物种的同源大分子的比较，来确定物种间的亲缘关系，分支时间，进而定出系统进化树的。16SrRNA树和三界理论Woese等人：Proc.NatlAcad.Sci.USA87,4576–4579.§3.8.4.2分子进化树的构建基本思想:物种体内同功能生物分子（如蛋白质或核酸分子）的相似程度越高，则物种的亲缘关系越近。具体步骤:•选择“特征分子”，原则是：a.各个物种都有的同源分子，b.进化速率适当;•对这些同源分子的序列进行多序列比对(multi-sequencesalignment),截取比对的最好的区域作为物种的代表序列；3.按某种方法，算出代表序列两两之间的差异度，如：以及空隙的数目不同残基分别表示相同残基其中,,,,]1)][(341ln[43NgNuNmNgNuNmNgNgNuNmNgNuNmNudS4.基于这些差异度，绘制系统发生树5.对系统发生树进行可信度检验(bootstrap)MaximumParsimonyMethodFundamentalsofMolecularEvolutionpp.106-111适用于已经有了严格多序列alignment结果的情况。例子:位点序列123456789S1AAGAGTGCAS2AGCCGTGCGS3AGATATCCAS4AGAGATCCG有三种结构：具体做法是，对一种结构，将所有位点的可能最小差异得分加起来，得到该结构的总差异得分。假设对任何两个碱基,相同时cost为0，不同时cost为1；那么，对于以结构1的第5个位点：观察位点5在结构1的情况：其可能的最小cost是2我们会发现，对于某些位点，不管树取哪种结构，该位点的cost总是不变，这种位点称为“无信息位点”。在例子中，只有5，7，9三个是“信息位点”。因此，我们实际上只需就这些“信息位点”对每一个种结构计算总差异得分，就能判断那种结构最合理。结构1结构2结构3位点5最小cost212位点7最小cost212位点9最小cost122总最小cost546所以，结构2是最优的，它的tree-length是4。适用于:物种(序列)相似程度很高的情况。优点：找到的一定是最优的树(结构),能推测“祖先”序列。缺点：当物种(序列)的数目较大时(N13)，计算时间太长，所以，可行性很差。No.oftaxaNNo.ofrootedtrees(2N-3)*(2N-5)*(2N-7)*…*1No.ofunrootedtrees(2N-5)*(2N-7)*…*133141535105156945105710395945………FitchandMargoliashMethod参考文献：(Science155:279-284,1987)这是一种基于“距离”的方法,一般步骤如下:1.对要研究的一组物种(或序列),采用某种规则,算出两两之间的距离,构造出距离矩阵;2.选出距离最近的两个物种(比如A和C),把其余的物种看成一个“复合物种”,A到“复合物种”的距离是A和构成“复合物种”的所有物种的距离的平均，C亦然；3.求出A、C、“复合物种”三者构成的