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