# Graduate School in Nonlinear Science

**
MIDIT OFD CATS
Modelling, Nonlinear Dynamics Optics and Fluid Dynamics Chaos and Turbulence Studies
and Irreversible Thermodynamics Risø National Laboratory Niels Bohr Institute and
Technical University of Denmark Building 128 Department of Chemistry
Building 321 P.O. Box 49 University of Copenhagen
DK-2800 Lyngby DK-4000 Roskilde DK-2100 Copenhagen Ø
Denmark Denmark Denmark
**

**COMPUTATIONAL PROBLEMS IN BIOINFORMATICS **

**by Paul Fischer**

The Technical University of Denmark

Informatics and Mathematical Modelling (IMM)

Richard Petersens Plads

Building 322, DK-2800 Kgs. Lyngby

Tel. +45 4525 3713

email: paf@imm.dtu.dk

MIDIT-seminar 513

**Thursday, September 19, 2002, 16.00 h**

at IMM, Bldg. 305, Room 053, DTU

**Abstract:**
The talk gives an overview of some computational
problems in bioinformatics. A fundamental problem
is that of "aligning" two strands of genetic information,
e.g., two DNA sequences. An alignment matches parts
of one strand to parts of the other one in such
a way to maximise a given objective function.
Combinatorial pattern matching algorithms for this problem
are known.
In the last years an alternative approach has proved to
be quite successful, the use of Makrov-models.
These are randomized devices that generate
strands of (abstract) genetic information.
The basic idea then is to construct for each
given strand a Makrov-model that generates the
strand with high probability. Then these models
are applied to the other strands to detect which
parts are similar (or different).
We would like to present the combinatorial
approach as well as the statistical one.