计算机在分子生物学中的应用.pptVIP

T-coffee算法中最关关键的两个因素是：构建扩展比对信息库和优化。它的算法示意图如下：第94页，共150页，星期日，2025年，2月5日第95页，共150页，星期日，2025年，2月5日其中，基本库是建立在一系列待比较序列的两两比对的基础上的（这种比对有可能是全局的比对，也有可能是局部的比对）。每种比对结果在基本库中的权重是不同的，我们需要对所得的比对结果进行分析，并对每种结果给出一个权重。T-coffee的时间复杂度大至在O（N3L）（其中，L是序列的平均长度）第96页，共150页，星期日，2025年，2月5日（III）DIALIGN算法DIALIGN算法是基于片断一片断的局域多序列比对算法，它首先找出无空位的保守片段对(相当于点矩阵中的对角线)；然后为每一保守片段对赋予一个权重w用以评价其生物意义，并找出具有最大加权总和的相容片断对搜集(consistentcollectionofdiagonals)，这些片段都满足相容性准则，即这些片段对可以被排序，而不会相互重叠；利用贪婪法将对角线依据分值高低逐步联配(assemble)成多序列比对；在序列中加入空位直到所有对角线相关的残基都被适当安置．由于以保守片断作为考虑问题的出发点，自然形成比对的空位位数及空位位置，从而避免了序列比对中的一个最为困扰的问题：空位罚分的设定．第97页，共150页，星期日，2025年，2月5日（I）基于遗传算法的多序列比对SAGA算法基于遗传算法的多序列比对SAGA算法将序列集中不等长的序列以两端加空位方式补齐，构造初始群体中的个体；共设有交叉，加空位，移动空位等22个遗传算子，并根据上一代算子所起的作用，给其以一定的权值，根据权值的大小动态决定这一代是否使用该算子；选用WSP度量作为适应度函数．该算法的优点是：可以对任意多个序列同时比对，而不会受到限制．主要缺点是速度慢，易于陷入局域优化解．第98页，共150页，星期日，2025年，2月5日（II）Prrp迭代比对算法Prrp这是一个著名的迭代比对算法，其基本思想是：将一个序列集随机地分为两组，然后用双重动态规划比对算法再将这两组序列合并起来．对于不同的随机分组重复这种两组比对过程，直到满足终止条件为止．具体算法为：从一个多序列比对开始(这一比对可以由任意简单方法而得到，并做为这个算法的种子)，以该比对中任意两个序列的距离构造一棵系统发育树，并计算所有序列的的权重；以WSP分值优化两组比对；再以该比对作为种子重复进行上述过程，直到权重w收敛为止．第99页，共150页，星期日，2025年，2月5日（III）Muscle算法Muscle算法以系统发育树作为分组依据，使得分组迭代更为合理，该算法主要由三部分组成)：首先初步、快速地利用渐进比对算法构建一个多序列比对结果MSA1；然后以这个比对为基础，计算两两序列的距离，重新用渐进比对算法构建多序列比对MSA2；最后根据指导树的分支点，将序列分为两组(profile)，通过重新比对这两个profile，构建一个新的多序列比对MSA3，若该比对的SP分值有改善则保留，否则删除该比对结果；重复执行第三部分，直到满足事先规定的结束条件为止．由于有导向的分组，使得Muscle算法的准确率高于Prrp。第100页，共150页，星期日，2025年，2月5日5．3分子生物学信息中心及其数据库近20年来，有关分子生物学的大规模研究合作项目（如HGP等）在世界范围内开展起来。这些跨单位，跨地区甚至跨国的科研协作均要求在保证实验数据可靠性与完整性的前提下，及时进行信息的共享。第101页，共150页，星期日，2025年，2月5日分子生物学数据库中数据的增长速度是十分迅速的第102页，共150页，星期日，2025年，2月5日作为分子生物学的数据库，应当要满足以下的特点：时间性注释支撑数据数据质量集成性第103页，共150页，星期日，2025年，2月5日生物分子数据库可以分成一级数据库和二级数据库两大类：一级数据库：数据库中的数据直接来源于实验获得的原始数据，只经过简单的归类整理和注释二级数据库：对原始生物分子数据进行整理、分类的结果，是在一级数据库、实验数据和理论分析的基础上针对特定的应用目标而建立的。第104页，共150页，星期日，2025年，2月5日1、世界上主要的分子生物学信息中心与它们的数据库介绍现阶段建立的分子数据库种类繁多，内容广泛；并且随着网络技术的普及，分子生物学信息系统大都实现了网络化；数据库中的信息量也呈爆炸性的增长；数据库的相关数据操作算法也不断增加。第105页，共150页，星期日，2025年，2月5日在这里规定，当不