Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site

CREMA - Constrained Refining of Multiple Alignments to identify correlations between mutations

Project information

The goal of this project is to explore how constraint programming can help identify amino acid correlations by refining multiple sequence alignments obtained under the default assumption of independent mutations. The hypothesis that two mutations are correlated can be tested by realigning the sequences at those regions giving a lower penalty for mismatches at those positions. Given the nature of the problem and the need to test many combinations of sequence positions – many hypotheses of co-evolution – this problem is particularly suited to a constraint programming approach, using propagation to limit the boundaries of the necessary realignments and a branch-and-bound search to explore only those combinations that can result in significant correlations.

Ongoing since April 1st 2011, concludes in April 1st 2013.


Funding entity: Fundação Ciência e Tecnologia (MCTES).

Reference: PTDC/EIA-CCO/115999/2009

Funding: 44924.


Principal researcher: Ludwig Krippahl.

Funding: 44924.

Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541