@Article{Will:Busch:Backofen:_effic_sequen_align_side_const:Constraints2008,
  author =	 {Sebastian Will and Anke Busch and Rolf Backofen},
  title =	 {Efficient Sequence Alignment with Side-Constraints by
                  Cluster Tree Elimination},
  journal =	 {Constraints Journal},
  issn = 	 {1383-7133},
  volume =       13,
  number =       1,
  pages  =       {110-129},
  year =	 2008,
  user =	 {will},
  url =          {http://ai.uwaterloo.ca/~vanbeek/Constraints/vol13.html},
  abstract =	 {Aligning DNA and protein sequences is a core technique in
                  molecular biology. Often, it is desirable to include partial
                  prior knowledge and conditions in an alignment. Going beyond
                  prior work, we aim at the integration of such side
                  constraints in free combination into alignment
                  algorithms. The most common and successful technique for
                  efficient alignment algorithms is dynamic programming
                  (DP). However, a weakness of DP is that one cannot include
                  additional constraints without specifically tailoring a new
                  DP algorithm. Here, we discuss a declarative approach that
                  is based on constraint techniques and show how it can be
                  extended by formulating additional knowledge as
                  constraints. We take special care to obtain the efficiency
                  of DP for sequence alignment. This is achieved by careful
                  modeling and applying proper solving strategies. Finally, we
                  apply our method to the scanning for RNA motifs in large
                  sequences. This case study demonstrates how the new approach
                  can be used in real biological problems. A prototypic
                  implementation of the method is available at
                  http://www.bioinf.uni-freiburg.de/Software/CTE-Alignment.},
 doi =           {10.1007/s10601-007-9032-x}
}