学位论文 > 优秀研究生学位论文题录展示

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

作　者: 刘天航
导　师: 殷建平
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 基因-基因交互作用单核苷酸多态群智能冲突规避策略 Java平台并行化多核处理器
分类号: TP391.41
类　型: 硕士论文
年　份: 2011年
下　载: 19次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

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

内容摘要

全文目录

相似论文