DNA是遗传信息的载体,遗传信息的作用通常由蛋白质的功能来表现,但DNA并非蛋白质合成的直接模板,合成蛋白质的模板是RNA。RNA二级结构预测问题是计算机科学和生物信息学的基本课题之一,RNA二级结构预测用于蛋白质功能分析,序列对比分析法及热动力学最小自由能量方法是RNA二级结构预测的两种基本方法,序列对比分析法的基本思想,是找出检测序列和目标序列的相似性。序列对比的最终实现,必须依赖于某个数学模型,在序列非常相近或新的独立序列的情况下,序列对比法不适应。目前热动力学最小自由能量方法已成为RNA二级结构预测的最常用方法。 目前预测RNA二级结构的大多数算法仅预测嵌套的RNA二级结构,不允许伪结点存在。但伪结点在几种已知RNA中具有重要功能。如Pleij等人于1985年预测了RnaSe P RNAS中的伪结点结构,并由Kock等人于1998年予以证实。 包含伪结点的RNA二级结构预测问题是NPC问题。目前预测包含伪结点的RNA二级结构的动态规划算法有:Rivals算法、B.Lyngsφ算法和Jens Reeder的代数动态规划等算法。Rivals算法、B.Lyngsφ算法都可预测包含伪结点的RNA二级结构.Rivas算法可计算包含任意平面伪结点和特定条件下的非平面伪结点结构,其时间复杂度为O(n~6),空间复杂度为O(n~4)。Lyngsφ算法仅可计算包含一个平面伪结点的结构,其时间复杂度为O(n~5),空间复杂度为O(n~3)。最近较好的预测算法使用其O(n~4)时间和O(n~3)的空间预测任意的平面伪结点。 动态规划算法需要的时间和空间较大,预测长度大于1000个碱基的RNA二级结构十分困难。嵌套的二级结构算法又不能预测伪结点结构,因此迫切需要快速算法预测包含伪结点的RNA二级结构。 本文提出一个预测RNA二级结构的贪心算法,算法思想为计算具有最多堆迭的RNA二级结构,该想法来源于“堆迭结构相对稳定”的