@INPROCEEDINGS{palu_moehl_will_cp2010,
  AUTHOR = {Alessandro Dal Palu and Mathias M{\"o}hl and Sebastian Will},
  TITLE = {A Propagator for Maximum Weight String Alignment with Arbitrary Pairwise Dependencies},
  BOOKTITLE = {Proceedings of the 16th International Conference on
                  Principles and Practice of Constraint Programming (CP-2010)},
  YEAR = {2010},
  PAGES = {8},
  LOCATION = {St Andrews, Scotland},
  USER = {mmohl},
  ABSTRACT = { The optimization of weighted string alignments is a
                  well studied problem recurring in a number of
                  application domains and can be solved
                  efficiently. The problem becomes MAX-SNP-hard as soon
                  as arbitrary pairwise dependencies among the
                  alignment edges are introduced.  We present a global
                  propagator for this problem which is based on
                  efficiently solving a relaxation of it. In the
                  context of bioinformatics, the problem is known as
                  alignment of arc-annotated sequences, which is
                  e.g. used for comparing RNA molecules. For a
                  restricted version of this alignment problem, we
                  show that a constraint program based on our
                  propagator is on par with state of the art
                  methods. For the general problem with unrestricted
                  dependencies, our tool constitutes the first
                  available method with promising applications in this
                  field.  },
  user =	 {mmohl}
}