APPROXBIOGEO · Geometric approximation algorithms and applications to bioinformatics
FP6 — Marie Curie Actions (Human Resources and Mobility)
- Duration
- 2006-12-01 → 2008-11-30
- EU contribution
- €80,000
- Participants
- 1
- Scheme
- IRG
Lines connect the coordinator with its partners.
Results in brief
Final Activity Report Summary - APPROXBIOGEO (Geometric approximation algorithms and applications to bioinformatics)
We designed approximation algorithms for the following geometric problems. The first problem we considered is to compute a shortest path between two points under anisotropic and non-uniform metrics. Second, we showed how to construct approximate Voronoi diagrams under doubling metrics, and how to construct approximate Voronoi cells. Then, we gave efficient approximation algorithms for matching two geometric shapes, and for fitting a histogram to a set of points. Finally, we developed a program for predicting the three-dimensional shape of a protein, given its amino-acid sequence.
Data: CORDIS, © European Union
Project objective
The goal of this project is twofold.- First, we will design and analyse approximation algorithms for geometric problems. We will work on two types of problems: shortest paths problems in weighted (and possibly anisotropic) regions, and approximate Vorono i diagrams. Unlike previous work, our work on the weighted region problem will focus on removing the dependency on the bit-complexity of the input and, at the same time, remove the dependency on extra geometric parameters such as the measure of the smallest angle in the input triangulation. We will try to generalize approximate Voronoi diagrams to arbitrary convex distance functions, and we will try to obtain approximate Voronoi cells with a small number of facets.- Second, we will apply techniques from computational geometry (and in particular, from geometric approximation algorithms) to bioinformatics problems. We want to combine existing expertise of INRA in bioinformatics and statistics with A. Vigneron's knowledge of geometric algorithms and data structures. We will work on ab-initio protein structure prediction, docking and 5D biological image analysis.
Original text from CORDIS.
Participants
- INSTITUT NATIONAL DE LA RECHERCHE AGRONOMIQUE · PARISCoordinatorFrance
Links
Data: CORDIS, © European Union