APPROXBIOGEO · Geometric approximation algorithms and applications to bioinformatics
6РП — Действия „Мария Кюри“
- Период
- 2006-12-01 → 2008-11-30
- Финансиране от ЕС
- 80 000 €
- Участници
- 1
- Схема
- IRG
Линиите свързват координатора с партньорите.
Накратко на български
Геометрични алгоритми за приближено изчисляване се прилагат за задачи като определяне на най-късия път между две точки или предсказване на 3D формата на протеин. Тези методи помагат за по-бързото и ефективно анализиране на сложни данни в биоинформатиката.
Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.
Резултати накратко
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.
Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз
Цел на проекта
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.
Оригинален текст от CORDIS (на английски).
Участници
- INSTITUT NATIONAL DE LA RECHERCHE AGRONOMIQUE · PARISКоординаторФранция
Връзки
Данни: CORDIS, © Европейски съюз