TY - GEN
T1 - A propagator for maximum weight string alignment with arbitrary pairwise dependencies
AU - Dal Palù, Alessandro
AU - Möhl, Mathias
AU - Will, Sebastian
PY - 2010/1/1
Y1 - 2010/1/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/78149277198
U2 - 10.1007/978-3-642-15396-9_16
DO - 10.1007/978-3-642-15396-9_16
M3 - Conference contribution
AN - SCOPUS:78149277198
SN - 364215395X
SN - 9783642153952
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 167
EP - 175
BT - Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings
PB - Springer Verlag
T2 - 16th International Conference on Principles and Practice of Constraint Programming, CP 2010
Y2 - 6 September 2010 through 10 September 2010
ER -