两种带约束的序列比对算法 (2009年)

通过理论证明，得出了当距离函数中惩罚因子φ=0时的解应满足的条件，并在此基础上改进两种最长公共子序列的优化算法，使之能够求解出带约束的序列比对问题。这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1))，空间复杂度分别为O(nmr)和O((n+m)(r+1))。推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l)，使比对结果中不会出现错配，保证了比对的质量。实现了基于回溯的改进算法，验证了其求解带约束的序列比对问题的有效性。