基于离散Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用

摘要：

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

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

所属期刊栏目：31

分类号：TP181(自动化基础理论)

在线出版日期：2008-05-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：51-58