排序距离矩阵蛋白质结构比对算法

排序距离矩阵蛋白质结构比对算法

许海洋, 周春光, 郎美娜, 邹淑雪

吉林大学计算机科学与技术学院, 长春 130012

收稿日期:2007-10-17 修回日期:1900-01-01 出版日期:2008-07-26 发布日期:2008-07-26
通讯作者: 周春光

Protein Structure Comparison by Sort Matrix Alignment

XU Haiyang, ZHOU Chunguang, LANG Meina, ZOU Shuxue

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2007-10-17 Revised:1900-01-01 Online:2008-07-26 Published:2008-07-26
Contact: ZHOU Chunguang

摘要/Abstract

摘要： 提出一种改进的SortMatAlign算法, 通过快速排序预处理距离矩阵, 使MatAlign算法的时间复杂度由O(N₄)降为O(N₃). 结果表明, SortMatAlign算法计算出的RMSD值平均是MatAlign算法的1.098倍, 使用残基个数和RMSD综合衡量标准的S值平均是MatAlign算法的0.968倍, 在同等条件下, 运行速度比MatAlign提高18.276倍.

关键词: 蛋白质结构, 结构比对, 快速排序, SortMatAlign算法, 时间复杂度

Abstract: An improved SortMatAlign method was proposed by which MatAlign time complexity was reduced from O(N₄) to O(N₃) by quick sort and pretreatment of distance matrices. Experiment results support the new method’s feasibility and effectiveness. On the average, the value of RMSD by SortMatAlign is 1.098 times that by MatAlign, and the Svalue comprehensively evaluated by the number of residue pairs and RMSD is 0.968 times that by MatAlign. SortMatAlign is 18.276 times faster than MatAlign to get the same result.

Key words: protein structure, structural comparison, quick sort, SortMatAlign method, time complexity

中图分类号:

TP18

许海洋, 周春光, 郎美娜, 邹淑雪. 排序距离矩阵蛋白质结构比对算法[J]. J4, 2008, 46(04): 670-674.

XU Haiyang, ZHOU Chunguang, LANG Meina, ZOU Shuxue. Protein Structure Comparison by Sort Matrix Alignment[J]. J4, 2008, 46(04): 670-674.

[1]	景文博, 段锦, 王晓曼, 赵思, 徐皓, 姜会林. 夏克-哈特曼阵列光斑质心探测误差比较[J]. J4, 2010, 48(06): 1013-1017.
[2]	邹淑雪, 刘桂霞, 时小虎, 周春光. 基于距离最大熵值的蛋白质结构域边界检测系统[J]. J4, 2009, 47(6): 1237-1240.
[3]	邹淑雪, 黄艳新, 李艳文, 周春光. 一种基于支持向量机的蛋白质结构域边界预测方法[J]. J4, 2008, 46(05): 930-934.