下一代测序技术及全基因组关联分析技术的目标是识别遗传变异、表观遗传修饰与人类复杂疾病之间关联模式,最终依据个体遗传信息开展个体化医疗。遗传疾病可分为单基因疾病及复杂疾病。单基因疾病符合孟德尔式遗传规律,单个基因上易感位点的改变导致基因功能改变从而导致疾病形成。相比之下,复杂疾病如癌症、糖尿病等是由基因上多个单核苷酸多态性(SNP)之间相互作用形成,其分子层次上的致病机理仍然是未知的。因为SNP具有数量多、分布广等特点,全基因组SNP数据已成为识别复杂疾病致病基因并解释其致病过程的重要生物标记。由于SNP之间存在连锁不平衡性,从而使得该数据中存在大量冗余。因此,基于全基因组SNP数据的复杂疾病分析通常包含两个主要过程,首先对少量样本作全基因组SNP基因分型,然后从所有SNP中选择具有代表性的特征SNP子集,以降低冗余及噪声信息,然后采集大量样本并在特征SNP位点上作基因分型,以开展关联分析识别致病基因。本文通过设计优化算法及数据挖掘技术开展复杂疾病SNP数据分析方法研究,主要包含以下四个内容:1)基于组合优化算法的信息SNP选择方法。针对信息SNP选择过程中候选子集构造及基因型重构两个阶段中存在时间复杂度高等挑战,本文利用智能优化算法及确定性算法分别设计两种信息SNP选择方法。第一种方法首先利用两位点连锁度量以及多位点连锁度量构造最大相关最小冗余(MCMR)目标函数,以同时保证信息最大化及冗余最小化,接着利用贪婪算法搜索最优解。MCMR是以连锁不平衡性为优化目标,因此选择结果可解释性强并且避免了学习模型反复重构。第二种方法出发点是设计最近均值分类算法(NMC)克服特征选择阶段样本反复重构问题,该方法直接以最近均值分类器的重构准确度为优化目标,利用蚁群算法遍历组合空间,以搜索最优信息SNP子集。虽然NMC一定程度上忽略了连锁不平衡性这一重要生物现象,但是它能兼容基因型数据以及单体型数据。实验结果表明这两种信息SNP选择策略分别适用于不同应用环境且具有一定优势。2)基于多次蚁群搜索框架(MACA)的标签SNP选择方法。与信息SNP选择的重构准确度不同,标签SNP是以单体型覆盖度为评价标准,标签SNP主要用于基于单体型的复杂疾病关联研究。本文设计一种多次蚁群算法的组合空间搜索策略,每次迭代中将位点组合为不同粒度的节点,然后分别利用蚁群算法构造最优解,其基本思想是粗粒度加速算法收敛,细粒度提高解质量。MACA利用位点组合的单体型覆盖度设计启发式因子,以提高每次蚁群算法的搜索性能。实验部分利用模拟数据集及真实数据集从不同样本数量和不同SNP数量上验证MACA在标签SNP数量及运行时间等指标上的优势。3)统一信息SNP及标签SNP的核SNP选择方法。信息SNP是从信息含量角度选择具有代表性的SNP,而标签SNP则是从单体型多样性角度选择代表性SNP,两者选择代表性SNP的角度差别大,因此在同一数据集上选择的SNP子集不尽相同,使得后续研究人员难以选择。提出一种基于层次聚类的核SNP选择方法KSHC,该方法首先利用相对熵减少概念构造聚类距离公式,然后利用层次聚类算法将相似SNP进行聚类并识别聚类中核SNP,接着设计Top k及后向删除特征选择策略分别选择核SNP以统一信息SNP及标签SNP。KSHC基本原理是以信息熵最小确保同一类簇中单体型种类最少,同时保证不同位点上等位基因频率分布差异最小,这两点分别对应标签SNP与信息SNP的特征。实验在多个数据集上利用覆盖度及重构准确度指标评价KSHC,实验结果表明核SNP能有效统一信息SNP及标签SNP。4)基于最大一致最大差异准则的致病基因识别方法(MCMD)。传统方法通常仅考察致病基因型在患病组和对照组的分布差异,而本文方法不仅保证致病基因型在患病组合对照组的频率差异最大即最大差异性,并且保证患病组的致病基因型具有稳定的模式即最大一致性。MCMD假设患病组由于患有同一种疾病,那么其理想情况下其致病模式应该完全一致即致病基因完全一样,但是由于存在异质性,因此可能存在几种致病基因型,尽管如此其致病模式具有稳定性即最大一致性。在此假设基础上,以最大一致性及最大差异性准则为易感基因型评价函数,然后利用贪婪法寻找乳腺癌的致病基因型,接着进一步利用蚁群算法在不同上位性基因组合中寻找多组高风险致病基因型以分析乳腺癌异质性。