RNA二级结构形状—碱基对距离及半监督聚类算法研究

发布时间：2022-01-21 23:13

　　RNA是生命体内重要的大分子之一,不仅在遗传信息翻译中起决定作用,还具有酶的催化、细胞调节、病毒遗传信息携带等功能。RNA功能多样性的关键在于RNA空间结构,而RNA空间结构的构成由RNA二级结构决定。真实RNA二级结构存在于高于最小自由能一定阈值范围内的RNA二级结构集合中。因此,通过计算RNA二级结构间距离区别RNA二级结构差异,并使用高效的聚类算法对RNA二级结构集合进行划分筛选代表结构,对真实RNA结构预测有重要意义。本文对RNA二级结构距离计算算法和RNA二级结构聚类算法进行研究,内容如下。首先,针对已有RNA二级结构距离计算算法计算依据单一,误差性大的问题,提出RNA二级结构形状-碱基对距离计算算法。算法第一步是计算RNA二级结构的形状距离,将RNA二级结构抽象为带符号的有序树,通过转换、删除的树编辑操作来计算形状距离。第二步通过归一化思想计算形状距离和碱基对的平均分。第三步对Rsd-bp算法进行多进程优化,实现计算效率的提升。其次,针对传统算法采用随机选择的方式初始化中心点,易陷入局部最优解的问题,提出半监督的RNA二级结构k-medoids算法,根据Rsd-bp算法计算... 

【文章来源】：燕山大学河北省

【文章页数】：72 页

【学位级别】：硕士

【部分图文】：

RNA二级结构的多边形表示图和抽象结构表示RNAHeliCes[32]

燕山大学工程硕士学位论文第 2 章 相关知识概念酸)是由核糖核苷酸经磷酯键缩合而成长链状分子起构成已知生命形式所必需的四种主要大分子。如核苷酸分子、磷酸、核糖、碱基构成，RNA 碱基主呤、C 胞嘧啶、U 尿嘧啶。根据碱基配对原则，R生物学功能。RNA 碱基配对规则为 A-U、C-G、G，又被称为摆动基对。

25: else:26: D←D127: maxd1← [maxd - dist(m0,m)]28: space←seg_maxd(newr,dist(:,m))29: sapce←space-al30: M,d← f_m(m0[i],maxd,cluster,space,D,m)31: return M,dEND算法 4.2 通过可变搜索邻域的方式进行中心点替换减少了数据比对的次数提高了算法效率。算法 4.2 时间复杂度分析主要包括两部分：(1)12 行到 31 行通过递归的方式查找某一中心点可替换中心点，其时间复杂度为 O( log N )，N 在最坏的情况下为该簇搜索最大半径内的数据个数；(2)1 到 11 行为主函数，遍历搜索该簇内的新中心点。综上所述，算法 4.2 的总时间复杂度为O( N log N )，空间复杂度为O( N )。

【参考文献】：
期刊论文
[1]云计算环境下面向数据分布的K-means聚类算法[J]. 刘雪娟,袁家斌,操凤萍.  小型微型计算机系统. 2017(04)
[2]IC-kmedoids:适用于RNA二级结构预测的聚类算法[J]. 王常武,刘小凤,王宝文,刘文远.  生物医学工程学杂志. 2015(01)
[3]半监督聚类的若干新进展[J]. 李昆仑,曹铮,曹丽苹,张超,刘明.  模式识别与人工智能. 2009(05)
[4]RNA二级结构预测中动态规划的优化和有效并行[J]. 谭光明,冯圣中,孙凝晖.  软件学报. 2006(07)
[5]RNA折叠[J]. 王传铭,潘珉,曹槐.  自然杂志. 2004(05)

博士论文
[1]半监督聚类算法的研究与应用[D]. 管仁初.吉林大学 2010

硕士论文
[1]基于RBP的次最优自由能RNA二级结构的密度聚类问题研究[D]. 王秀芹.燕山大学 2014



本文编号：3601135