序列联配以及序列二级结构联配是生物信息处理中最基本最重要的问题。自1970年Needleman和Wunsch提出的经典的动态规划算法以来,如何获得结果准确,时间空间效率更高的序列联配算法和软件一直是生物信息学研究中的一项重要课题。考虑实际序列联配问题中的序列具有较高的相识度,也就是说在最佳联配中各个序列中插入的空格数将不会太大,本文将待插入的空格数上限作为限制来设计序列联配算法,从而降低算法的运行时间和空间的复杂度。Needleman和Wunsch给出的运行时间和空间为O(m?n)的动态规划算法至今仍然是最为实用和有效的双序列联配算法之一,其中m,n为两条序列的长度。本文在Needleman和Wunsch的动态规划算法的基础上提出了一种在k插缺数限制下双序列联配的算法,其运行时间和空间复杂度都为O k?min?,(m n?)。同时,文中将该思想引入Hirschberg线性空间算法中,给出了一种在k插缺数限制下的双序列联配线性空间算法,其运行时间仍然为O k?min?,(m n?),但只使用线性的内存空间。大量实际数据说明一般最佳联配下插入空格数在序列长度的20%以内,因此在实验中,大部分序列将k规定在序列长度的20%,新算法可以将运行时间直接减少近50%的情况下仍然保证找到最优解,对于部分相似度高的序列,甚至可以将运行时间直接减少近85%的情况下仍然保证找到最优解。接下来,文中将参数k的思想应用到三条序列联配算法中,设计了在k插缺数限制下三条序列联配的算法,时间复杂度和空间复杂度都为2O(k?n),其中k为参数表示允许插入的最大空格数,三条序列长度均为n。在多序列联配问题中由于序列数量增加而导致计算难度陡增,引入参数k的概念也不能获得实际有效的算法。因此本文给出一种基于双序列联配的快速多序列联配启发式算法。然后以BAliBASE数据库来测试与其他算法比较,实验也验证我们的算法明显比之前的算法的准确性更好。对序列二级结构联配问题,文中同样经典的Bafna算法中引入参数k的概念。将原本时间和空间复杂度都为3 2 2O(mn?m n)的算法改进为时间和空间复杂度都为2 2 21 1O(k mn?k n)的算法,其中m、n为两条序列长度,1k是序列中允许插入的最大空格数。最后本文总结了引入参数k的概念的序列联配及序列二级结构联配问题的研究结果,并对相关工作的未来的研究方向做了展望及提出了一些问题可能的解决方法。