Combinatorial Optimization in Biology Combinatorial Optimization in Biology Quantitative technologies have, in recent years, taken on enormous importance for molecular biology. Some of the most fundamental problems facing biologists today, such as sequencing the Human Genome, rely extensively on the use of bioinformatics and computational techniques.
Large gaps remain to be filled, however.
Little attempt has been made to address some important optimization problems arising in a biologically-motivated setting, often because these problems have been thought to be computationally hard. Surprisingly, many of them are not. Particularly for problems relying on a geometric formulation, the theoretical machinery often exists for finding algorithms that solve them in polynomial time. Our goal is, based on these theoretical insights, to develop such algorithms so that they can readily be implemented. In the case of the Human Genome Project, we have already found that simple models of DNA sequencing procedures lead to polynomial-time algorithms that can improve sequencing efficiency substantially.