群智能优化算法及在复杂疾病关联分析中的应用研究

发布时间：2020-03-27 13:31

【摘要】：目前,群智能优化算法得到长足的进步和发展,并已成功应用于科学计算和工程领域。然而,随着科技进步和大数据时代的兴起,大量复杂的高维优化问题不断涌现,使得很多现有优化方法不再适用于新问题的求解。近年来,和声搜索(Harmony Search,HS)和差分进化(Differential Evolution,DE)算法在求解复杂优化问题方面引起研究者广泛关注。和声搜索算法具有很强的全局探索能力,不容易陷入局部搜索,适用于复杂的实数和离散优化问题求解。差分进化算法在实数优化方面具有丰富和成熟的研究基础,在复杂问题求解方面也已展现出了优异性能。然而,对于大规模高维(大于500维)复杂优化问题,许多优秀群智能优化算法的全局求解性能会大幅下降。因此,高维复杂优化问题求解成为信息科学领域研究的热点之一。在生命科学领域,高通量测序技术产生了大量组学数据(基因组、代谢组、蛋白质组和糖组学等),为研究人类复杂疾病的致病原因提供了良好的研究基础,但同时也对科学计算技术提出了巨大挑战。特别是在全基因组关联研究(Genome-wide Association Study,GWAS)中,人们试图从全基因组序列中发现多个联合作用于复杂疾病的单核苷酸多态性(Single Nucleotide Polymorphism,SNP)位点,但由于组合爆炸问题,传统的穷举法难以适用于鉴定所有SNP组合位点与复杂疾病的关联性,使得目前成功的GWAS应用还主要是单个SNP致病位点的发现,而对于多SNP联合致病组合位点探测,是非常复杂的高维组合优化问题,依然没有非常好的精确计算方法,成为目前生物信息学与生命科学研究的重点之一。针对上述两个问题,本课题主要从高维复杂优化问题的群智能求解算法及其在人类复杂疾病关联分析中的应用展开研究。为了能够提升高维复杂优化问题的求解性能,重点研究了和声搜索和差分进化算法在搜索过程中全局探索能力(Exploration power)和局部开发能力(Exploitation power)的变化,以及造成算法性能下降的主要因素。发现和声搜索与差分进化算法有一个共同问题,在进行高维复杂问题优化的后期,它们的更新操作成功率会非常低。另外,差分进化算法中的变异算子在求解高维优化问题时,存在大量冗余计算,也是影响算法搜索速度的关键因素,为此,提出了两个求解高维复杂问题的群智能优化算法(面向高维复杂优化问题的和声搜索算法,改进的差分进化算法)。为了能够从高维的SNP数据中快速搜索出多SNP联合致病组合位点,重点研究了使用和声搜索算法探测多SNP联合致病组合位点的可能性,主要从算法的搜索速度和致病组合位点的识别能力方面进行研究,提出了两种基于和声搜索的SNP联合致病位点探测算法。本博士论文主要在以下几个方面进行了较为深入的研究和探索:(1)针对高维多峰值复杂优化问题求解,提出了基于变量动态降维选择调整策略的和声搜索算法(DIHS)。通过比较传统和声搜索算法用于产生新和声的Take-all策略和一个简单的Take-One策略,发现在优化进程的后期,Take-all策略产生优胜新解的成功率随着优化问题维度的增高下降很快,是影响传统HS算法求解速度和精度的关键因素。为此,提出采用变量动态降维选择调整策略和动态步长扰动机制,用以提高和声搜索算法产生优胜新解的成功率,从而提升算法全局求解能力。通过对12个多峰和4个单峰的典型优化问题进行测试,结果表明,对于高维多峰值优化问题,DIHS在搜索过程中能够始终保持较高的更新操作成功率,并能够以较小的运行代价获得高精度全局最优解。与标准HS相比,在求解1000维的这16个测试问题时,求解精度平均提升了 90.33%,且运行时间平均减少23.8%。(2)针对差分进化(Differential Evolution,DE)算法在进行高维复杂问题求解时存在大量冗余计算、易陷入局部搜索等问题,提出改进的差分进化算法,将变异算子和交叉算子相融合,引入局部变量动态调整策略,以增强DE的全局搜索能力。采用动态的交叉概率参数(Crossover rate,CR)同时管理变异算子和局部变量调整策略,用于降低计算冗余。通过实验测试表明,提出的DE算法的求解质量在所有测试问题上都优于标准DE算法,并且在求解1000维的16个复杂测试问题时,计算速度平均提升13.79%,全局最优解的求解精度平均提升81.96%。另外通过与三个经典的复杂问题求解算法(SaDE,CoDE,CMAES)和7个高维问题求解算法相比较,证明了改进DE算法求解高维复杂优化问题的可行性。(3)在全基因组关联性研究中,两个SNP组合位点是非常常见和重要的致病组合。然而,由于SNP位点的组合数量巨大和致病模型丰富多样,使得现有很多算法在进行致病位点探测时,存在运算代价大和致病模型识别准确率低的缺点。为此,提出了一种快速的两位点探测算法(FHSA-SED),采用两个互补的轻量级评分标准(基于贝叶斯网络的K2-Score和Gini-Score)评价SNP组合位点与疾病状态的关联性;利用和声搜索算法进行全局搜素,将评分较高的SNP组合位点存放在候选集中,最后利用改进的G-test方法对候选SNP组合位点进行检验和确认。12个有边际效应(Disease with Marginal Effect,DME)与 70 个无边际效应(Disease with No Marginal Effect,DNME)的仿真数据实验和1个真实的老年性黄斑变性(age-related macular degeneration:AMD)数据实验表明,FHSA-SED算法在进行两个SNP致病位点探测时,具有搜索速度快,识别能力强和准确率高等特点。(4)为了能够快速准确地进行多SNP联合致病组合位点探测,提出了一种基于小生境策略的和声搜索算法(NHSA-DHSC)。通过提出小生境识别技术辅助HS算法,探测不同类型的SNP致病组合模型并防止HS算法陷入局部搜索;通过运用SNP组合位点的联合熵作为和声搜索的启发式因子,快速识别边际效应低的致病SNP组合位点;K2-Score和Gini-Score用于识别多样的致病组合模型;改进的G-test方法用于检验最终结果的真伪性。实验采用12个有边际效应的DME仿真数据集,8个高阶无边际效应的DNME仿真数据集和1个真实的AMD数据测试NHSA-DHSC算法的致病位点探测性能,结果表明,该算法能够快速准确的识别DME致病位点,可以快速识别一些无边际效应的多SNP联合致病组合位点,并且能够从AMD数据中快速发现已知的致病SNP位点。
【图文】：

图１．邋１两个ＤＮＡ序列的单位点多态性（Ｃ／Ａ多态）逡逑在人类基因组上，平均每５００？１０００个碱基对中就有１个ＳＮＰ位点，其总的ＳＮＰ逡逑数量超过了邋３００万个。大部分ＳＮＰ不会对人的健康或表型产生影响，但是，，有些ＳＮＰ逡逑变异位点往往和人类的健康或外在表型特征有直接的关联关系，特别是多个ＳＮＰ变逡逑

图１．２论文组织结构图逡逑
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18;R-05


本文编号：2603022