序列比对是生物信息研究的基础和前提。进行序列比对的目的之一是让人们能够判断序列之间是否具有足够的相似性,判定序列之间是否具有同源性,进而为蛋白质结构和功能预测、系统进化树的建立、基因病的治疗、新药物设计等许多生物研究提供了宝贵的信息。序列比对算法的研究已经成为生物信息学中的热点研究课题,特别是多序列比对。现在大多数序列比对软件以动态规划算法作为其空位插入的核心算法。然而,一个普遍的问题是目前常用的大部分序列比对算法虽比对结果越来越优,但却均由于计算复杂度所导致的计算速度缓慢这一瓶颈而在应用上受到限制。虽然近年来由于算法自身的不断改进以及计算机科学的发展,从而使现在应用广泛的序列比对程序如CLUSTALX获得了相对满意的计算效率,随着各种基因组测序计划陆续完成,大量序列数据急剧增长,以序列比对为核心的数据分析任务对于高效率的多序列比对算法的需求日益迫切。本文是在MICHSEL S. WATERMAN提出的基于欧拉路径的DNA多序列比对算法的基础上,通过对该算法的分析,找出该算法中存在的一些问题,对该算法作了进一步的探索,并通过程序实现来进一步检验该算法的运行速度及比对结果得分函数的高低。该算法是一种新颖的算法思想,运行速度快,比对结果好。这种算法与渐进算法中的CLUSTALX的最大不同是把导入的DNA序列片段构建成一个有向图,然后按照图形的一定转换规则,得到我们需要的一个有向无循环图,从图中根据边的多样性得到一条公共序列,通过这个公共序列与所有输入的序列进行两两比对,最终求得多序列比对结果。本文从程序实现的角度对该算法进行了研究,对该算法一些地方进行了改进,通过不同的得分函数对比对结果的计算,可以看出我们的比对结果有一定的改进,并与不同的多序列比对算法进行了比较。