摘要:2009年3月从墨西哥暴发的甲型H1N1流感疫情，迅速蔓延到全世界。这次流感疫情最终影响了两百多个国家，造成上万人死亡。对人类的生命与健康造成了极大的危害。两年过去了，学术界对甲型H1N1流感病毒的研究并未停止。因为流感病毒极易发生变异。而一旦变异，很可能造成新一轮世界范围的疫情。

　　　本文从使用生物信息学的手段进行甲型H1N1流感病毒变异分析研究出发，从信息处理和算法研究两个角度，围绕序列比对、进化树建立和蚁群算法并行化等问题展开研究，主要的研究内容和主要成果包括：

　　　（1）甲型H1N1流感病毒变异分析信息处理  下载了甲型H1N1流感病毒基因，对其进行了信息处理，建立了进化树。为分析当前甲型H1N1流感病毒的变异情况提供了数据，供生物专业的学者进行研究时使用。

　　　（2）改进求解多序列比对蚁群算法  研究了求解多序列比对的蚁群算法，改进了该算法，在概率公式、信息素更新策略、字符选择策略等方面提出了自己的改进策略。使得改进后的算法对于大部分序列集合可以获得更好的结果。

　　　对改进后的算法进行了并行化，在主从式模型下提出了算法的并行策略，将算法的复杂度从O(Cyclenum·N2·LEN2)降到了O(Cyclenum·(N2·LEN2/p+p))，提高了算法的执行效率。

　　　（3）提出一种并行启发式进化树搜索算法  针对基于特征的建树方法时间代价大的缺点，设计了一种并行启发式进化树搜索算法。可以大大降低进化树的搜索次数。并使用最大简约法对该算法进行了测试，对算法的三种信息素更新策略进行了比较。

　　　（4）提出两种大规模并行蚁群算法  针对大规模蚁群算法并行化时存在的问题，提出了两种并行蚁群算法。一是将竞争机制引入处理器调度，提出基于竞争的粗粒度并行蚁群算法。二是将主从式并行策略进行了发展，设计了树形结构的层次并行蚁群算法。并对两种算法进行了理论分析。

关键词：H1N1流感病毒、序列比对、进化树、蚁群算法、并行化

　　　本文考虑使用进化树分析的方法来进行甲型H1N1病毒的变异分析信息处理。建立了甲型H1N1病毒基因的进化树，辅助生物学研究人员分析H1N1病毒基因的变化关系。

　　　同时在算法研究方面，针对基因的进化树分析相关算法研究中目前存在的一些问题，我们进行了深入的研究，主要的工作包括生物序列比对和生物进化树建立，由于在序列比对算法研究时，我们主要研究基于蚁群算法的序列比对，而目前在大规模蚁群算法并行化的研究中还存在一定的问题，因此本文对蚁群算法并行化进行了进一步研究。