多任务高阶SNP上位检测方法、系统、存储介质、设备

摘要

本发明属于单核苷酸多态性上位检测技术领域，公开了一种多任务高阶SNP(single nucleotide polymorphism)上位检测方法、系统、存储介质、设备，所述多任务高阶SNP上位检测方法利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换位二进制格式文件整理成样本矩阵；根据数据中SNP位点和样本量的大小，设置搜索算法参数；将SNP样本数据读入，开始准备第一阶段搜索；利用多任务、多和声记忆库和声搜索(harmony Search，HS)算法进行高阶SNP上位组合检测。本发明提出一种多任务和声搜索检测方法，采用多个和声记忆库，分别存放不同阶的SNP组合，多任务技术的运用，可以同时进行多个不同阶数的高阶SNP上位探测，促进种群内个体之间的相互学习，增强种群的多样性，进而提升全局搜索能力。

说明书

技术领域

本发明属于单核苷酸多态性上位检测技术领域，尤其涉及一种多任务高阶SNP上位检测方法、系统、存储介质、设备。

背景技术

目前：单核苷酸多态(Single Nucleotide Polymorphism，SNP)是指在基因组水平上单个碱基位点变异引起的多态性，可能是单个碱基的转换(transition)或颠换(transversion)，也可能是由于碱基的插入或缺失所致。在序列1中的一个碱基对C-G在序列2中表现为A-T，该位点就被称为1个SNP位点。在人类全基因组上，这样的SNP位点超过300万个，通常情况下，绝大部分SNP不会给人类的健康带来威胁，但是，有些SNP变异位点与人类的健康密切关联。上位效应(epistatic effect)：表示一个基因或SNP之间的相互作用，传统定义为一个位点上的等位基因掩盖了另一个等位基因表型的表达。对于多个SNP之间的上位效应是指多个SNP联合作用于表型的表达，对于复杂疾病来说，可能是受到多个SNP联合作用的影响，如果某个人在这几个位点上同时出现了SNP变异，其得病的概率会明显升高。k阶SNP上位(表示为k-order SNP上位组合)是由k个SNP联合作用于表型(或疾病状态)的上位组合。对于k>2的多任务高阶SNP上位检测是非常复杂的“SNP组合爆炸”问题，计算量巨大，现有计算机无法在有效时间内完成全基因组的上位组合检测。目前，虽然已经提出大量方法用于多任务高阶SNP上位检测，如穷举法、并行计算法、蒙特卡洛方法等，但依然存在搜索代价大，检测能力低下的问题。

现有的多任务高阶SNP上位检测技术基本都是一次只能完成某一阶数(如3阶)的SNP上位检测。需要通过多次试探性运行，才能完成不同阶数(2阶，3阶，…，k阶)的SNP上位检测。运行代价很大。

现有技术通过单个SNP与疾病状态进行关联性分析，已经发现了很多易感基因，然而，其对复杂疾病的解释性并不是很好。因此，生物界普遍认为“高阶SNP上位组合是可能形成复杂疾病的重要原因”，但是，由于高阶SNP组合的数量极大，是非常复杂的“组合爆炸问题”，现有计算机难以检测所有可能的SNP组合，这成为现有技术遇到的最重大挑战之一。另外，精准鉴别高阶SNP组合是否具有上位效应也是一个重要且复杂的研究课题，现有方法往往存在对SNP上位模型的偏好性，难以适用于所有上位模型的判断。

目前，针对高阶SNP上位的检测方法，主要有两个难题需要克服：从高维的搜索空间中，搜索出可能致病的SNP上位组合，这是一个“组合爆炸问题”，另外，由于对复杂疾病的致病机理未知，可能的SNP上位模型多种多样，如何能够正确鉴别致病的高阶SNP组合，也是一个巨大挑战。

现有技术从“搜索”的角度可以分为以下几种：

1.Exhaustive Search(穷举搜索)；通过枚举所有k-order(k个SNP的组合)SNP，采用某一方法对其进行关联性评价。优点是不会漏判某一可能的致病SNP组合，缺点是计算量极大，当k>3时，无法在有效时间内完成计算。

2.Stochastic search(随机搜索)；采用随机抽样的思想在解空间进行搜索，能够大幅降低计算量，但成功率较低，偏好于具有边际效应的SNP上位组合。

3.Machine learning-based methods(基于机器学习的方法)；基于机器学习的方法(如随机森林，支持向量机等)采用特征选择的思想从高维的SNP集合中去除对提升分类性能无效的SNP位点。缺点是该方法计算量很大，面对“小样本，高维度”的数据，分类准确率往往很低。

4.Stepwise search(逐步搜索法)；该方法采用统计方法筛选出具有边际效应的SNP集合，然后，利用该集合中的SNP位点，从中发现高阶SNP上位组合。该方法优点是：计算量小，搜索速度快。缺点是：难以发现无边际效应(或具有低边际效应)的高阶SNP上位组合。

5.基于群智能优化的搜索技术；基于群智能优化的搜索技术是利用群体中个体自身携带的信息进行相互学习和交流，可以明显提升搜索效率。但是，如何保证能够获得全局最优解，并且不会对高阶SNP上位模型具有偏好性是该方法当前面临的重要难题。

6.单任务搜索检测技术；现有的检测技术基本都是一次只能完成某一阶数(如3阶)的SNP上位检测。需要通过多次试探性运行，才能完成不同阶数(2阶，3阶，…，k阶)的SNP上位检测。运行代价很大。

从判断SNP组合与疾病状态的关联性(评价方法)角度，可以分为以下几种：

(1)统计检验方法(Statistictestmethod)。统计检验方法基于假设检验理论，根据疾病(Case)样本和正常(Control)样本中SNP组合对应基因型的分布进行差异显著性分析，筛选出Case和Control样本中该SNP组合的基因型分布具有显著性差异的SNP组合。

(2)互信息(MutualInformation，MI)。利用信息论的思想，分析SNP组合对应的基因型与疾病状态的交互信息量，实现对SNP组合的基因型与疾病状态的关联性分析。

(3)机器学习(MachineLearning，ML)。利用机器学习的思想，对指定SNP组合对应的样本数据进行训练和测试，进而评价该SNP组合对Case和Control样本的分类准确率。

(4)基于贝叶斯网络的评价方法(Bayesian network-based method)。贝叶斯网络是一个两层概率图形模型，其中一层由一组SNP节点组成，另一层由一个疾病节点组成。它们的条件依赖关系表示为有向无环图中的一组边。

上述评价需要进行多重检验；互信息和贝叶斯网络评价法都是轻量级评价方法，但存在对模型的偏好性。机器学习的优点是可以评价和比较任意阶数的SNP组合，但是，对于高阶SNP组合，识别准确率很低，并且计算量很大。现有对高阶SNP上位组合的检测方法主要存在以下不足：(1)过于依赖SNP上位(致病)模型，导致检测方法存在对某些仿真模型的偏好性，难以适用于未知模型的检测。尤其是面对真实的复杂疾病数据集时，难以给出有效的检测方法。(2)统计检验方法使用的P-value阈值由人为确定，导致检测结果的灵敏度不高。(3)现有的群智能搜索算法大都采用单一或具有相似功能的关联性评价函数，导致搜索结果不够准确，会漏掉真正致病的SNP上位组合。(4)对于存在的多个致病SNP组合的数据，检测能力较低。

现有技术虽然在高阶SNP上位组合检测中展现出了一定的效果，但总体还存在以下不足之处：

(1)检测方法计算复杂度很大，或容易漏掉真实的SNP上位组合。

(2)检测结果的灵敏度不高，通用性很低。

(3)检测方法存在对SNP上位模型的偏好性，检测算法的成功率不够高；所采用的单任务检测方法，对于未知疾病需要重复多次试探，造成计算量很大，并且不利于启发式搜索。

通过上述分析，现有技术存在的问题及缺陷为：

(1)现有检测方法计算复杂度很大，或容易漏掉真实的SNP上位组合。

(2)现有检测方法的检测结果的灵敏度不高，通用性很低。

(3)现有检测方法存在对SNP上位模型的偏好性，检测算法的成功率不够高；采用的单任务检测方法，对于未知疾病需要重复多次试探，造成计算量很大，并且不利于启发式搜索。

解决以上问题及缺陷的难度为：

(1)人类全基因组位点数量巨大，其组合的数量是更是指数级别增长，现有计算机和方法不能在有限时间内进行k-order(k阶，k>2)SNP组合的关联性检测，没有一种有效的方法可以快速发现可能存在的k-order SNP上位组合。

(2)SNP上位效应模型丰富多样，如主效应+交互模型，无主效应+交互模型等，单一方法不能正确识别所有的SNP上位模型,存在对上位效应模型的偏好性。

解决以上问题及缺陷的意义为：解决以上问题可为生物学家进行复杂疾病的致病原因提供有效的分析方法，可以快速找出可能的致病基因，进而采取有效措施进行诊断和靶向治疗。

本发明采用多任务+和声搜索策略，具有如下意义：

(1)和声搜索策略是一种基于群体智能的搜索方法，可以在多项式时间内完成搜索，并且具有很强的全局搜索能力。本发明采用和声搜索策略旨在提升搜索速度。

(2)多任务方法：可以同时进行多个不同阶数的高阶SNP上位组合的搜索，并且多个任务之间可以相互交流，能够相互促进，提升搜索能力。从而大幅提升任务的并行搜索速度。

(3)多任务采用多个关联性评价函数：可以提升对多样性的SNP上位模型的识别能力。

发明内容

针对现有技术存在的问题，本发明提供了一种多任务高阶SNP上位检测方法、系统、存储介质、设备。

本发明是这样实现的，一种多任务高阶SNP上位检测方法，所述多任务高阶SNP上位检测方法包括：

利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换位二进制格式文件整理成样本矩阵；

根据数据中SNP位点和样本量的大小，设置搜索算法参数；

将SNP样本数据读入，开始准备第一阶段搜索；

利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

进一步，所述利用Plink软件从VCF文件中读取出PED，MAP格式数据，进一步转换位二进制格式文件FAM，BED，BIM整理成样本矩阵。

进一步，所述根据数据中SNP位点和样本量的大小，设置和声搜索算法参数.有最大进化代数MaxT，和声记忆库大小HMS，和声记忆库考虑概率HMCR，局部微调概率PAR。

进一步，所述多任务高阶SNP上位检测方法的和声搜索算法是元启发式搜索算法，对于多任务高阶SNP上位检测问题，表示为如下组合优化问题：

其中X表示k个SNP的组合，该优化问题的目标是从基因组中找出与疾病状态Y具有最强关联性的SNP上位组合X

进一步，所述多任务高阶SNP上位检测方法采用的的多任务和声搜索算法的目标是从基因组中发现多个不同阶数的SNP上位组合，数学模型表示为：

其中，X

进一步，所述多任务高阶SNP上位检测方法每个任务对应一个独立的和声记忆库HM，分别采用各自的选择机制进行优胜劣汰；在搜索过程中，每次迭代，为每一个任务生成一个新个体；新个体的产生通过两种方式生成：群内学习生成，群体间组合交叉学习生成；多任务和声搜索方法的每个任务采用相同类型的关联性评价函数，分别采用不同类型的关联性评价函数，甚至每个和声记忆库中的个体进行多个不同类型的评价函数；采用的编码机制：多个任务采用了统一的编码，当阶数不同时，采用从左到右的选取策略。

本发明的另一目的在于提供一种计算机设备，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行如下步骤：

利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换位二进制格式文件整理成样本矩阵；

根据数据中SNP位点和样本量的大小，设置搜索算法参数；

将SNP样本数据读入，开始准备第一阶段搜索；

利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

本发明的另一目的在于提供一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行如下步骤：

利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换二进制格式文件整理成样本矩阵；

根据数据中SNP位点和样本量的大小，设置搜索算法参数；

将SNP样本数据读入，开始准备第一阶段搜索；

利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

本发明的另一目的在于提供一种单核苷酸多态性上位检测信息数据处理终端，所述单核苷酸多态性上位检测信息数据处理终端用于实现所述的多任务高阶SNP上位检测方法。

本发明的另一目的在于提供一种实施所述多任务高阶SNP上位检测方法的多任务高阶SNP上位检测系统，所述多任务高阶SNP上位检测系统包括：

数据预处理模块，用于利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换位二进制格式文件整理成样本矩阵；

算法参数设置模块，用于根据数据中SNP位点和样本量的大小，设置和声搜索算法参数.有最大进化代数MaxT，和声记忆库大小HMS，和声记忆库考虑概率HMCR，局部微调概率PAR。

数据读取模块，用于将SNP样本数据读入，开始准备第一阶段搜索；

高阶SNP上位组合检测模块，用于利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

结合上述的所有技术方案，本发明所具备的优点及积极效果为：本发明提出一种多任务和声搜索检测方法，采用多个和声记忆库，分别存放不同阶的SNP组合，多任务技术的运用，可以促进个体之间的相互学习，增强种群的多样性，进而提升全局搜索能力。

本发明的多任务高阶SNP上位检测方法容易理解，易实现，采用多任务和声搜索策略，能够同时进行多个不同阶数的多任务高阶SNP上位检测，大幅提升了检测性能，具有检测速度快，搜索能力强的优点。每个任务采用一个和声记忆库，分别采用相同或不同类型的关联性评价函数，一方面增强了种群(和声记忆库)的多样性，另一方面，种群之间的个体相互交叉学习，可以增强全局搜索能力。多个不同类型的关联性评价函数的使用，可以增强对SNP上位模型的鉴别能力，降低了对模型的偏好性，进而提升对高阶SNP上位组合的检测能力。

本发明能够解决现有技术对多任务高阶SNP上位检测灵敏度低的问题；本发明能够解决现有技术对多任务高阶SNP上位检测的鉴别正确率低和对SNP上位模型偏好性问题；本发明能够解决现有检测技术一次只能进行一个相同阶数的SNP上位检测的问题，而本发明可以同时进行多个不同阶数的高阶SNP上位组合的检测。本发明能够利用多和声记忆库策略提升和声搜索策略的全局检测能力，降低“SNP组合爆炸问题”的计算量。

附图说明

为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图做简单的介绍，显而易见地，下面所描述的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下还可以根据这些附图获得其他的附图。

图1是本发明实施例提供的多任务高阶SNP上位检测方法流程图。

图2是本发明实施例提供的多任务高阶SNP上位检测系统的结构示意图；

图2中：1、数据预处理模块；2、算法参数设置模块；3、数据读取模块；4、高阶SNP上位组合检测模块。

图3是本发明实施例提供的多任务高阶SNP上位检测方法实现流程图。

图4是本发明实施例提供的利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测流程图。

图5是本发明实施例提供的生成和声的基本规则示意图。

图6(a)是本发明实施例提供的群内生成新个体组合交叉和单位点互换示意图。

图6(b)是本发明实施例提供的群内生成新个体单位点变异示意图。

图7是本发明实施例提供的任务间(内)交叉学习示意图。

图8是本发明实施例提供的个体在任务之间迁移学习示意图。

图9是本发明实施例提供的产生新个体的基本流程图。

图10是本发明实施例提供的检测能力比较图。

图11是本发明实施例提供的算法检测用时比较图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

针对现有技术存在的问题，本发明提供了一种多任务高阶SNP上位检测方法、系统、存储介质、设备，下面结合附图对本发明作详细的描述。

如图1所示，本发明提供的多任务高阶SNP上位检测方法包括以下步骤：

S101：利用Plink软件从VCF文件中读取出PED，MAP格式数据，转换位二进制格式文件(FAM，BED，BIM)整理成样本矩阵；

S102：根据数据中SNP位点和样本量的大小，设置和声搜索算法参数.有最大进化代数MaxT，和声记忆库大小HMS，和声记忆库考虑概率HMCR，局部微调概率PAR；

S103：将SNP样本数据读入，开始准备第一阶段搜索；

S104：利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

本发明提供的多任务高阶SNP上位检测方法业内的普通技术人员还可以采用其他的步骤实施，图1的本发明提供的多任务高阶SNP上位检测方法仅仅是一个具体实施例而已。

如图2所示，本发明提供的多任务高阶SNP上位检测系统包括：

数据预处理模块1，用于利用Plink软件从VCF文件中读取出PED，MAP格式数据，进一步转换位二进制格式文件(FAM，BED，BIM)整理成样本矩阵；

算法参数设置模块2，用于根据数据中SNP位点和样本量的大小，设置和声搜索算法参数.有最大进化代数MaxT，和声记忆库大小HMS，和声记忆库考虑概率HMCR，局部微调概率PAR。

数据读取模块3，用于将SNP样本数据读入，开始准备第一阶段搜索。

高阶SNP上位组合检测模块4，用于利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测。

下面结合附图对本发明的技术方案作进一步的描述。

SNP:单核苷酸多态性(Single nucleotide polymorphism)。

高阶SNP上位(high-order SNP epistasis)：多个SNP位点联合作用于表型或疾病状态。

多任务(multi-task)：同时进行多个不同阶数的多任务高阶SNP上位检测。

多记忆库(multiple harmony memory)和声搜索策略：具有多个和声记忆库的和声搜索算法(HarmonySearchalgorithm)。

单任务优化是指每次集中完成一项优化任务，该任务可以是单目标优化问题，也可以是多目标优化问题。

多任务(multi-task)优化是一种新型的优化技术，能够利用多个不同任务之间的潜在关联性，彼此影响，相互作用，相互学习，从而快速实现多个优化任务。多任务优化可以同时解决多个单目标优化问题，也可以同时解决多个多目标优化问题。

本发明采用多任务优化技术进行多个多任务高阶SNP上位检测。

和声搜索算法是元启发式搜索算法，通过模拟音乐家们进行和声创造的过程，旨在发现一组最优的音符组合，演奏出最优美的和声。和声搜索具有很强的全局搜索能力，非常适合于组合优化问题求解。对于多任务高阶SNP上位检测问题，可以表示为如下组合优化问题：

其中X表示k个SNP的组合，该优化问题的目标是从基因组中找出与疾病状态Y具有最强关联性的SNP上位组合X

本发明所采用的的多任务和声搜索算法的目标是从基因组中发现多个不同阶数的SNP上位组合。数学模型可以表示为：

其中，X

本发明采用一种多任务、多和声记忆库的和声搜索算法，该方法能够同时进行多个优化问题的求解。其中，每个任务对应一个独立的和声记忆库(Harmony memory，HM)，分别采用各自的选择机制进行优胜劣汰。在搜索过程中，每次迭代，会为每一个任务生成一个新个体。新个体的产生主要通过两种方式生成：群内学习生成(包括群内交叉，单点互换，单点变异等)，群体间组合交叉学习生成。本发明的多任务和声搜索方法的每个任务可以采用相同类型(如贝叶斯网络法，统计检验法等)的关联性评价函数，也可以分别采用不同类型的关联性评价函数，甚至每个和声记忆库中的个体进行多个不同类型的评价函数(类似于多目标优化)。本发明从搜索策略上采用了新型的框架技术，搜索效率有了明显提升。多个任务同时进行，有助于提升搜索性能，特别是对应无边际效应的致病模型，通过多任务搜索机制，可以发现一些低阶的边际组合效应，进而促进发现更高阶的SNP上位组合。本发明所采用的编码机制：多个任务采用了统一的编码，但是，当阶数不同时，采用从左到右的选取策略，例如：在3-order的任务中，其中一个解向量X＝(2，6，9，14，49)，只需要选取SNP位点组合(2，6，9)进行关联性评价。该编码机制中，尽管SNP位点14和49可以用于和其它任务进行交叉学习，在本任务中，还可以与前面的SNP位点进行单位点互换，从而促进该任务种群中个体的优化。

如图3所示，本发明提供的多任务高阶SNP上位检测方法具体包括以下步骤：

(1)数据预处理

利用Plink软件从VCF文件中读取出PED，MAP格式数据，进一步转换位二进制格式文件(FAM，BED，BIM)整理成样本矩阵。

(2)算法参数设置

根据数据中SNP位点和样本量的大小，设置和声搜索算法参数.有最大进化代数MaxT，和声记忆库大小HMS，和声记忆库考虑概率HMCR，局部微调概率PAR等。

(3)数据读取。将SNP样本数据读入，开始准备第一阶段搜索。

(4)利用多任务、多和声记忆库和声搜索算法进行高阶SNP上位组合检测(算法流程如图3所示)。

本发明对初始和声进行关联性评价：

(伪代码1.1)每一个和声(个体)采用单个评价函数进行关联性评价)

下列代码的作用是：对K-1个任务(2,3，…,K)种群(种群大小为NP)中的个体进行关联性评价。

(伪代码1.1)每个个体会计算得到M＝K-1个适应值。

本发明对初始和声进行关联性评价：每一个和声(个体)需要采用3个评价函数进行评价)

下列代码的作用是：对K-1个任务(2,3，…,K)种群(种群大小为NP)中的个体进行分别采用关联性评价函数f

每个个体会计算得到K*3个适应值(多个评价指标)

伪代码2(任务划分)

本发明的任务划分：对所有个体进行任务划分

本发明产生新个体

每个个体会计算得到K个适应值

GenerateNewHarmonyInPop(k).//在任务k的群体中产生一个新个体

根据图5的基本规则产生新个体

伪代码3：本发明和声记忆库规则生成新个体

群内产生新个体，如图6(a)、图6(b)、图7-图9。群间交叉学习。

本发明在5个仿真数据集的测试结果比较(见表1，表2，表3，图10，图11)

表1.仿真数据集参数

表2.检测能力比较

表3.平均检测用时比较(单位：秒)

应当注意，本发明的实施方式可以通过硬件、软件或者软件和硬件的结合来实现。硬件部分可以利用专用逻辑来实现；软件部分可以存储在存储器中，由适当的指令执行系统，例如微处理器或者专用设计硬件来执行。本领域的普通技术人员可以理解上述的设备和方法可以使用计算机可执行指令和/或包含在处理器控制代码中来实现，例如在诸如磁盘、CD或DVD-ROM的载体介质、诸如只读存储器(固件)的可编程的存储器或者诸如光学或电子信号载体的数据载体上提供了这样的代码。本发明的设备及其模块可以由诸如超大规模集成电路或门阵列、诸如逻辑芯片、晶体管等的半导体、或者诸如现场可编程门阵列、可编程逻辑设备等的可编程硬件设备的硬件电路实现，也可以用由各种类型的处理器执行的软件实现，也可以由上述硬件电路和软件的结合例如固件来实现。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，都应涵盖在本发明的保护范围之内。