Configurational analyses of combinatorial and biological optimization problems.
(Konfigurationsanalysen kombinatorischer und biologischer Optimierungsprobleme.)

*(German)*Zbl 0790.92018
Bielefeld: Univ. Bielefeld, Fak. f. Math. vi, 204 p. (1992).

This doctoral dissertation is devoted to the design of a method for the comparative analysis of sequence configurations and its application to various optimization problems as well as to the evolution process of viral organisms. A basic step of the method consists in determining the isometric group of the sequence space with respect to the associated metric and in deriving a complete system of invariants that enables the unique (up to congruence) characterization of configurations. This leads to a new approach for the study of divergence structures and possible paths of evolution for sequence families.

The method is well-suited to analyse structures of configurations, which represent local minima of optimization problems such as the travelling salesman-, the spin-glass- or the graph partitioning problem. A main result is the strong evidence for the existence of an only trivial ultrametric in the local minima of these problems.

A structural analysis of the evolution process of viral sequences represents the third part of the study. Viral organisms are natural examples of an evolutionary optimization problem. The structures of several virus families are compared to each other. Moreover, the immune deficiency virus is taken as an example to show that the temporal calibration of rapidly evolving organisms by use of classical distance analyses can lead to erroneous interpretations. The application of the ‘statistical geometry’ - method developed in part 1, however, allows a new temporal classification of the age of origin of this virus.

The method is well-suited to analyse structures of configurations, which represent local minima of optimization problems such as the travelling salesman-, the spin-glass- or the graph partitioning problem. A main result is the strong evidence for the existence of an only trivial ultrametric in the local minima of these problems.

A structural analysis of the evolution process of viral sequences represents the third part of the study. Viral organisms are natural examples of an evolutionary optimization problem. The structures of several virus families are compared to each other. Moreover, the immune deficiency virus is taken as an example to show that the temporal calibration of rapidly evolving organisms by use of classical distance analyses can lead to erroneous interpretations. The application of the ‘statistical geometry’ - method developed in part 1, however, allows a new temporal classification of the age of origin of this virus.

Reviewer: R.Euler (Brest)

##### MSC:

92D15 | Problems related to evolution |

90C90 | Applications of mathematical programming |

49N70 | Differential games and control |

49N75 | Pursuit and evasion games |