多序列比对是生物信息学中至关重要的一步。传统的序列比对的方法是NP难问题。目前的算法都是以牺牲某种程度的精度为代价,达到可实用的速度。由于现有的蛋白质多序列比对算法难以兼顾速度和精度,因而在基于氨基酸多序列比对算法的蛋白质进化演化研究中,也不可避免的存在着计算量大和难以保证准确性的缺点。另外,每一种多序列比对算法都有自己的优缺点。那么,只有了解了这些算法的优缺点,才能针对不同的数据选用不同的算法。这样,对于蛋白质多序列比对算法的性能评估就显得尤为重要。对于蛋白质多序列比对算法优劣的评价方法,目前有很多种。但是,在蛋白质序列比对过程中会有噪声影响,还有人为因素的影响;由于这些原因,很难对每一个算法进行公正的评价。基于这个原因本文提出了置换距离的方法对蛋白质多序列比对算法进行评估,由于置换距离算法只关心蛋白质之间进化距离的相对次序而不考虑它们之间的细微差异,因此它能够克服噪声影响,具有更强的鲁棒性,从而对序列比对算法进行更加准确的评价。对于置换距离的度量本文用最长公共子序方法,它能够更快,更准确的反映出不同置换之间的差异性。上面说到现有的蛋白质多序列比对算法计算速度慢,难以达到用户的需求,因此本文提出了基于相对熵的蛋白质多序列比对算法。一般的多序列比对算法运行速度都很慢,这是由于它们都必须进行漫长的氨基酸序列比对过程;而本文提出的相对熵算法却避免了这一过程,直接对蛋白质序列进行分析,这样就大大提高了计算的速度。另外,用相对熵算法得到的结果与其它多序列比对算法得到的结果大体一致。可见,相对熵多序列比对算法无论在计算速度还是在计算精度上都可以很好的满足人们的要求。基于以上算法,本文首先用置换距离法对Dialign,Tcoffee,ClustalW等多序列比对算法进行评估,将评估结果与其它评估算法结果进行比较,以验证置换距离法的可行性。然后,用上面验证的置换距离法对本文提出的相对熵算法进行评价,从而证明了相对熵算法可行性及其在时间上的优势。