基于群智能和冲突规避策略的基因—基因交互作用检测及其并行计算

论文摘要

生物信息学是生命科学与信息科学交叉形成的一门新兴学科,目的是高效地挖掘生物实验数据中所包含的生物学意义。基因-基因交互作用研究是生物信息学中基因组分析的重要课题,对于研究复杂疾病的病因有着重要的意义。当前基因-基因交互作用的研究热点是在全基因组中进行交互作用检测,主要挑战有二个,一是在全基因组数据上的交互作用检测会遇到密集计算的负担,二是对交互作用的检测会受到边际作用的影响。单核苷酸多态（single nucleotide polymorphism,SNP）,作为一种遗传标记,由于其广泛存在于基因组中,并且容易测定,常被用作基因关联研究的研究对象。针对当前基因-基因关联研究中已有算法的一些缺陷,提出了二种解决该问题的思路,一是在算法方面进行研究,提出更有效和快速的算法,二是对原有算法进行并行化改进,利用并行计算平台对算法进行加速。按照这二种思路,主要在二个方面进行了创新。一是提出了一个基于群智能和冲突规避策略的基因-基因交互作用检测算法。首先对该领域的二种随机算法——蚁群优化算法和SNPHarvester算法进行了改进,克服了二种算法的缺陷,然后将二种改进算法结合起来,并使用冲突规避策略合理分配搜索资源,得到了一种可应用于全基因组的、不受边际作用影响的基因-基因交互作用检测算法。算法以SNP为研究对象,从大量SNP中选出具有显著交互作用的SNP组。算法初始化多个SNP组作为初值,同时产生多条搜索路径,通过局部极值搜索保护高阶交互作用。蚂蚁之间使用概率密度进行通信。通过使用冲突规避策略,减少了路径的交叉和重叠,使得到的解能更广泛地反映基因-基因交互作用在基因组范围内分布的情况。在仿真数据和真实数据上的实验证实,算法在统计能力上可以和SNPHarvester算法相比,在效率上有明显优势,得到的结果能够广泛地代表基因-基因交互作用在基因组的分布。二是提出了一个基于Java平台的并行化算法。并行算法主要面向个人计算机的硬件环境,充分利用多核处理器,开辟多个线程,对原算法进行了有效的并行加速。并行程序与原程序的比较结果验证了算法具有很好的可扩展性,可以向GPU（图形加速器）、集群计算机和超级计算机平台上的移植,也显示了Java在开发生物数据处理并行程序方面的巨大潜力。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 生物信息学的新进展
• 1.1.2 基因-基因交互作用检测的相关背景
• 1.1.3 并行计算应用于基因-基因交互作用检测
• 1.2 研究现状
• 1.2.1 基因-基因交互作用检测中存在的主要问题
• 1.2.2 主要算法分析
• 1.3 研究内容和研究成果
• 1.3.1 基于群智能和冲突规避策略的基因-基因交互作用检测算法
• 1.3.2 基于Java平台的并行算法
• 1.3.3 算法的实验验证
• 1.4 篇章结构
• 第二章 基因-基因交互作用的含义及其检验方法
• 2.1 引言
• 2.2 基因-基因交互作用的含义
• 2.2.1 基因-基因交互作用的统计学含义
• 2.2.2 基因-基因交互作用的生物学含义
• 2.3 基因-基因交互作用的检验方法
• 2.3.1 病例对照研究应用于基因-基因交互作用的检验
• 2.3.2 基因-基因交互作用检测中的多检验问题
• 2.4 小结
• 第三章 基于群智能和冲突规避策略的基因-基因交互作用检测算法
• 3.1 引言
• 3.2 改进的蚁群优化算法
• 3.2.1 蚁群优化算法
• 3.2.2 对原始蚁群优化算法的改进
• 3.3 改进的SNPHarvester算法
• 3.3.1 SNPHarvester算法
• 3.3.2 对SNPHarvester算法的改进
• 3.4 基于群智能和冲突规避策略的基因-基因交互作用检测算法
• 3.4.1 冲突规避策略
• 3.4.2 算法描述
• 3.5 小结
• 第四章 基于Java平台的并行计算
• 4.1 引言
• 4.2 Java多线程技术
• 4.2.1 Java的特点
• 4.2.2 Java多线程的优势
• 4.2.3 Java线程的状态
• 4.2.4 Java线程的创建
• 4.2.5 Java中多线程的互斥与同步
• 4.3 基于群智能和冲突规避策略的基因-基因交互作用的并行检测算法
• 4.3.1 原算法中潜在的并行性
• 4.3.2 并行检测算法
• 4.3.3 并行检测算法的实现
• 4.4 小结
• 第五章 实验验证与测试
• 5.1 引言
• 5.2 实验数据
• 5.2.1 仿真数据
• 5.2.2 真实数据
• 5.3 原算法的实验验证
• 5.3.1 参数设置
• 5.3.2 运行环境
• 5.3.3 基于仿真数据的实验验证
• 5.3.4 基于真实数据的实验验证
• 5.4 并行程序的实验验证
• 5.4.1 参数设置
• 5.4.2 运行环境
• 5.4.3 基于仿真数据的实验验证
• 5.4.4 基于真实数据的实验验证
• 5.5 小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果