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~+算法有效性性。