|
Mathematics and Computational Biology
Variation and selection are key features of evolution. Variation (acting upon the genome) is typically realized by mutations, that is insertions, deletions and point mutations and, in case of diploid organisms, additionally by recombination. Selection can act upon genotypes and phenotypes and is oftentimes determined by some kind of interaction among them. Variational processes, as they occur in nature, are typically randomizations and it is a central question in evolutionary biology what role and function variation has. This question has been adressed by M. Kimura in his neutral theory. The object of Kimura's neutral Theory is the role of variation in complete absence of selection. A further closely related question becomes immediately apparent, namley how can certain (well adapted) phenotypes persist while their corresponding genoms are acted upon by random alterations?
It seems that, at leat on molecular level, nature is capable of "computing by white noise'' and a particularly beautiful instance of this "white noise computation'' are the SELEX experiments in which RNA molecules are dramatically optimized. A deeper understanding of this optimization process would certainly have significant consequences and implications for other scientific fields. For example, fields like "genetic algorithms'' and "evolutionary computation'' are strongly driven by their biological paradigms. One structure that allows for the preservation of the phenotype while simultaneously enabeling the search for better ones is a neutral network. When talking about neutral networks we will assume that selection acts exclusively upon isolated phenotypes, that is, we will assume to have a map assigning to phenotypes certain fitness values. This notion was introduced by S. Wright, who successfully used these maps to describe evolutionary processes. Since we have for each phenotype at least one genotype we have the following compositum of maps (assuming there are no multiple phenotypes for one genotype). We will refer to the first map as to the genotype phenotype map and call the preimage of a fixed phenotype its neutral network.
(Back to Top)
Combinatorial Optimization in Computational Biology - Project
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. We are now extending these algorithms to be able to accommodate additional experimental desiderata. This will enable full-scale automation of DNA sequencing and the elimination of a labor-intensive bottleneck that currently retards the process. Another optimization problem we are addressing in this context is that of pooling, or group testing. Pooling is the technique of choice for identifying a few "positive'' clones from a large collection consisting mainly of "negatives''. While designing efficient yet accurate pools appears at first sight to be computationally hard, experience with sequencing algorithms suggests to us that useful variants on the problem may in fact be solvable in polynomial time. We are working towards developing algorithms for constructing implementable pooling designs that will robustly yield the desired identifications, using a minimum number of pools.
For more information visit the Combinatorial Optimization in Biology site. Joint research program with CCS-3, T-10.
(Back to Top)
|
|
