基于低差异序列的搜索算法及其在SNP关联分析中的应用

摘要

单核苷酸多态性(single nucleotide polymorphism，SNP)，主要是指在基因组水平上由单个核苷酸的变异所引起的DNA序列多态性。它数量多、分布广，而且被认为是不同个体在复杂性状以及常见疾病的易感性上产生差异的重要因素。最近的研究中还发现，多个SNP位点的联合对表型所做的影响，可能会远大于单个SNP各自对表形所做的影响，这一作用被称为上位作用。因此，研究上位作用的检测对于SNP与疾病的关联分析工作具有重大意义。目前SNP数据具有高维度和低样本量的特点，多位点联合使搜索空间变得更大，上位作用检测仍然是一个富有挑战性且未解决的问题。
　　本文致力于上位作用检测工作中搜索算法的研究。通过研究多位点联合的搜索空间的性质和传统启发式搜索算法的原理和特点，结合低差异序列的几何分布特性，提出将低差异序列应用于搜索算法的思想。本文研究了低差异序列在搜索算法中的应用，并提出了一种新的基于低差异序列的搜索算法用于解决SNP关联分析问题，并在模拟数据集和真实数据集上对该算法以及其它两种算法进行实验，对结果进行了分析与评价。实验结果表明，与其它算法相比该算法在上位作用检测中更具优势，说明了该算法在启发信息比较少的搜索空间中具有比常规搜索算法更好的表现。