Improving multiple sequence alignments with constraint programmingand local search

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Sequence alignment is a core problem in Bioinformatics, and
multiple sequence alignments (MSA) are an important tool for phyloge-
netics, motif and domain identication, physiological studies and even
protein structure and interaction, since MSA provide information on
the coevolution of amino acid residues. However, the complexity of si-
multaneously 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 exibility in the scoring functions.
Original languageUnknown
Title of host publicationWorkshop on Constraint Based Methods for Bioinformatics
Publication statusPublished - 1 Jan 2011
EventWorkshop on Constraint Based Methods for Bioinformatics -
Duration: 1 Jan 2011 → …


ConferenceWorkshop on Constraint Based Methods for Bioinformatics
Period1/01/11 → …

Cite this