空间随机行走比对问题的动态规划算法  

Alignment of Random Walks by Dynamic Programming

作　　者：尚英姿[1] 董宇辰[2] 董涛[3] 

机构地区：[1]河北经贸大学数统学院,河北石家庄050011 [2]厦门大学经济学院,福建厦门361005 [3]河北省老年病医院体检科,河北石家庄050011

出　　处：《数学的实践与认识》2011年第2期103-109,共7页Mathematics in Practice and Theory

基　　金：河北省软科学项目(0545725)

摘　　要：受计算生物学中两个蛋白质结构比对问题的启发,定义了三维空间随机步以及两个随机步同构等的概念.研究了步长为k的随机步非同构意义下的个数.最后提出了两个非同构随机步对齐的优化问题,通过研究随机步的同构,采用动态规划给出了将一个随机步对齐到另一个随机步所需最少的操作步数的算法.Inspired by protein structures alignment allowing twist,we propose the problem of comparison of two random walks on a periodic lattice.In this paper we define the isomorphism between two walks and give a dynamic algorithm to find the minimum number of operations to make one walk to be another walk.

关 键 词：随机步 折叠 随机步对齐 特殊正交群 动态规划 

分 类 号：O221.3[理学—运筹学与控制论]