@inproceedings{palu_moehl_will_cp2010,
author = {Dal Palu, Alessandro and Möhl, Mathias and Will, Sebastian},
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},
doi = {https://link.springer.com/chapter/10.1007/978-3-642-15396-9_16},
user = {mmohl},
pages = {8},
location = {St Andrews, Scotland},
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.  }
}