论文部分内容阅读
基因微阵列是实验分子生物学中的一个前所未有的突破,其使得研究者可以同时监测多个基因在多个实验条件下的表达水平的变化,进而为发现基因协同表达网络、研制药物、预防疾病等提供技术支持。随着基因微阵列技术的飞速进步,大量的基因表达数据和相应的挖掘结果（保序子矩阵,Order-Preserving SubMatrix,OPSM）积累下来,同时也不能方便且完全的为生物学家所利用。因此,亟待研究和设计探索与分析这些丰富数据资源的相关方法与技术。近年来,学术界提出大量的关于基因表达数据中保序子矩阵OPSM的批量挖掘的算法,且具有良好的挖掘性能。当面对海量的、含有噪声的且分布式并行环境时,已有的OPSM挖掘方法存在如下问题:（1）在分布式并行环境下,如何在减少数据通信并充分利用计算资源的情况下,保证挖掘结果的准确性与完整性;（2）如何不通过挖掘而直接从索引好的基因表达数据中检索出所需要的OPSM;（3）如何为大量积累的OPSM设计索引与查询技术,使用户获得良好的查询响应;（4）如何使用自定义约束来提高OPSM查询的相关性与响应速度。本文以基因表达数据中局部模式的挖掘、索引与查询为研究背景,针对上述问题进行了深入研究,提出了相应的适用于数据密集型计算环境的挖掘、索引与查询方法和优化技术。本文的研究工作得到了国家“973计划”课题、国家自然科学基金重点项目、西北工业大学研究生创业种子基金的支持。本文的研究内容以及创新点主要体现在如下几个方面:（1）基于蝶形网络的基因表达数据的并行分割与挖掘方法指出现有分布式并行系统存在的不易并行等问题。为了快速挖掘基因表达数据中的保序子矩阵（OPSM）,提出了基于蝶形网络的基因表达数据的并行分割与挖掘方法。其扩展了Hama BSP框架,使得节点在每个超步中只需要与指定的某个节点通信即可,且最多使用log2N个超步。实验表明,所提出方法弥补了Apache Hama系统的处理框架BSP的不足,减少了信息传递量,加速了处理速度。同时从理论上证明了该方法能保证挖掘结果的完整性。（2）基于关键词的OPSM查询关键技术研究保序子矩阵OPSM的快速检索对生物学家寻找某种生理功能模块起着重要作用,但现有大多数方法需要通过挖掘来实现。为了跳过挖掘而直接通过索引数据来检索OPSM,提出了带有行列表头的前缀树索引方法、基于行/列关键词的精确/模糊查询技术以及多类型OPSM查询方法。通过大量实验证明了该方法的有效性与可扩展性。（3）OMEGA:OPSM并行挖掘、索引与搜索工具的设计与实现设计和实现了基于蝶形网络和带有行列表头的前缀树索引的OPSM并行挖掘、索引与检索系统。（4）OPSM的约束查询关键技术研究为了提升OPSM查询的相关性,提出了基于枚举序列与多维索引的两种查询方法。其利用自定义约束从提出的两种索引中搜索相关结果。在真实数据集上的实验结果表明:与蛮力搜索方法相比,基于枚举序列与多维索引的两种查询方法能够更准确有效地检索OPSM。为了进一步减少索引的大小,提出了基于数字签名与Trie的OPSM索引与查询方法。实验结果证明了查询方法的有效性与准确性。