高胜召，陈未如,2，张 雪,2，陈章昭，韩 静

（1.沈阳化工大学 计算机科学与技术学院，辽宁 沈阳 110142；2.辽宁省化工过程工业智能化技术重点实验室，辽宁 沈阳 110142）

0 引 言

新冠病毒变异株中最受关注的是Delta、Omicron、Alpha、Gamma、Beta、Lambda、Mu 变异株。以上变异株或是增加了毒性，或是增强了传播性，某些变异株还会降低疫苗效用，对公共卫生构成重大威胁[1]。因此，对于新冠病毒突变的研究至关重要。

考虑到DNA 序列的特殊性，已经有许多专门针对DNA序列挖掘的算法，如ToMMSA、ATRHunter 等[2]。机器学习也被应用到DNA 序列挖掘[3]。至今已经有许多研究人员在针对SARS-CoV-2 的研究中获得了成果。Qin 等人[4]提出了一种识别共突变模块的算法，并找到了42 个共突变模块，基于这些共突变模块，将SARS-CoV-2 种群分为43 组，并根据不一致的共突变模块的数量确定了各组之间的系统发育关系。Liu 等人[5]提出一种计算并发度的公式。Mishra 等人[6]对SARS-CoV-2 序列进行聚类分析，将突变分为3 类：共同发生的突变、前导和尾随突变、相互排斥的突变。

本文以SARS-CoV-2 为例进行生物变异结构关系挖掘，将共突变模块的挖掘与结构关系模式相结合，提出并发变异关系挖掘，并提出更加适合生物变异结构关系性质的公式，尝试从结构化的角度来挖掘出新冠病毒基因序列的变异信息，并从算法的时间复杂度与空间复杂度进行讨论。

1 结构关系模式挖掘

结构关系模式挖掘是在序列模式挖掘基础上提出的一种新的数据挖掘任务。结构关系是一种包括并发关系、互斥关系、关联关系及这些关系的复合关系的形式，用于表示序列模式之间存在的关系。……