Sequence alignment algorithm is very mature.Smith-Waterman’s dynamic algorithm is the most efficient and basic method in 1-dimensional sequence alignment.But it is not fit for 3-dimensional structure alignment because it requires vast time and space.In this paper
we develop a dynamic algorithm to compare two protein 3-dimensional structures by using some geometry invariants under translation and rotation.Geometry invariants include many useful features of protein 3-dimensional structure.By calculating the geometry invariants
"distance" and "similarity scoring" are defined.At the end
a new algorithm based on dynamic programming is provided.Comparison with computer simulation and HOMSTRAD(HOMologous Structure Alignment Database) indicates that our approach is better in both the aligned results and alignment speed.
关键词
蛋白质结构比对相似分值动态规划
Keywords
protein 3-dimensional structurealignmentsimilarity scoringdynamic programming