| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于离散Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用 |
| 作者 | 刘琦1) 张引2) 叶修梓2) 俞荣栋1) |
| 作者单位 | 1)(浙江大学沃森基因组科学研究院 杭州 310008) 2)(浙江大学计算机科学与技术学院 杭州 310027) |
| 发表年份 | 2008 |
| 发表月份 | 1期(51—58) |
| 文章摘要 | 摘要 提出了一种利用离散Hopfield网络求解图论极大独立集的启发式算法，并将其应用于RNA二级结构的茎区选择和预测当中.算法通过映射RNA序列的茎区为无向图中的节点，将预测RNA二级结构的问题转化为求解图的极大独立集的问题.定义了合理的能量变化函数，利用离散Hopfield网络进行迭代，以获得能量最优的预测结构.文中将算法与传统的最大匹配数算法以及最小自由能算法在运行时间上进行比较，并且选择特定的序列在茎区和碱基对水平上进行精度测试，结果证明该算法在效率和精度上具有一定的优势.算法的时间复杂性为max｛O(n2),O(N2)｝，空间复杂度为O(N2)，其中n为RNA序列长度，N为RNA的茎区段个数. 关键词 RNA；二级结构；极大独立集；离散Hopfield神经网络；茎区 |