Abstract
In this thesis, we study the constrained sequence alignment problem. We introduce two new elements into the problem: ranges between patterns, and unorderedness of the patterns. In addition to the various biological applications of such variants, we investigate the impacts of the new elements to the design of efficient algorithms for the problems. Also, we introduce a new dimension to the problem: one-annotated or not. The one-annotated version, as a special case of the original problem, has its own biological applications, and often admits more efficient algorithms. Hence to clarify the difference is meaningful. The goal of the constrained alignment problem is to align a set of sequences such that specified patterns must be aligned together. This is desirable since one often have the knowledge about the patterns that are necessary for some function to work. If one is aligning sequences under such knowledge, or want to determine if a query sequence have the function of some protein family, constrained alignment turns out to be useful. For the original problem, we proposed a 2-approximation algorithm which significantly improves the efficiency over previous results. Ranges and order of binding elements are sometimes important for determining gene expression. The introduction of ranges and order information turns out to be meaningful both theoretically and biologically. As to the range information, we require that ranges between any two adjacent patterns satisfy user's specification. We refer to this problem as SARC (sequence alignment with ranged constraint). For the one-annotated case, our algorithm solves the problem in $O(n^{2} \log n)$ time and $O(n^{2})$ space. As to the order information, we prove that if the patterns are allowed to appear in any order in the output alignment, then the problem becomes not approximable within any function computable in polynomial time. We also show that the a relative to this problem that is a member of NPO turns out to be NPO-complete. Another direction of extension in this thesis is to generalize the definition of patterns. We introduce a generalized framework to admit higher flexibility without loss of efficiency.