两种带约束的序列比对算法

Two Algorithms for Constrained Sequence Alignment Problem

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

Constrained sequence alignment,a new problem,demands the alignment result including the constraint sequence. Algorithms of this problem could be more complicated. In this paper,two conditions to slove the constrained sequence alignment problem are demonstrated theoretically when the penalty factor φ in the distance function is 0. The two algorithms for the longest common subsequence problem is extended to solve CSA problem. The time complexities of the two improved algorithms are O（nmr） and O（nm（r ＋ 1）） and the space complexities are O（nmr） and O（（n ＋ m）（r ＋ 1））, respectively. The results of the two algorithms are exact without mismatchs when the numbers of ＂ -＂ inserted into X and Y are （m - l） and （n - l）, respectively. The experiments prove the validity of the two algorithms.