Detail

Constrained Refining of Multiple Alignments to identify correlations between mutations

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.