RNA二级结构预测算法研究.pdf

中文摘要摘要RNA(RibonucleicAcid,砌妊)分子在生物细胞中不仅充当着遗传信息的载体和传递工具,还具有催化RNA的剪接,加工和修饰RNA前体,调控基因表达和生物体的生长发育等一系列重要的功能,而功能与结构是密切相关的,因此对RNA分子结构的研究就成为分子生物学的一个重要领域。由于RNA分子具有降解速度快,难以结晶等特点,通过x射线晶体衍射和核磁共振等实验方法去测定RNA分子的立体结构花费的成本高、时间长,虽然测得的结果精确可靠,可是面对当前海量的生物序列,实验方法显然跟不上要求,因此RNA二级结构预测就成为研究RNA分子结构的主要手段。RNA二级结构预测是指借助于计算机手段和各种数学方法从理论上去预测RNA的空间结构,可为揭示RNA结构与功能的关系提供重要信息,大大提高认识RNA空间结构的效率。论文对目前主流的RNA二级结构预测算法的理论和实现方法进行了细致的研究。通过对基于热力学的预测方法(包括Zuker的最小自由能算法、遗传模拟退火算法、Hopfield神经网络方法、免疫粒子群算法)和比较序列分析方法(协同变异预测模型、随机上下文无关语法预测)以及基于机器学****的分类预测方法的分析,对这些算法存在的优缺点进行了比较研究,总结出了RNA结构预测方法发展的趋势和要求,为本文的预测算法奠定了理论和实验基础。首先论文分析了人工鱼群智能算法在优化问题中的优势和不足,并针对基本人工鱼群算法在解决离散问题的过程中存在的的缺陷进行了相应改进,首次将鱼群算法应用到RNA二级结构预测问题中,建立了一种基于人工鱼群算法的最小自由能算法模型。在对算法编码实现时,采用集合表示状态点,能有效地缩小搜索空间,有利于算法在较短时间内找到目标解。仿真实验与传统的基于最小自由能的相关算法进行了比较研究,结果表明,使用改进鱼群算法进行RNA序列的二级结构预测能获得较理想的预测效果,能有效减少计算量、节省计算时间,特别当待测序列长度大于500时,鱼群算法在收敛速度上有着较明显优势。其次,研究了粒子群优化算法在组合优化问题中的应用背景,针对基本粒子群算法的早熟收敛,容易陷入局部最优且搜索精度不高等缺点,进行了相应的改进,提出了局部精英粒子群算法,在该算法中,通过改变粒子的邻居拓扑结构,使每个粒子拥有固定的局部邻居,每次迭代都会根据自身在邻居中的地位和状态以及历史最优值来调整下一步的状态。由于有效地保持粒子的多样性,使得算法有较好地跳出局部极值的特性。本文根据局部精英粒子群算法的思想构建了一套基于最小自由能思想的RNA重庆大学博士学位论文二级结构预测模型。在对算法进行编码时,使用集合来表示粒子的状态,巧妙地将粒子运动的速度和状态函数使用集合之间的运算来重载,避免了传统粒子群算法参数选择的烦恼。实验数据有力地支持了改进后的粒子群算法和新的粒子运动状态编码方式。第三,通过扩展NSSEL(NewSecondaryStructureElememLabels,NSSEL)标签,创建了一套能够描述伪结结构信息的eNSSEL(extendedNSSEL,eNSSEL)标签。一条RNA分子序列中的所有碱基都可以使用eNSSEL标签进行标记,从另一个角度来理解,即:任意一个碱基都可以被分类为某一个标签,因此,一条原始的RNA分子序列能与一条eNSSEL标签序列一一对应。由于eNSSEL标签携带了结构信息,因此,对于某一个RNA分子而言,只要得到其对应的标签序列,就可以知道其二级结构的组成。根据该思想,建立了基于SVMs(supportvectormachines,SVMs)的分类预测模型。该模型通过有效训练后,在可接受的预测精度范围里具有较低的计算复杂度,能有效地解决传统算法中存在的计算复杂性问题,为预测长链分子提供了一种全新的思路。关键词:RNA一--级结构预测,鱼群算法,粒子群算法,icinformation,acatalystofbiochemicalreactions,anadaptermoleculeinproteinsynthesis,-icresonance,,thesepredictionalgorithmsCallraiseefficiencygreatlyforscientiststo