本文首先讨论双序列比对和多序列比对的定义，介绍多序列比对的四种常用模型，分析其优缺点；然后分析和比较多序列比对的各类算法(精确算法、近似算法、启发式算法和并行算法等)；最后给出需要解决的研究问题。在充分调研了序列比对问题的基础上，本文围绕着放松限制条件的序列比对、多序列比对的并行近似算法和序列比对的并行模型等三个问题开展了研究。 本文主要内容：放松限制条件的序列比对；提出了一个时间复杂度为O((α+1)n2(α+1))的放松限制条件的双序列比对问题的完全算法；提出了一个时间复杂度为O(k2(α+1)2(α+1))的LCMSA的近似算法。多序列比对的并行近似算法。 序列比对的并行模型。在研究该模型已有的算法后，本文改进了已有的算法，使其在输出最优罚分的同时还能输出最优比对；对改进的双序列比对算法进行了复杂度分析，其晶格开销为O(l1l2(m+k2)，延迟时间为O(l1l2(m+k)，(l1和l2分别为两个序列的长度，罚分值用k位二进制数表示，空格计数用m位二进制数表示)。