ISyE Seminar Series-COMBINATORIAL OPTIMIZATION MODELS IN MOLECULAR BIOLOGY
This talk will illustrate the kinds of problems in the entitled category. Particular focus will be on the lattice model for protein folding and protein alignment by contact maps. The talk will develop formulations and show how one is sharper than another. I shall also illustrate symmetry exclusion and suggest some open problems. The contact map of a protein is a graph whose nodes represent the amino acid residues and whose edges represent 'closeness' in the native state. A similarity measure for two proteins is the relative size of a maximum subgraph isomorphism. I shall illustrate how standard methods break down, such as the ineffectiveness of clique inequalities for a related maximum independent set problem.