Article ID: | iaor20083853 |
Country: | Netherlands |
Volume: | 173 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 17 |
Publication Date: | Aug 2006 |
Journal: | European Journal of Operational Research |
Authors: | Wilhelm W.E., Butenko S. |
Keywords: | optimization, graphs |
Many important problems arising in computational biochemistry and genomics have been formulated in terms of underlying combinatorial optimization models. In particular, a number have been formulated as clique-detection models. The proposed article includes an introduction to the underlying biochemistry and genomic aspects of the problems as well as to the graph-theoretic aspects of the solution approaches. Each subsequent section describes a particular type of problem, gives an example to show how the graph model can be derived, summarizes recent progress, and discusses challenges associated with solving the associated graph-theoretic models. Clique-detection models include prescribing (a) a maximal clique, (b) a maximum clique, (c) a maximum weighted clique, or (d) all maximal cliques in a graph. The particular types of biochemistry and genomics problems that can be represented by a clique-detection model include integration of genome mapping data, nonoverlapping local alignments, matching and comparing molecular structures, and protein docking.