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