Project code: BRICKS-afm2.1-ACMB

Research group (till 31-12-2008): Algorithms, Combinatorics and Optimization (PNA1)

In this project we researched the applications of algorithms and combinatorial methods to problems inspired/dictated by (computational) biology.

The increasing use of computational methods in biology has led to an explosion in biological data. Naive algorithms to process such data are often unacceptably slow and an intelligent algorithmic/combinatorial approach is necessary. Indeed, the last ten years has shown that there are many areas in biology where a combinatorial optimization approach (i.e. obtaining solutions which minimise or maximise some objective function) is valuable for gaining biological insights. A classic example is the problem Sorting By Reversals, which asks for the smallest number of substring reversals required to transform one permutation into another. This is a well-motivated abstraction which models the fact that, in nature, periodic genomic rearrangement events are responsible for reversing genomic intervals, and can thus be used to estimate evolutionary similarity and dissimilarity between two apparently different species.

This project has a discrete, combinatorial flavour, in contrast to many other 'mathematics in biology' projects which tend more towards continuous analysis e.g. partial differential equations.

Members

Coordinator of this project
Leen Stougie

Other member
Steven Kelk

Cooperation
Dr. Leen Stougie and dr. Steven Kelk work in close collaboration with several researchers from other CWI themes and clusters, most notably John Tromp (INS4) and Rudi Cilibrasi (also INS4).

The project has continued within the group: Life Sciences.