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.