Sebastian Will, Anke Busch, Rolf Backofen:
Efficient Sequence Alignment with Side-Constraints by Cluster Tree Elimination.
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.
URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-001
@article{REWERSE-RP-2008-001, author = {Sebastian Will and Anke Busch and Rolf Backofen}, title = {Efficient Sequence Alignment with Side-Constraints by Cluster Tree Elimination}, journal = {Constraints Journal - Special Issue on Constraint based methods for Bioinformatics}, year = {2008}, volume = {13}, number = {1}, pages = {110--129}, url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-001} }