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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 课题背景与研究意义
•   1.2 国内外研究现状
•     1.2.1 基于单序列研究算法
•     1.2.2 基于多序列研究算法
•   1.3 本文的主要研究内容
•   1.4 论文组织结构
• 第2章 相关知识
•   2.1 RNA基本概念
•     2.1.1 RNA
•     2.1.2 RNA二级结构
•     2.1.3 RNA二级结构常见相似度距离计算算法
•   2.2 聚类
•     2.2.1 聚类概念
•     2.2.2 常见聚类分类
•   2.3 半监督聚类
•   2.4 本章小结
• 第3章 基于Rsd-bp距离的多个RNA二级结构距离计算
•   3.1 问题分析
•   3.2 Rsd算法
•     3.2.1 Rs树模型构建
•     3.2.2 Rsd算法设计
•   3.3 基于Rsd-bp距离的多个RNA二级结构距离计算
•     3.3.1 归一化思想
•     3.3.2 Rsd-bp算法设计
•     3.3.3 多进程优化Rsd-bp算法
•   3.4 算法分析
•   3.5 本章小结
• 第4章 基于半监督学习的RNA二级结构聚类算法研究
•   4.1 问题分析
•     4.1.1 RNA二级结构半监督聚类存在缺陷
•     4.1.2 k-medoids算法存在缺陷
•   4.2 输入数据预处理
•     4.2.1 数据集合预处理
•     4.2.2 约束集合预处理
• +算法设计'>  4.3 SS-medoids⁺算法设计
•     4.3.1 SS-medoids+算法思想
•     4.3.2 中心点更新规则
•   4.4 算法分析
•   4.5 本章小结
• 第5章 实验验证
•   5.1 实验环境及数据集来源
•   5.2 多进程优化Rsd-bp算法
•     5.2.1 Rsd-bp算法计算能力验证实验
•     5.2.2 计算时间验证实验
•     5.2.3 整体分析
• +算法的RNA二级结构聚类实验'>  5.3 基于SS-medoids⁺算法的RNA二级结构聚类实验
•     5.3.1 实验数据
•     5.3.2 评分标准
•     5.3.3 实验步骤与结果分析
•   5.4 本章小结
• 结论
• 参考文献
• 附录
• 致谢

文章来源

类型: 硕士论文

作者: 李佳慧

导师: 王常武,李永强

关键词: 二级结构,树模型,距离计算,半监督聚类

来源: 燕山大学

年度: 2019

分类: 基础科学,信息科技

专业: 生物学,计算机软件及计算机应用

单位: 燕山大学

分类号: TP311.13;Q522

DOI: 10.27440/d.cnki.gysdu.2019.000437

总页数: 72

文件大小: 2500K

下载量: 12