摘要
COVID-19冠状病毒是2019年开始在全球范围内传播的一种大规模传染性呼吸道疾病。COVID-19不仅对我们的生活、日常习惯和医疗保健系统产生了普遍有害的影响，而且还会让我们因为感染而导致死亡。无论何时，要对一个新病毒进行研究，都得提取其基因，然后在数据库搜索是否有同源基因的存在。由于基因测序技术的发展，字符串匹配算法作为一种传统的算法受到了巨大的挑战。研究表明，基因测序过程中会出现大量的短读片段，所以对字符串匹配算法的效率和时间提出了更高的要求。 模式精确匹配与近似比对算法是基因测序中很关键的两个组成部分。目前流行的BLAST(Basic Local Alignment Search Tool)是一种近似比对算法，但是要寻找病毒生物特定的表达基因时，需要精确匹配具体的模式串。为了使模式匹配能够适应大量甚至是爆炸性的基因序列数据，需要找到一种高效稳定的算法。 多模式匹配WM(Wu-Manber)算法在多模式精确匹配上有很好的效果，本文基于MPI(Message Passing Interface)的多模式串匹配WM算法的应用研究，主要是结合基因序列的特点提出了一种基于N-gram模型的预处理方法，并且在匹配过程中使用布隆过滤器减少匹配次数。利用MPI的非阻塞通信技术，使得匹配计算与通信时间较大程度重叠。主要过程是主进程对文本进行N-gram处理并且对模式串生成WM算法所需要的数据结构，然后将这些数据结构和文本任务分段发送给从进程，从进程接收处理后的任务文本和WM算法需要的数据结构，可以进行匹配任务。主进程在分配任务之后，等待时间也可以同时进行匹配，各进程匹配完成后可以直接输出匹配结果。 实验部分分为五个部分，第一个是对于不同进程数对并行算法的影响；第二个是基因序列文本任务分块对于算法的影响；第三个是基因文本的大小对算法的影响；第四个是模式串的最短长度对算法的影响；第五个是与常规WM算法和AC(Aho-Corasick)算法的对比实验。 实验结果表明：进程数并不是越多越好，在选择12个进程，即机器多核数目的2倍时，效率最高。在任务分块执行时，分2块执行效率最高，因为这样可以最大程度的利用MPI的非阻塞通信的优点。而且在基因序列文本长度变化较大时，该算法的速度比常规WM算法和AC算法都表现得更好。而且对于WM算法受模式串集合中的最短长度的干扰导致效率低下的问题，在基因序列中也因为基因序列的长度一般都较长而避免，所以该算法的表现也明显更加优秀，最佳能达到31倍的加速效果。
NETL