Computational Biology Problems

This chapter deals with some combinatorial optimization problems arising in computational biology. We first survey the assessment of the evolutionary distance between two genomes. The problem is equivalent to packing the edges of a bi-colored graph into a maximum number of alternating cycles, which naturally leads to an exponential-size ILP model. We then turn to the study of a particular type of bipartite matching, called alignment. Alignments are used to compare either protein sequences or protein 3-dimensional structures. We describe two exponential-size models for this type of comparisons and their compact extended reformulation