【摘 要】
:
应用热动力学最小自由能量方法从RNA序列预测其二级结构起始于Tinoco等人,Zuker将动态规划算法用于复杂的Tinoco模型,设计了Mfold算法,算法的时间复杂度为O(n3).Mfold算法不允许伪结点存在,但伪结点在几种已知RNA中具有重要功能.包含伪结点的RNA二级结构预测问题是NPC问题.Rivas与Eddy提出了简化的包含多个伪结点的热动力学模型,并首次相应的多项式时间算法,算法的时
【机 构】
:
山东经济学院计算机科学与技术系,济南,250014 山东大学计算机学院,济南,250100
【出 处】
:
2004年全国理论计算机科学学术年会
论文部分内容阅读
应用热动力学最小自由能量方法从RNA序列预测其二级结构起始于Tinoco等人,Zuker将动态规划算法用于复杂的Tinoco模型,设计了Mfold算法,算法的时间复杂度为O(n3).Mfold算法不允许伪结点存在,但伪结点在几种已知RNA中具有重要功能.包含伪结点的RNA二级结构预测问题是NPC问题.Rivas与Eddy提出了简化的包含多个伪结点的热动力学模型,并首次相应的多项式时间算法,算法的时间复杂度为O(n6).B.1yngs(φ)等人提出仅包含一个平面伪结点的模型及算法,其时间复杂度为O(n5),空间复杂度为O(n3). 本文提出了一个新算法,其时间复杂度为O(n5),空间复杂度为O(n4)。算法使用六段子序列的组合表示包含伪结点的**A二级结构,并利用Lsnns巾算法的一个计算技巧,可预测包含多个平面伪结点和一个非平面伪结点的二级结构。
其他文献
"不确定有穷自动机NFA(即Non-FiniteAutomat),先转化为确定有穷自动机FA(即FiniteAutomat),再转化为规范有穷自动机GFA(即GageFiniteAutomat)",是有穷自动机极小化的研究基础.HopcroftJE.等学者曾论及"NFA→FA→GFA"等价转换,但未见构造性算法.为此,本文将给出有穷自动机的规范化算法.
在国内电信领域,长期以来,应用软件滞后于市场需求.传统的电信运营支撑系统以业务为中心,分散建设,分散管理,分散设计,缺乏统一的平台框架,缺少统一的客户信息,无法支持决策,难于统一企业经营思路和策略,难于建立企业的整体品牌形象,且存在着开发周期长,可维护性差等问题,很难满足以客户为中心的新一代电信运营支撑系统的需求.
本文结合电信管理论坛(TMF)对新一代电信运营支撑系统(NGOSS)的研究成果,针
本文鉴于信息战的战略地位,对网络系统和软件自身的防御和反攻击的智能化进行了研究。文章围绕软件的安全威胁、软件智能防御机制、软件智能防御机制的实现进行了论述。
随着Internet的迅猛发展和WWW的兴起,分布式计算已成为计算机技术的关键研究领域.但不论是基于过程还是面向对象的分布式计算环境,它们都采用了传统的客户/服务器模式,实现分布计算的关键技术是通过远程过程调用(RPC)或对象引用(object-reference)实现跨平台的互操作,这种模式适合于传统的相对稳定的网络环境和应用程序.但在处理爆炸性的网络信息资源及移动计算、信息服务等新兴应用领域,
贝叶斯分类是机器学习和数据挖掘中最有效的学习算法之一,它的时间复杂性仅仅是线性的,空间复杂度也很低,只需要遍历训练数据一次.朴素贝叶斯分类在分类中非常有效,试验表明,朴素贝叶斯分类算法预测能力和决策树C4.5一样好.贝叶斯分类总是基于这样一种看似不现实的假设:对于给定的类,所有属性的分布是相互独立的.随着网络应用的迅猛发展,网络的安全问题也显得越来越突出.传统的网络入侵检测技术的局限性越来越明显,
近几年,随着网络计算技术的发展,Internet使得在全球范围开展各种协同工作成为可能,新应用(虚拟企业、电子商务、远程医疗等)和新技术(软件组件、agent/多agent系统、移动agent等)不断产生,一方面给协同科学的研究和应用提供了强有力的支持,另一方面也对建立协调与协作系统提出了更高要求.本文的内容,主要是在分析目前多agent社会组织设计方法的基础上,按照开放系统的设计需求,提出一个通
在人工智能领域内,博弈是很重要的一个研究分支.通过对博弈的研究,可以解决很多实际问题,使电脑智能向人类智能迈进一大步.1997年,世界头号国际象棋大师卡斯帕罗夫与IBM的超级计算机"深蓝"较量后不得不俯首称臣,让人脑第一次尝到了在电脑面前失败的滋味.博弈理论在这场人机大战中起了关键性的作用.博弈理论已被用于很多棋类游戏的设计中.本文以五子棋问题为例,讨论了一个基于博弈树的五子棋算法及其具体实现,在
基于案例推理(Case-BasedReasoning简称CBR)是近十几年来人工智能中发展起来的,有别于基于规则推理的一种新的推理模式,它是指借用已有的事例或经验来解决新问题,评价解决方案,解释异常情况或理解新情况.采用基于规则的人参病虫害专家系统存在系统难于维护,系统不会学习,维护耗时,知识难于获取和推理脆弱性等问题,而CBR在进行问题求解时,使用以前求解类似问题的经验进行推理的方法,其核心在于
离散数学是研究离散量的结构及其相互间关系的一门学科,是计算机科学的数学基础.集合论中的有关关系的研究在计算机科学中得到了广泛的应用.关系的各种闭包运算实际上是获得具有良好性质的关系的方法,而由关系矩阵直接判断关系的传递性、求解关系的传递闭包是一个经常碰到但又不容易解决的问题.
感知器(perceptron)是由美国学者F.Rosen-blatt于1957年提出的,其目的是为了模拟人脑的感知和学习能力.感知器是最早提出的一种神经网络模型,是一个具有单层神经元的网络,网络的激活函数是线性阈值单元.原始的感知器算法只有一个输出结点,相当于单个神经元.早期的研究人员试图用感知器模拟人脑的感知特征,但后来发现感知器的学习能力有很大的局限,如只能对线性可分的输入向量进行分类,以致于