Volume 3, Number 2, Fall 2008

EN:

Polymers are compounds formed by the joining of smaller, often repeating, units linked by covalent bonds. The analysis of their structure is a fundamental issue in a number of fields. This work gives an exact mathematical formalization of the problems of determining the composition or the sequence of polymers by processing data obtained from their tandem mass spectrometry analysis and describes effective solution algorithms for such problems. The procedure is exemplified by considering the case of peptides, but may be used for generic polymeric compounds submitted to mass spectrometry. The analysis does not rely on databases, but on computation of solutions compatible with the given spectral data. Note that the proposed approach guarantees finding all the above solutions, while other known methods cannot give this guarantee. Both the computational running times and the biological accuracy of the experimental analyses are encouraging.

EN:

In this paper we formulate four problems in computational molecular biology as 0-1 quadratic programs. These problems are all NP-hard, and the current solution methods used in practice consist of heuristics or approximation algorithms tailored to each problem. Using test problems from scientific databases, we address the question, “Can a general-purpose solver obtain good answers in reasonable time?” In addition, we use the latest heuristics as incumbent solutions to address the question, “Can a general-purpose solver confirm optimality or find an improved solution in reasonable time?” Our computational experiments compare four different reformulation methods: three forms of linearization and one form of quadratic convexification.

EN:

One of the main tasks in computational biology is the computation of alignments of genomic sequences to reveal their commonalities. In case of DNA or protein sequences, sequence information alone is usually sufficient to compute reliable alignments. RNA molecules, however, build spatial conformations, which can be represented by graph-like secondary structures. Often, secondary structures are more conserved than the actual sequence. Hence, computing reliable alignments of RNA molecules should take this additional information into account.

We present a novel framework for the computation of exact multiple sequence-structure alignments. We give a graph-theoretic representation of the sequence-structure alignment problem and phrase it as an integer linear program. We identify a class of constraints that make the problem easier to solve and relax the original integer linear program in a Lagrangian manner. We run experiments on data from the RFAM database and compare the performance of our model to heuristically inferred multiple structural alignments. Finally, experiments on a recently published benchmark show that in the pairwise case our algorithm achieves results comparable to those obtained by more costly dynamic programming algorithms while needing less computation time.

EN:

High-throughput technology has enabled molecular biologists to study genes and gene products of living organisms on a systems level: nowadays, it is possible to measure the activity of thousands of genes in a single experiment. With this type of measurement, one aims at revealing the structure and the dynamics of the underlying genetic regulatory network. In particular, one is interested in identifying groups of genes with shared functions or shared regulatory mechanisms which leads to various challenging optimization problems.

Here, we consider the problem of finding multiple, diverse modules of genes that exhibit similar trends regarding one or several gene expression data sets. We present a hybrid evolutionary algorithm for this task that distinguishes itself from previous approaches in three aspects: (i) a set of diverse modules can be found in a single optimization run, (ii) multiple data sets can be considered simultaneously without mixing the corresponding data, and (iii) the trade-off between available runtime and quality of the generated solution can be set by the user.

EN:

We present an algorithm for optimal step-and-shoot multileaf collimator field segmentation minimizing tongue-and-groove effects. Adapting the concepts of [7] we characterize the minimal decomposition time as the maximal weight of a path in a properly constructed weighted digraph. We also show that this decomposition time can be realized by a unidirectional plan, thus proving that the algorithm from [9] is monitor unit optimal in general and not only for unidirectional leaf movement. Our characterization of the minimal decomposition time has the advantage that it can be used to derive a heuristic for the reduction of the number of shape matrices following the ideas of [7].

EN:

We illustrate how an iterative method and the idea of recurrence can be employed to optimize chemotherapy scheduling. We take the density of host and cancer cells as the states, and aim at minimizing the treatment period for each state. We derive the equation satisfied by the optimal values of the objective function at different states. The theorem of existence and uniqueness for the solution to this equation is proved, and some important properties of the optimal values of the objective function are presented. The optimal treatment schedule can be derived directly from the optimal objective function values at different states. We use an iterative method to solve the equation numerically. Some ideas to further enhance the model are discussed.

EN:

This paper describes a methodology which combines elements of statistics, probability, mathematical programming, simulation, multiobjective optimization and metaheuristics, to analyze management problems in a health care context. We apply this approach to a staffing problem in a primary care center, taking into account both cost and service quality criteria. We illustrate our approach with a case study.