Graduate School in Nonlinear Science

Sponsored by The Danish Research Agency

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


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

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.