中山大学学报自然科学版 ›› 2011, Vol. 50 ›› Issue (2): 87-92.

• 研究论文 • 上一篇    下一篇

基于置换距离度量的蛋白质多序列比对算法性能评估

高 峰1, 李防震1, 王 珺2,董骝焕2   

  1. (1山东经济学院计算机科学与技术学院∥山东省数字媒体技术重点实验室,山东 济南 250014;2中国科学院马普学会计算生物学伙伴研究所,上海 200031)
  • 收稿日期:2010-04-14 修回日期:1900-01-01 出版日期:2011-03-25 发布日期:2011-03-25
  • 通讯作者: 李防震;董骝焕

Performance Assessment of Protein Multiple Sequence Alignment Algorithms Based on Permutation Distance Measurement

GAO Feng1, LI Fangzhen1, WANG Jun2, DONG Liuhuan2   

  1. (1School of Computer Science and Technology∥Shandong Provincial Key Laboratory of Digital Media Technology, Shandong Economic University,Jinan 250014, China;2CASMPG Partner Institute for Computational Biology, CAS at Shanghai, Shanghai 200031, China)
  • Received:2010-04-14 Revised:1900-01-01 Online:2011-03-25 Published:2011-03-25

摘要: 蛋白质多序列比对是一种重要的生物信息学工具,在生物的进化分析以及蛋白质的结构预测方面有着重要的应用。各种比对算法在这个领域都取得了很大的成功,但是每种算法都有其固有的缺陷。提出置换距离法,对当前流行的几种蛋白质多序列比对算法进行对比评价。由于置换距离法仅关注于不同蛋白质间进化距离的相对次序,而不考虑这些进化距离之间的细微差异,因而得到的评价结论更具有鲁棒性。另外,采用最长公共子序法度量置换距离可以比较准确的反映不同置换之间的差异性。基于该算法,对Dialign, Tcoffee, ClustalW和Muscle多序列比对算法进行了性能评估。

关键词: 多序列比对, 置换距离, 最长公共子序, 进化距离

Abstract: Protein multiple sequence alignment is an important bioinformatics tools. It has important applications in biological evolution analysis and protein structure prediction. A variety of alignment algorithms in this field have achieved great success. However, each algorithm has its own inherent deficiencies. In this paper, permutation distance is proposed to evaluate several protein multiple sequence alignment algorithms that are widely used currently. As the permutation distance method only concerns the relative order of different protein evolutionary distances, without taking into account the slight difference between the evolutionary distances, it can get more robust evaluations. In addition, the longest common subsequence method can well define the distances between different permutations. Using these methods, we compared and assessed Dialign, Tcoffee, ClustalW and Muscle.

Key words: multiple sequence alignment, permutation distance, longest common subsequence, evolutionary distance

中图分类号: