文献类型：期刊文章

作　　者：刘琦[1] 张引[2] 叶修梓[2] 俞荣栋[1]

机构地区：[1]浙江大学沃森基因组科学研究院,杭州310008 [2]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机学报》

年　　份：2008

卷　　号：31

期　　号：1

起止页码：51-58

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：提出了一种利用离散Hopfield网络求解图论极大独立集的启发式算法,并将其应用于RNA二级结构的茎区选择和预测当中.算法通过映射RNA序列的茎区为无向图中的节点,将预测RNA二级结构的问题转化为求解图的极大独立集的问题.定义了合理的能量变化函数,利用离散Hopfield网络进行迭代,以获得能量最优的预测结构.文中将算法与传统的最大匹配数算法以及最小自由能算法在运行时间上进行比较,并且选择特定的序列在茎区和碱基对水平上进行精度测试,结果证明该算法在效率和精度上具有一定的优势.算法的时间复杂性为max{O(n2),O(N2)},空间复杂度为O(N2),其中n为RNA序列长度,N为RNA的茎区段个数.

关 键 词：RNA  二级结构  极大独立集 离散HOPFIELD神经网络 茎区

分 类 号：TP181]