\input zb-basic
\input zb-ioport
\iteman{io-port 05679059}
\itemau{Peng, Yung-Hsing; Yang, Chang-Biau; Tseng, Kuo-Tsung; Huang, Kuo-Si}
\itemti{An algorithm and applications to sequence alignment with weighted constraints.}
\itemso{Int. J. Found. Comput. Sci. 21, No. 1, 51-59 (2010).}
\itemab
Summary: Given two sequences $S_{1}, S_{2}$, and a constrained sequence $C$, a longest common subsequence of $S_{1}, S_{2}$ with restriction to C is called a constrained longest common subsequence of $S_{1}$ and $S_{2}$ with $C$. At the same time, an optimal alignment of $S_{1}, S_{2}$ with restriction to $C$ is called a constrained pairwise sequence alignment of $S_{1}$ and $S_{2}$ with $C$. Previous algorithms have shown that the constrained longest common subsequence problem is a special case of the constrained pairwise sequence alignment problem, and that both of them can be solved in $O(rnm)$ time, where $r, n$, and $m$ represent the lengths of $C, S_{1}$, and $S_{2}$, respectively. In this paper, we extend the definition of constrained pairwise sequence alignment to a more flexible version, called weighted constrained pairwise sequence alignment, in which some constraints might be ignored. We first give an $O(rnm)$-time algorithm for solving the weighted constrained pairwise sequence alignment problem, then show that our extension can be adopted to solve some constraint-related problems that cannot be solved by previous algorithms for the constrained longest common subsequence problem or the constrained pairwise sequence alignment problem. Therefore, in contrast to previous results, our extension is a new and suitable model for sequence analysis.
\itemrv{~}
\itemcc{}
\itemut{algorithm; longest common subsequence; sequence alignment; weighted constraint}
\itemli{doi:10.1142/S012905411000712X}
\end