面向基因测序数据的高效位点与表型关联挖掘算法

疾病表型通常会受SNP位点调控，挖掘疾病表型与SNP位点间的关联规则有助于提供个性化分子诊疗方案。由于SNP位点具有遗传异质性，在挖掘疾病表型与SNP位点间的关联规则时，需要将最小支持度阈值设为较低值，甚至是0，又由于SNP位点数据量庞大，这会使得关联规则算法时间复杂度极高。为此，提出了HEMAPS算法，通过使用线程并行处理和垂直数据格式改进Apriori算法。此外，为解决质量性状表型样本比例不平衡问题，提出了一种新的关联规则评价指标——匹配度。实验结果表明，HEMAPS算法的时间复杂度比Apriori算法明显降低。

High-Efficiency Mining Algorithm for Association Rules Between Phenotypes and SNPs

Since SNPs usually regulate disease phenotypes, association rules between disease phenotypes and SNPs can help provide personalized molecular diagnosis and treatment. In consideration of SNPs＇ ge- netic heterogeneity, we need to set the minimum support threshold for a low value or even for zero when mining association rules between disease phenotypes and SNPs. Besides, the time complexity of mining al gorithm becomes very high owing to the large number of SNPs. Therefore, HEMAPS algorithm, an improvement of Apriori, is presented in this paper. HEMAPS improves Apriori by using vertical data format and multi-thread parallel computing. In addition, this paper proposes match degree as a new evaluate index of association rules to solve the problem of sample ratio imbalance of quality traits. Experimental results show that the time complexity of HEMAPS is significantly lower than that of Apriori.