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).
Principal researcher: Ludwig Krippahl.