PRELIMINARY ABSTRACT:
---------------------
Improving Multiple Sequence Alignments with Constraint Programming and Local Search 
Marco Correia, Fábio Madeira, Pedro Barahona and Ludwig Krippahl 
Keywords: 
constraints, sequence, alignment, bioinformatics
Abstract: 
Sequence alignment is a core problem in Bioinformatics, and multiple sequence
alignments (MSA) are an important tool for phylogenetics, motif and domain
identification, physiological studies and even protein structure and interaction,
since MSA provide information on the coevolution of amino acid residues. However,
the complexity of simultaneously aligning multiple sequences is exponential on
the number of sequences, and so MSA must be computed using heuristics that cut
through this large search space, compromising the quality of the result and
limiting the scoring functions that can be used. In this paper, we propose a
constraint programming (CP) and local search based method for repairing MSA
obtained with classical algorithms in order to improve the alignments and to
allow greater flexibility in the scoring functions.