生物信息学是在生命科学的研究中,以计算机为工具对生物信息进行储存、检索和分析的科学。其中,序列比对是生物信息学最基本的一个研究方法,如何获得比对质量更好、时间空间效率更高的序列比对算法是生物信息学研究的一个重要的课题。生物序列比对算法在生物信息学中占有重要的地位,而多序列比对又是其中比较难解决的问题。论文首先介绍了双序列比对问题的最基本方法——动态规划全局比对算法,然后学习和研究了双序列比对的空隙罚分函数,接着介绍了多序列比对问题,并对多序列比对问题的动态规划算法以及比较经典的树比对、星比对算法和现在比较流行的CLUSTALW算法,并给出判断多序列比对结果好坏的目标函数。本文提出了进行全局多序列比对的一种方法——基于图论方法的DNA多序列星比对算法。该算法将所有输入序列按照一定长度分成字符段,并将这些字符段的各种信息记录在构成de Bruijn图中,这样求取有最好匹配性的中心序列问题就转化为求de Bruijn图中按照边的权值的贪心路径问题,使多序列比对问题的时间复杂度降到线性,求得中心序列后,利用星比对算法得到最终的多序列比对结果,本文还对星比对算法进行了改进。试验结果表明基于图论方法的DNA多序列星比对算法是有效可行的,尤其是对于大量低变异率的序列数据时,同现在广泛应用的算法相比,有较快的运算速度和较好的比对结果。