求解蛋白质二维结构预测问题的树搜索算法研究
发布时间：2021-10-06 22:48
蛋白质结构预测问题是指从蛋白质的一级结构预测它的折叠和二级,三级,四级的结构,而蛋白质的结构信息可以给出远多于其序列所能给出的功能机制信息,因此这一问题是生命科学与理论化学所追求的核心问题之一。由于蛋白质结构预测问题已经被证明是一种NP问题,而启发式算法对解决NP问题有着相当大的优势,因此人们试图找到高效的启发式算法解决这种问题。启发式算法是相对于最优化算法提出的一种算法。通过学习自然界中的各种现象,该种算法力图在计算的时间和计算的精度之间取得一个良好的平衡,从而实现在较短的时间内,能够对于比较复杂的问题得到一个可以接受的计算结果。为了解决蛋白质结构预测问题,人们通常将蛋白质结构简化成具体的模型进行计算,本算法是基于其中一种应用十分广泛的模型——HP格点模型。本算法的基础为拟人改进的PERM算法,该算法通过在传统的PERM算法的基础之上增加拟人改进策略对算法进行了优化。这一类算法是一种剪枝算法,通过考虑当前构型在历史构型中的地位以及任意动作对当前构型的影响制定合适的剪枝策略,从而提高算法的搜索效率。本算法是在拟人改进的PERM算法的基础之上对其进行了进一步的优化,使用该算法的计算结果作...
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：49 页
【学位级别】：硕士
【部分图文】：
链长为25的蛋白质的一个最低能量构型尽管SC-HP格点模型是一种简化的蛋白质构型，但是该模型可以在一定程度上很
蛋白质结构的检索过程看作是一种树的搜索过程，这种完能的蛋白质构型的目的，并且不会出现遗漏的问题。但是间复杂度过高，对于链长较长的算例无法在可以接受的时及的 SC-HP 格点模型，之前很复杂的蛋白质结构预测问题问题：对于给定的任意一条给定的蛋白质链，我们需要找对于这样的一个问题，我们很快就可以想出用穷举法进行确定一个相邻坐标用来放初始的球，之后由于需要满足 S则可以将与该球相邻且间距为一的三个格点坐标作为下一后一个球，并且若没有出现合法动作数为 0 的情况，则可。当遍历完所有情况后，就可以得到该蛋白质链的所有可最多的构型即为搜索的目标。而基于该完整算法可以构建示[17]：
华 中 科 技 大 学 硕 士 学 位 论 文成的向量与第 i 个和第 i+1 个氨基酸构成的向量的夹角； 表示第 i 个氨基酸和第 j 个氨基酸之间的空间距离；果第 i 个氨基酸为疏水氨基酸 A，则 =1，否则 = ， 代表主链能量， 代表残基能量。对于 AB 非格点模型，求解的目标是找到一个 ( = )使得该能量公式达到最小值[20]。
【参考文献】：
期刊论文
[1]遗传算法在优化问题中的应用综述[J]. 李岩,袁弘宇,于佳乔,张更伟,刘克平. 山东工业技术. 2019(12)
[2]基于遗传算法预测2D三向的蛋白质结构[J]. 夏慧芳,郭雨珍,江宏昊. 生物信息学. 2019(01)
[3]人工智能AlphaFold成功预测蛋白质3D结构[J]. 医学信息学杂志. 2019(01)
[4]程序设计的时间复杂度优化技巧[J]. 赵美勇,崔旭冉,宋思睿,汤继澳,王梦媛. 数字通信世界. 2019(01)
[5]基于模拟退火与贪心策略的平衡聚类算法[J]. 唐海波,林煜明,李优,蔡国永. 计算机应用. 2018(11)
[6]求解最短路问题的改进禁忌搜索算法[J]. 程航,张磊. 交通科技与经济. 2018(02)
[7]一种求解二维矩形Packing问题的拟人型全局优化算法[J]. 邓见凯,王磊,尹爱华. 计算机工程与科学. 2018(02)
[8]蛋白质结构预测[J]. 邓海游,贾亚,张阳. 物理学报. 2016(17)
[9]带有停滞检测的蚁群算法在2D HP格点模型中的应用[J]. 刘羽,熊壬浩. 计算机应用与软件. 2016(02)
[10]NP完全问题研究及前景剖析[J]. 杜立智,陈和平,符海东. 武汉工程大学学报. 2015(10)
博士论文
[1]基于群智能算法的蛋白质结构预测研究[D]. 陈烨.中国矿业大学 2018
[2]启发式算法中疏散性机制在求解组合优化问题中的应用[D]. 丁俊文.华中科技大学 2017
[3]链式几何结构的拟人型优化方法[D]. 熊正大.华中科技大学 2011
[4]蛋白质结构预测的现实求解方法[D]. 吕志鹏.华中科技大学 2007
硕士论文
[1]局部搜索算法求解组合优化问题[D]. 张永飞.东北师范大学 2018
[2]AB非格点模型蛋白的混合型结构预测算法研究[D]. 孙媛媛.南京信息工程大学 2014
[3]求解圆形Packing问题及模型蛋白结构预测问题的启发式算法[D]. 周国城.南京信息工程大学 2011
[4]基于AB非格模型与遗传退火算法的蛋白质折叠结构预测[D]. 林晓丽.武汉科技大学 2007
[5]关于蛋白质折叠构形预测问题的一个PERM改进算法[D]. 崔茂林.华中科技大学 2004
本文编号：3420888
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：49 页
【学位级别】：硕士
【部分图文】：
链长为25的蛋白质的一个最低能量构型尽管SC-HP格点模型是一种简化的蛋白质构型，但是该模型可以在一定程度上很
蛋白质结构的检索过程看作是一种树的搜索过程，这种完能的蛋白质构型的目的，并且不会出现遗漏的问题。但是间复杂度过高，对于链长较长的算例无法在可以接受的时及的 SC-HP 格点模型，之前很复杂的蛋白质结构预测问题问题：对于给定的任意一条给定的蛋白质链，我们需要找对于这样的一个问题，我们很快就可以想出用穷举法进行确定一个相邻坐标用来放初始的球，之后由于需要满足 S则可以将与该球相邻且间距为一的三个格点坐标作为下一后一个球，并且若没有出现合法动作数为 0 的情况，则可。当遍历完所有情况后，就可以得到该蛋白质链的所有可最多的构型即为搜索的目标。而基于该完整算法可以构建示[17]：
华 中 科 技 大 学 硕 士 学 位 论 文成的向量与第 i 个和第 i+1 个氨基酸构成的向量的夹角； 表示第 i 个氨基酸和第 j 个氨基酸之间的空间距离；果第 i 个氨基酸为疏水氨基酸 A，则 =1，否则 = ， 代表主链能量， 代表残基能量。对于 AB 非格点模型，求解的目标是找到一个 ( = )使得该能量公式达到最小值[20]。
【参考文献】：
期刊论文
[1]遗传算法在优化问题中的应用综述[J]. 李岩,袁弘宇,于佳乔,张更伟,刘克平. 山东工业技术. 2019(12)
[2]基于遗传算法预测2D三向的蛋白质结构[J]. 夏慧芳,郭雨珍,江宏昊. 生物信息学. 2019(01)
[3]人工智能AlphaFold成功预测蛋白质3D结构[J]. 医学信息学杂志. 2019(01)
[4]程序设计的时间复杂度优化技巧[J]. 赵美勇,崔旭冉,宋思睿,汤继澳,王梦媛. 数字通信世界. 2019(01)
[5]基于模拟退火与贪心策略的平衡聚类算法[J]. 唐海波,林煜明,李优,蔡国永. 计算机应用. 2018(11)
[6]求解最短路问题的改进禁忌搜索算法[J]. 程航,张磊. 交通科技与经济. 2018(02)
[7]一种求解二维矩形Packing问题的拟人型全局优化算法[J]. 邓见凯,王磊,尹爱华. 计算机工程与科学. 2018(02)
[8]蛋白质结构预测[J]. 邓海游,贾亚,张阳. 物理学报. 2016(17)
[9]带有停滞检测的蚁群算法在2D HP格点模型中的应用[J]. 刘羽,熊壬浩. 计算机应用与软件. 2016(02)
[10]NP完全问题研究及前景剖析[J]. 杜立智,陈和平,符海东. 武汉工程大学学报. 2015(10)
博士论文
[1]基于群智能算法的蛋白质结构预测研究[D]. 陈烨.中国矿业大学 2018
[2]启发式算法中疏散性机制在求解组合优化问题中的应用[D]. 丁俊文.华中科技大学 2017
[3]链式几何结构的拟人型优化方法[D]. 熊正大.华中科技大学 2011
[4]蛋白质结构预测的现实求解方法[D]. 吕志鹏.华中科技大学 2007
硕士论文
[1]局部搜索算法求解组合优化问题[D]. 张永飞.东北师范大学 2018
[2]AB非格点模型蛋白的混合型结构预测算法研究[D]. 孙媛媛.南京信息工程大学 2014
[3]求解圆形Packing问题及模型蛋白结构预测问题的启发式算法[D]. 周国城.南京信息工程大学 2011
[4]基于AB非格模型与遗传退火算法的蛋白质折叠结构预测[D]. 林晓丽.武汉科技大学 2007
[5]关于蛋白质折叠构形预测问题的一个PERM改进算法[D]. 崔茂林.华中科技大学 2004
本文编号：3420888
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3420888.html
